multiplos - Evaluación diferida de términos en una lista infinita en Haskell

multiplos en haskell

Question

Tengo curiosidad sobre el rendimiento en tiempo de ejecución de una lista infinita como la siguiente:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Esto creará una lista infinita de la secuencia de fibonacci.

Mi pregunta es si hago lo siguiente:

takeWhile (<5) fibs

¿Cuántas veces evalúa fibs cada término en la lista? Parece que desde que takeWhile comprueba la función de predicado para cada elemento en la lista, la lista de fibs evaluará cada término varias veces. Los primeros 2 términos se dan de forma gratuita. Cuando takeWhile quiera evaluar (<5) en el tercer elemento, obtendremos:

1 : 1 : zipWith (+) [(1, 1), (1)] => 1 : 1 : 3

Ahora, una vez que takeWhile quiere evaluar (<5) en el 4º elemento: la naturaleza recursiva de fibs construirá la lista de nuevo de la siguiente manera:

1 : 1 : zipWith (+) [(1, 2), (2, 3)] => 1 : 1 : 3 : 5

Parecería que el tercer elemento necesita ser computado de nuevo cuando queremos evaluar el valor del 4º elemento. Además, si el predicado en takeWhile es grande, indicaría que la función está haciendo más trabajo que es necesario ya que está evaluando cada elemento precedente en la lista varias veces. ¿Está mi análisis aquí correcto o Haskell está haciendo un almacenamiento en caché para evitar evaluaciones múltiples aquí?

Answer 1

Cuando se evalúa algo en Haskell, se mantiene evaluado, siempre que se haga referencia al mismo nombre ¹ .

En el siguiente código, la lista l solo se evalúa una vez (lo que podría ser obvio):

let l = [1..10]
print l
print l -- None of the elements of the list are recomputed

Incluso si algo se evalúa parcialmente, esa parte se mantiene evaluada:

let l = [1..10]
print $ take 5 l -- Evaluates l to [1, 2, 3, 4, 5, _]
print l          -- 1 to 5 is already evaluated; only evaluates 6..10

En su ejemplo, cuando se evalúa un elemento de la lista de fibs , se mantiene evaluado. Dado que los argumentos a zipWith referencia a la lista de fibs real, significa que la expresión de fibs utilizará la lista de fibs ya parcialmente calculada al calcular los siguientes elementos en la lista. Esto significa que ningún elemento se evalúa dos veces.

¹ Esto, por supuesto, no es estrictamente requerido por la semántica del lenguaje, pero en la práctica, este es siempre el caso.

Answer 2

Esta es una estructura de datos perezosos autorreferencial, donde las partes "posteriores" de la estructura se refieren a partes anteriores por su nombre.

Inicialmente, la estructura es solo un cálculo con punteros no evaluados de nuevo a sí mismo. A medida que se desarrolla, los valores se crean en la estructura. Las referencias posteriores a las partes ya computadas de la estructura pueden encontrar el valor que ya existe esperándolos. No es necesario volver a evaluar las piezas, ¡y no hay trabajo adicional que hacer!

La estructura en la memoria comienza simplemente como un puntero no evaluado. Una vez que miramos el primer valor, se ve así:

> take 2 fibs

(un puntero a una celda de cons, que apunta a ''1'', y una cola que contiene el segundo ''1'', y un puntero a una función que contiene referencias a fibs, y la cola de fibs.

La evaluación de un paso más expande la estructura y desliza las referencias a lo largo de:

Y así vamos desplegando la estructura, cada vez produciendo una nueva cola no evaluada, que es un cierre que contiene referencias al primer y segundo elementos del último paso. Este proceso puede continuar infinitamente :)

Y como nos referimos a los valores anteriores por su nombre, GHC los conserva en memoria para nosotros, por lo que cada elemento se evalúa solo una vez.

Answer 3

Ilustración:

module TraceFibs where

import Debug.Trace

fibs :: [Integer]
fibs = 0 : 1 : zipWith tadd fibs (tail fibs)
  where
    tadd x y = let s = x+y
               in trace ("Adding " ++ show x ++ " and " ++ show y
                                   ++ "to obtain " ++ show s)
                        s

Que produce

*TraceFibs> fibs !! 5
Adding 0 and 1 to obtain 1
Adding 1 and 1 to obtain 2
Adding 1 and 2 to obtain 3
Adding 2 and 3 to obtain 5
5
*TraceFibs> fibs !! 5
5
*TraceFibs> fibs !! 6
Adding 3 and 5 to obtain 8
8
*TraceFibs> fibs !! 16
Adding 5 and 8 to obtain 13
Adding 8 and 13 to obtain 21
Adding 13 and 21 to obtain 34
Adding 21 and 34 to obtain 55
Adding 34 and 55 to obtain 89
Adding 55 and 89 to obtain 144
Adding 89 and 144 to obtain 233
Adding 144 and 233 to obtain 377
Adding 233 and 377 to obtain 610
Adding 377 and 610 to obtain 987
987
*TraceFibs>

Answer 4

Piénsalo de esta manera. La variable fib es un puntero a un valor perezoso. (Puede pensar en un valor Lazy a = IORef (Unevaluated (IO a) | Evaluated a) debajo como una estructura de datos como (sin sintaxis real) Lazy a = IORef (Unevaluated (IO a) | Evaluated a) ; es decir, comienza como no evaluado con un procesador y luego cuando se lo evalúa "cambia" a algo que recuerda el valor.) Debido a que la expresión recursiva utiliza la variable fib , tienen un puntero al mismo valor diferido ("comparten" la estructura de datos). La primera vez que alguien evalúa fib , ejecuta el thunk para obtener el valor y ese valor se recuerda. Y como la expresión recursiva apunta a la misma estructura de datos diferida, cuando la evalúan, ya verán el valor evaluado. Al atravesar la "lista infinita" perezosa, solo habrá una "lista parcial" en la memoria; zipWith dos punteros a "listas" que son simplemente punteros a miembros anteriores de la misma "lista", debido al hecho de que comenzó con punteros a la misma lista.

Tenga en cuenta que esto no es realmente "memorando"; es solo una consecuencia de referirse a la misma variable. En general, no hay "memoria" de los resultados de la función (lo siguiente será ineficaz):

fibs () = 0 : 1 : zipWith tadd (fibs ()) (tail (fibs ()))