autorreferencia en Haskell funciona

Question

estoy aprendiendo Haskell y que la siguiente expresión en Haskell Wiki realmente me desconcertado:

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

Estoy totalmente no puede entender por qué esto funciona.

Si aplico la lógica de currying estándar (zipWith (+)) devuelve una lista de tomas de función como argumento y, a su vez, devuelve otra función que toma otra lista como argumento y devuelve una lista (zipWith::(a -> b -> c) -> [a] -> [b] -> [c]). Por lo tanto, fibs es una referencia a una lista (que aún no se ha evaluado) y (tail fibs) es la cola de la misma lista (no evaluada). Cuando intentamos evaluar (take 10 fibs), los primeros dos elementos están vinculados a 0 y 1. En otras palabras, fibs==[0,1,?,?...] y (tail fibs)==[1,?,?,?]. Después de que la primera adición completa fibs se convierte en [0,1,0+1,?,..]. Del mismo modo, después de la segunda adición obtenemos [0,1,0+1,1+(0+1),?,?..]

• ¿Mi lógica es correcta?
• ¿Hay un más simple manera de explicar esto? (¿Alguna idea de las personas que saben qué hace el compilador Haskell con este código?) (se aceptan enlaces y referencias)
• Es cierto que este tipo de código solo funciona debido a la evaluación perezosa?
• ¿Qué evaluaciones ocurren cuando hago fibs !! 4?
• ¿Este código asume que zipWith procesa elementos de principio a fin? (Creo que no debería, pero no entiendo por qué no)

Edit2: acabo de encontrar la pregunta anterior preguntó y respondió bien here. Lo siento si desperdicié el tiempo de alguien.

EDIT: He aquí un caso más difícil de entender (fuente: Project Euler forums):

filterAbort :: (a -> Bool) -> [a] -> [a] 
filterAbort p (x:xs) = if p x then x : filterAbort p xs else [] 

main :: Int 
main = primelist !! 10000 
     where primelist = 2 : 3 : 5 : [ x | x <- [7..], odd x, all (\y -> x `mod` y /= 0) (filterAbort (<= (ceiling (sqrt (fromIntegral x)))) primelist) ] 

Tenga en cuenta que all (\y -> x mod y /= 0)... ¿Cómo puede referirse a x aquí no causar una recursión infinita?

Answer 1

voy a trazar la evaluación para usted:

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

Con:

> zipWith f (a:as) (b:bs) = f a b : zipWith f as bs 
> zipWith _ _  _  = [] 

> tail (_:xs)    = xs 
> tail []     = error "tail" 

Así:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 
↪ fibs = 0 : 1 : ((+) 0 1 : zipWith (+) (tail fibs) (tail (tail fibs))) 
↪ fibs = 0 : 1 : 1 : ((+) 1 1 : zipWith (+) (tail (tail fibs)) (taii (tail (tail fibs)))))  
↪ fibs = 0 : 1 : 1 : 2 : ((+) 1 2 : zipWith (+) (tail (tail (tail fibs))) (tail (taii (tail (tail fibs)))))) 
↪ fibs = 0 : 1 : 1 : 2 : 3 : ((+) 2 3 : zipWith (+) (tail (tail (tail (tail fibs)))) (tail (tail (taii (tail (tail fibs))))))) 

Etc. Así que si el índice en esta estructura, lo hará fuerce cada paso de fibs a ser evaluado hasta que se encuentre el índice.

¿Por qué es esto eficiente? Una palabra: compartiendo.

Como se calcula fibs, crece en el montón, registrando valores que han sido computadora. Las referencias posteriores a fibs llegan a reutilizar todos los valores previamente calculados para fibs. ¡Memorización gratuita!

¿Cómo se ve ese intercambio en el montón?

A medida que solicita el objeto en el final de la lista, Haskell calcula el siguiente valor, lo registra, y se mueve que la auto-referencia de un nodo.

El hecho de que esto termine depende fundamentalmente de la pereza.