promedio - ¿Cuál es la diferencia entre una lista cíclica y una lista infinita en haskell?

multiplos de un numero en haskell

Question

Referencia a la respuesta de @dfeuer a esta pregunta: la forma menos costosa de construir una lista cíclica en Haskell , que dice que usar las listas cíclicas "derrota" al recolector de basura, ya que tiene que mantener todo lo que ha consumido de una lista cíclica asignada hasta que elimine la referencia a cualquier celda de contras en la lista.

Aparentemente en Haskell, una lista cíclica y una lista infinita son dos cosas separadas. Este blog ( https://unspecified.wordpress.com/2010/03/30/a-doubly-linked-list-in-haskell/ ) dice que si implementa el cycle siguiente manera:

cycle xs = xs ++ cycle xs

Es una lista infinita, no una lista cíclica. Para que sea cíclico, debes implementarlo de esta manera (como se encuentra en el código fuente de Prelude):

cycle xs = xs'' where xs'' = xs ++ xs''

¿Cuál es exactamente la diferencia entre estas dos implementaciones? ¿Y por qué es que si usted se aferra a una celda de contras en algún lugar de una lista cíclica, el recolector de basura tiene que guardar todo antes de que se asigne también?

Answer 1

La diferencia está enteramente en la representación de la memoria. Desde el punto de vista de la semántica del lenguaje, no se pueden distinguir, no se puede escribir una función que pueda distinguirlos, por lo que sus dos versiones de cycle se consideran dos implementaciones de la misma función (son exactamente las mismo mapeo de argumentos a resultados). De hecho, no sé si la definición del lenguaje garantiza que una de ellas sea cíclica y la otra infinita.

Pero de todos modos, vamos a sacar a la luz el arte ASCII. Lista cíclica:

   +----+----+                 +----+----+
   | x0 |   ----->   ...   --->| xn |    |
   +----+----+                 +----+-|--+
     ^                                |
     |                                |
     +--------------------------------+

Lista infinita:

   +----+----+
   | x0 |   ----->  thunk that produces infinite list
   +----+----+

La cosa con la lista cíclica es que desde cada celda de contras de la lista hay un camino a todos los demás y a sí mismo . Esto significa que, desde el punto de vista del recolector de basura, si una de las celdas contras es accesible, entonces todas son. En la lista infinita simple, por otro lado, no hay ciclos, por lo que desde una celda de contras dada solo se puede alcanzar a sus sucesores.

Tenga en cuenta que la representación de la lista infinita es más poderosa que la cíclica, porque la representación cíclica solo funciona con listas que se repiten después de cierto número de elementos. Por ejemplo, la lista de todos los números primos puede representarse como una lista infinita, pero no como una lista cíclica.

Tenga en cuenta también que esta distinción se puede generalizar en dos formas distintas de implementar la función de fix :

fix, fix'' :: (a -> a) -> a
fix  f = let result = f result in result
fix'' f = f (fix'' f)

-- Circular version of cycle:
cycle  xs = fix (xs++)

-- Infinite list version of cycle:
cycle'' xs = fix'' (xs++)

Las bibliotecas de GHC van para mi definición de fix . La forma en que GHC compila el código significa que el procesador creado para el result se usa tanto como el resultado como el argumento de la aplicación de f . Es decir, el thunk, cuando es forzado, llamará al código objeto para f con el propio thunk como argumento, y reemplazará el contenido del thunk con el resultado.

Answer 2

Las listas cíclicas y las listas infinitas son diferentes operativamente, pero no semánticamente.

Una lista cíclica es literalmente un bucle en la memoria (imagina una lista enlazada individualmente con los punteros que siguen un ciclo), por lo que ocupa un espacio constante. Debido a que se puede acceder a cada celda de la lista desde cualquier otra celda, mantenerla en una celda hará que se retenga la lista completa.

Una lista infinita ocupará más y más espacio a medida que evalúes más. Los elementos anteriores se recolectarán en la basura si ya no son necesarios, por lo que los programas que la procesan pueden ejecutarse en un espacio constante, aunque la sobrecarga de recolección de basura será mayor. Si se necesitan elementos anteriores de la lista, por ejemplo, porque mantiene una referencia al encabezado de la lista, la lista consumirá un espacio lineal a medida que lo evalúa, y finalmente agotará la memoria disponible.

La razón de esta diferencia es que, sin optimizaciones, una implementación típica de Haskell como GHC asignará memoria una vez para un valor , como xs'' en la segunda definición de cycle , pero asignará repetidamente memoria para una invocación de función, como el cycle xs en la primera definición.

En principio, las optimizaciones pueden convertir una definición en otra, pero debido a las características de rendimiento bastante diferentes, es poco probable que esto suceda en la práctica, ya que los compiladores generalmente son bastante conservadores al hacer que los programas se comporten peor. En algunos casos, la variante cíclica será peor debido a las propiedades de recolección de basura ya mencionadas.

Answer 3

cycle xs = xs ++ cycle xs            -- 1
cycle xs = xs'' where xs'' = xs ++ xs'' -- 2

¿Cuál es exactamente la diferencia entre estas dos implementaciones?

Usando GHC, la diferencia es que la implementación # 2 crea un valor autorreferencial ( xs'' ), mientras que # 1 simplemente crea un thunk que resulta ser el mismo.

¿Y por qué es que si usted se aferra a una celda de contras en algún lugar de una lista cíclica, el recolector de basura debe guardar todo antes de que se asigne también?

Esto es de nuevo específico de GHC. Como dijo Luis, si tiene una referencia a una celda de contras en una lista cíclica, puede acceder a la lista completa simplemente dando una vuelta al ciclo. El recolector de basura es conservador y no recolectará nada que puedas alcanzar.

Haskell es puro y donde la refactorización es un sonido ... solo cuando ignora el uso de la memoria (y algunas otras cosas como el uso de la CPU y el tiempo de cálculo). Haskell el lenguaje no especifica qué debe hacer el compilador para diferenciar # 1 y # 2. GHC: la implementación sigue ciertos patrones de administración de memoria que son sensibles, pero no evidentes de inmediato.