haskell - tuplas - Comprender una lista definida recursivamente(fibs en términos de zipWith)

multiplicar haskell

Question

Estoy aprendiendo Haskell, y encontré el siguiente código:

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

que estoy teniendo problemas para analizar, en términos de cómo funciona. Es muy claro, entiendo que no se necesita nada más, pero me gustaría entender cómo Haskell logra "completar" las mentiras cuando escribo:

take 50 fibs

¿Alguna ayuda?

¡Gracias!

Answer 1

Echemos un vistazo a la definición de zipWith zipWith f (x:xs) (y:ys) = fxy : zipWith xs ys

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

Para take 3 fibs sustituyendo la definición de zipWith y xs = tail (x:xs) obtenemos 0 : 1 : (0+1) : zipWith (+) (tail fibs) (tail (tail fibs))

Para take 4 fibs sustituyendo una vez más, obtenemos 0 : 1 : 1 : (1+1) : zipWith (+) (tail (tail fibs)) (tail (tail (tail fibs)))

y así.

Answer 2

Escribí un artículo sobre esto hace un tiempo. Puedes encontrarlo here .

Como mencioné allí, lea el capítulo 14.2 en el libro de Paul Hudak "The Haskell School of Expression", donde habla sobre Recursive Streams, usando el ejemplo de Fibonacci.

Nota: la cola de una secuencia es la secuencia sin el primer elemento.

|---+---+---+---+----+----+----+----+------------------------------------| | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | Fibonacci sequence (fibs) | |---+---+---+---+----+----+----+----+------------------------------------| | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | tail of Fib sequence (tail fibs) | |---+---+---+---+----+----+----+----+------------------------------------|

Agregue las dos columnas: agregue fibs (fibs de la cola) para obtener la cola de la secuencia fib

|---+---+---+---+----+----+----+----+------------------------------------| | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | tail of tail of Fibonacci sequence | |---+---+---+---+----+----+----+----+------------------------------------|

agregar fibs (fibs de cola) se puede escribir como zipWith (+) fibs (fibs de cola)

Ahora, todo lo que necesitamos hacer es preparar la generación comenzando con los primeros 2 números de fibonacci para obtener la secuencia de fibonacci completa.

1: 1: zipWith (+) fibs (fibs de la cola)

Nota: Esta definición recursiva no funcionará en un lenguaje típico que haga una evaluación entusiasta. Funciona en Haskell ya que hace una evaluación perezosa. Entonces, si pides los primeros 4 números de fibonacci, toma 4 fibs , haskell solo calcula la secuencia suficiente como se requiere.

Answer 3

Explicaré un poco cómo funciona internamente. Primero, debes darte cuenta de que Haskell usa una cosa llamada thunk por sus valores. Un thunk es básicamente un valor que todavía no se ha calculado: piense en ello como una función de 0 argumentos. Siempre que Haskell quiera, puede evaluar (o evaluar parcialmente) el procesador, convirtiéndolo en un valor real. Si solo evalúa parcialmente un thunk, el valor resultante tendrá más thunk.

Por ejemplo, considera la expresión:

(2 + 3, 4)

En un lenguaje ordinario, este valor se almacenaría en la memoria como (5, 4) , pero en Haskell, se almacena como (<thunk 2 + 3>, 4) . Si solicita el segundo elemento de esa tupla, le dirá "4", sin agregar 2 y 3 juntos. Solo si solicita el primer elemento de esa tupla evaluará el procesador y se dará cuenta de que es 5.

Con fibs, es un poco más complicado, porque es recursivo, pero podemos usar la misma idea. Debido a que fibs no toma argumentos, Haskell almacenará permanentemente cualquier elemento de la lista que se haya descubierto; eso es importante.

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

Ayuda a visualizar el conocimiento actual de Haskell de tres expresiones: fibs , tail fibs y zipWith (+) fibs (tail fibs) . Asumiremos que Haskell comienza sabiendo lo siguiente:

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

Tenga en cuenta que la 2ª fila es solo la primera que se desplazó a la izquierda, y la 3ª fila es la suma de las dos primeras filas.

Pide take 2 fibs y obtendrás [0, 1] . Haskell no necesita evaluar más a fondo lo anterior para descubrirlo.

Pide take 3 fibs y Haskell obtendrá el 0 y 1, y luego se dará cuenta de que necesita evaluar parcialmente el thunk. Para evaluar completamente zipWith (+) fibs (tail fibs) , necesita sumar las dos primeras filas; no puede hacer eso completamente, pero puede comenzar a sumar las dos primeras filas:

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

Tenga en cuenta que ingresé el "1" en la 3ª fila, y también apareció automáticamente en la primera y segunda filas, ya que las tres filas comparten el mismo procesador (piénselo como un puntero al que se escribió). Y debido a que no terminó de evaluar, creó un nuevo procesador que contiene el resto de la lista, si alguna vez fuera necesario.

No es necesario, sin embargo, porque se take 3 fibs : [0, 1, 1] . Pero ahora, digamos que pides take 50 fibs ; Haskell ya recuerda el 0, 1 y 1. Pero necesita seguir. Entonces continúa sumando las primeras dos filas:

fibs                         = 0 : 1 : 1 : 2 : <thunk3>
tail fibs                    = 1 : 1 : 2 : <thunk3>
zipWith (+) fibs (tail fibs) = 1 : 2 : <thunk3>

...

fibs                         = 0 : 1 : 1 : 2 : 3 : <thunk4>
tail fibs                    = 1 : 1 : 2 : 3 : <thunk4>
zipWith (+) fibs (tail fibs) = 1 : 2 : 3 : <thunk4>

Y así sucesivamente, hasta que haya rellenado 48 columnas de la 3ra fila, y así haya resuelto los primeros 50 números. Haskell evalúa todo lo que necesita y deja el infinito "resto" de la secuencia como un objeto thunk en caso de que alguna vez necesite más.

Tenga en cuenta que si posteriormente solicita take 25 fibs , Haskell no lo evaluará de nuevo, solo obtendrá los primeros 25 números de la lista que ya ha calculado.

Editar : se agregó un número único a cada procesador para evitar confusiones.

Answer 4

here puede encontrar un ejemplo muy relacionado, aunque no lo he revisado por completo, quizás sea de alguna ayuda.

No estoy exactamente seguro de los detalles de la implementación, pero sospecho que deberían estar en la línea de mi argumento a continuación.

Por favor, tome esto con una pizca de sal, esto puede ser imprecisa por su implementación, pero solo como una ayuda comprensiva.

Haskell no evaluará nada a menos que se lo obligue a hacerlo, lo que se conoce como Evaluación diferida, que es un concepto hermoso en sí mismo.

Así que supongamos que nos han pedido que hagamos una take 3 fibs Haskell almacena la lista de fibs como 0:1:another_list , ya que se nos ha pedido que take 3 podemos asumir que está almacenado como fibs = 0:1:x:another_list y (tail fibs) = 1:x:another_list y 0 : 1 : zipWith (+) fibs (tail fibs) será entonces 0 : 1 : (0+1) : (1+x) : (x+head another_list) ...

Por coincidencia de patrones, Haskell sabe que x = 0 + 1 lo que nos lleva a 0:1:1 .

Aunque estaré realmente interesado si alguien conoce algunos detalles de implementación adecuados. Puedo entender que las técnicas de Evaluación Lazy pueden ser bastante complicadas.

Espero que esto ayude a entender.

Exención de responsabilidad obligatoria nuevamente: Por favor, tome esto con un poco de sal, esto puede ser imprecisa por su implementación, pero solo como una ayuda comprensiva.