Comprender el fibonacci de Haskell

Question

fibs :: [Int] 
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)] 

Esto genera la secuencia de Fibonacci.

entiendo el comportamiento de los guardias, de :, zip y tail, pero no entiendo <-. ¿Qué está haciendo aquí?

Answer 1

¿Cómo sabría el analizador qué entra (a, b) de lo contrario?

EDITAR: Gracias a ViralShah, haré esto un poco menos gnómico. El "< -" le dice al analizador que asigne la lista de pares desde el lado derecho "zip fibs (tail fibs)" al lado izquierdo "(a, b)".

Answer 2

La lista comprensión en los soportes:

[ a + b | (a, b) <- zip fibs (tail fibs)] 

devuelve una lista que contiene la salida de (a + b) donde las variables A y B vienen del resultado de

zip fibs (tail fibs) 

Answer 3

Debido a la upvotes Hice mi comentario en una respuesta.

Lo que ves no es un guardia pero es list comprehension. Para empezar, piense en ello como una forma de expresar una notación de conjunto matemático como A = {x | x elemento N} que significa algo como: El conjunto A es el conjunto de todos los números naturales. En la lista de comprensión que sería [x | x <- [1..] ].

También puede usar restricciones en sus números: [x | x <- [1..], x `mod` 2 == 0 ] y muchas otras cosas.

Hay muchos turorials buenos de Haskell que cubren la comprensión de la lista e incluso una pregunta de StackOverflow con respecto a los recursos de Haskell.

Answer 4

Lo único delicado es el zip fibs (tail fibs). zip solo hace una lista por pares de cada uno de sus argumentos. Así que si usted tiene dos listas como esta:

[ 1, 2, 3, 4 ] 
[ "a", "b", "c", "d" ] 

Zipping ellos harán:

[ (1,"a"), (2,"b"), (3,"c"), (4,"d") ] 

La flecha izquierda (asignación en un patrón desestructuración) simplemente extrae los elementos emparejados por lo que se pueden sumar. Las dos listas que se comprimen son fibs y (tail fibs) - en otras palabras, la secuencia de Fibonacci y la secuencia de Fibonacci compensada por 1 elemento. Haskell se evalúa con pereza, por lo que puede calcular la lista por cuantos elementos se requieran. Esto se aplica a zip también.

Answer 5

Extendemos.

zip crea pares de los contenidos de dos listas. Así que el primer par zip fibs (tail fibs) nos da es (0, 1), que suma 1. Entonces, la lista es [0,1,1]. Ahora sabemos tres elementos en la lista, por lo que la comprensión de la lista puede continuar, tomando el siguiente elemento de la lista y el siguiente elemento de la cola, que da (1,1) - sumados, haciendo 2. Luego obtenemos el siguiente par, que es (1,2), haciendo el siguiente número en la secuencia 3. Esto puede continuar infinitamente, ya que la comprensión siempre proporcionará suficientes elementos.

Answer 6

Por lo que vale la pena, creo que la siguiente versión más fácil de entender:

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

Answer 7

Una ventaja de la programación funcional es que se puede evaluar una expresión con la mano como si fuera un problema de matemáticas:

fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)] 
    = 0 : 1 : [ a + b | (a, b) <- zip [0, 1, ??] (tail [0, 1, ??])] 

Aquí el ?? es la pieza que aún no se ha evaluado. Lo llenaremos mientras procedemos.

 = 0 : 1 : [ a + b | (a, b) <- zip [0, 1, ??] [1, ??])] 
    = 0 : 1 : [ a + b | (a, b) <- (0, 1) : zip [1, ??] [??]] 

en cuenta que estoy elidiendo la evaluación de zip desde su definición no se da aquí y los detalles no son realmente con la cuestión actual. Esta es la notación que usaré para mostrar que cada par de números es creado por zip y consumido por la lista de comprensión.

 = 0 : 1 : 0+1 : [ a + b | (a, b) <- zip [1, ??] [??]] 
    = 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, ??] [??]] 

Ahora sabemos que el siguiente elemento de la ?? es un 1:

 = 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, 1, ??] [1, ??]] 
    = 0 : 1 : 1 : [ a + b | (a, b) <- (1, 1) : zip [1, ??] [??]] 
    = 0 : 1 : 1 : 1+1 : [ a + b | (a, b) <- zip [1, ??] [??]] 
    = 0 : 1 : 1 : 2 : [ a + b | (a, b) <- zip [1, ??] [??]] 

Y el siguiente elemento es un 2:

 = 0 : 1 : 1 : 2 : [ a + b | (a, b) <- zip [1, 2, ??] [2, ??]] 

Enjuague y repita.

Answer 8

Define este diagrama corriente

  .----->>------->>----. 
     /     \ 
     /     / 
     \     /  
    <---- 0 <---- 1 ---<<--- (+)  
       /   \   
       \    \   
        \   /  
        *---->>------*  

que tira nueva entrada de sí misma tal como se produce, pero siempre por uno y dos posiciones antes del punto de la producción, el mantenimiento de los dos "punteros traseras" en la secuencia como estaba. Esto se refleja en la definición fibs = 0:1:[ a+b | a <- fibs | b <- tail fibs], con comprensiones de listas paralelas (:set -XParallelListComp etc.).

Ya que sólo utiliza sus últimos dos elementos, es equivalente a

map fst . iterate (\(a, b) -> (b, a+b)) $ (0,1) 

Answer 9

yo todavía no entiendo. Me gusta esta respuesta: https://stackoverflow.com/a/42183415/246387 (desde code-apprentice).

pero yo no entiendo cómo a partir de esta línea:

= 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, ??] [??]] 

que se mueva a lo siguiente:

= 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, 1, ??] [1, ??]] 

y además de esto, tengo otra cosa que me molesta:

¿Cómo puedo usar fib dentro de la lista de comprensión si no tengo fib en absoluto (por lo que parece, pero estoy seguro de que estoy equivocado), porque fib isn ' t calculado aún. "espera" (en el lado izquierdo del signo igual) para calcular en el lado derecho (del signo igual).