Listas de diferencias en programación funcional

13

La pregunta ¿Qué hay de nuevo en estructuras de datos puramente funcionales desde Okasaki? , y la respuesta épica de jbapple, mencionó el uso de listas de diferencias en la programación funcional (en oposición a la programación lógica), que es algo que me ha interesado recientemente. Esto me llevó a encontrar la implementación de la lista de diferencias para Haskell. Tengo dos preguntas (perdóname / corrígeme si debo hacer dos preguntas diferentes en StackExchange).

La simple pregunta es, ¿alguien conoce la consideración académica de las listas de diferencias en la programación funcional y / o implementaciones además de la de la biblioteca Haskell? La respuesta de jbapple no dio una cita para las listas de diferencias (las listas de diferencias en la programación lógica existen en la tradición y en un par de fuentes que tengo Around Here Somewhere (TM)). Antes de encontrar la implementación de Haskell, no sabía que la idea había saltado de la lógica a la programación funcional. Por supuesto, las listas de diferencias de Haskell son una especie de uso natural de las funciones de orden superior y funcionan de manera bastante diferente a las de la programación lógica, pero la interfaz es ciertamente similar.

Lo más interesante (y mucho más difuso) sobre lo que quería preguntar es si el límite superior asintótico reclamado para la biblioteca de la lista de diferencias de Haskell mencionada anteriormente parece correcto / plausible. Mi confusión puede deberse a que me falta algo obvio sobre el razonamiento de complejidad con pereza, pero los límites reclamados solo tienen sentido para mí si la sustitución sobre una estructura de datos grande (o formación de cierre, o búsqueda variable, o algo ) siempre lleva tiempo constante. ¿O es la "captura" simplemente que no hay límite en el tiempo de ejecución para "cabeza" y "cola" precisamente porque esas operaciones pueden tener que pasar por un montón arbitrario de cálculos / sustituciones diferidos?

Rob Simmons
fuente
1
Al principio me confundían los "lenguajes de programación funcional (en oposición a los lenguajes de programación funcional)", pero ¿querías escribir "(en oposición a los lenguajes de programación lógica)"?
Tsuyoshi Ito
Oh, oops, sí, eso es lo que quise decir, ahora está arreglado.
Rob Simmons
La segunda pregunta me parece más apropiada en Stack Overflow pero, ahora que la ha hecho aquí, puede ser mejor esperar para ver si alguien puede responder aquí. Personalmente, no puedo encontrar ninguna razón para dudar de los límites alegados al leer el código fuente, pero no he seguido su razonamiento para dudar de ellos, y también es posible que me falte algo.
Tsuyoshi Ito

Respuestas:

8

¿O es la "captura" simplemente que no hay límite en el tiempo de ejecución para "cabeza" y "cola" precisamente porque esas operaciones pueden tener que pasar por un montón arbitrario de cálculos / sustituciones diferidos?

Creo que eso es más o menos correcto. Sin embargo, los DL solo tienen operaciones de construcción rápidas, por lo que el arado es , donde m es el número de operaciones utilizadas para construir el DL.Θ(metro)metro

La siguiente versión desfuncionalizada de algunas de las operaciones esenciales requiere pereza para , pero de lo contrario debería ser una forma directa de comprender los límites de complejidad que se reclaman en el original .O(1) fromList

{-# LANGUAGE NoMonomorphismRestriction #-}

data DL a = Id
          | Cons a
          | Compose (DL a) (DL a)

fromList [] = Id
fromList (x:xs) = Compose (Cons x) (fromList xs)

toList x = help x []
    where help Id r = r
          help (Cons a) r = a:r
          help (Compose f g) r = help f $ help g r

empty = Id

singleton = Cons

cons x = append (singleton x)

append = Compose

snoc xs x = append xs (singleton x)

Θ(norte)headtail[a] -> [a]toList

jbapple
fuente
Entonces, lo que está obteniendo de la pereza es que pedir la cola de una lista dos veces no hará la operación costosa dos veces, lo cual es bueno.
Rob Simmons
@ Rob, no entiendo lo que quieres decir con eso.
jbapple
Creo que el ejemplo que estaba tratando de hacer (mal) está ilustrado en este ejemplo: tengo una "diferencia" extraordinariamente larga en la lista de diferencias "xs" que hice repetidamente "husmeando" cosas en la lista original. La primera vez que llamo "head xs" espero que le tome a O (n) tiempo para hacer un cálculo diferido; sin embargo, debido a que ese cálculo debería ser memorizado, la segunda llamada a "head xs" (para el mismo "xs") debería tomar el tiempo O (1).
Rob Simmons
1
Bueno, estoy de acuerdo con eso, pero la pereza a la que hice referencia en mi respuesta fue sobre fromList, que no se usa en snoc o head. Entonces, como pedante como es, estaba confundido por el "qué" en tu declaración "lo que obtienes de la pereza". Diría que tu ejemplo y el mío son dos cosas que obtienes de la pereza.
jbapple
Ok, y esa aclaración también me ayuda a comprender mejor tu punto anterior.
Rob Simmons
11

Sí, los límites dependen de la suposición de que la composición de la función lleva tiempo constante. Básicamente, si tiene una lista de unión:

datatype 'a join = Nil | Cons of 'a * 'a join | Join of 'a join * 'a join

O(norte)

Neel Krishnaswami
fuente