Comprendre une liste définie de manière récursive (fibs en termes de zipWith)

Question

J'apprends Haskell, et je suis tombé sur le code suivant :

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

que j'ai un peu de mal à analyser, en termes de fonctionnement. C'est très soigné, je comprends que rien de plus n'est nécessaire, mais j'aimerais comprendre comment Haskell arrive à "remplir" les fibres lorsque j'écris :

take 50 fibs

Une aide ?

Merci !

Answer 1

Je vais vous expliquer un peu comment cela fonctionne en interne. Tout d'abord, vous devez savoir que Haskell utilise une chose appelée un "objet". jeté pour ses valeurs. Un thunk est fondamentalement une valeur qui n'a pas encore été calculée -- pensez-y comme une fonction à 0 argument. Quand Haskell le souhaite, il peut évaluer (ou partiellement évaluer) le thunk, le transformant en une valeur réelle. S'il ne fait que en partie évalue un thunk, alors la valeur résultante contiendra plus de thunks.

Par exemple, considérez l'expression :

(2 + 3, 4)

Dans un langage ordinaire, cette valeur serait stockée en mémoire sous la forme de (5, 4) mais en Haskell, il est stocké sous forme de (<thunk 2 + 3>, 4) . Si vous demandez le deuxième élément de ce tuple, il vous répondra "4", sans jamais additionner 2 et 3. Ce n'est que si vous demandez le premier élément de ce tuple qu'il évaluera le thunk et réalisera que c'est 5.

Avec les fibres, c'est un peu plus compliqué, parce que c'est récursif, mais on peut utiliser la même idée. Parce que fibs ne prend aucun argument, Haskell stockera de manière permanente tous les éléments de la liste qui ont été découverts -- c'est important.

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

Il permet de visualiser les connaissances actuelles de Haskell sur trois expressions : fibs , tail fibs y zipWith (+) fibs (tail fibs) . Nous supposerons que Haskell commence par connaître les éléments suivants :

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

Notez que la deuxième ligne est juste la première décalée vers la gauche, et que la troisième ligne est la somme des deux premières lignes.

Demandez take 2 fibs et vous obtiendrez [0, 1] . Haskell n'a pas besoin d'évaluer plus avant ce qui précède pour le savoir.

Demandez take 3 fibs et Haskell obtiendra le 0 et le 1, puis se rendra compte qu'il doit évaluer en partie le thunk. Afin d'évaluer pleinement zipWith (+) fibs (tail fibs) il doit additionner les deux premières lignes. Il ne peut pas le faire entièrement, mais il peut commencer pour additionner les deux premières lignes :

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

Notez que j'ai rempli le "1" dans la troisième ligne, et qu'il est apparu automatiquement dans la première et la deuxième ligne également, puisque les trois lignes partagent le même thunk (pensez-y comme un pointeur qui a été écrit). Et parce qu'il n'a pas fini d'évaluer, il a créé un nouveau thunk contenant le "1". reste de la liste, si cela s'avérait nécessaire.

Mais ce n'est pas nécessaire, car take 3 fibs est fait : [0, 1, 1] . Mais maintenant, disons que vous demandez take 50 fibs Haskell se souvient déjà des 0, 1 et 1. Mais il doit continuer. Il continue donc à additionner les deux premières lignes :

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>

Et ainsi de suite, jusqu'à ce qu'il ait rempli 48 colonnes de la troisième ligne, et donc calculé les 50 premiers chiffres. Haskell évalue juste ce dont il a besoin, et laisse le "reste" infini de la séquence sous forme d'objet thunk au cas où il en aurait besoin.

Notez que si vous demandez par la suite take 25 fibs Haskell ne l'évaluera pas à nouveau - il prendra simplement les 25 premiers chiffres de la liste qu'il a déjà calculée.

Modifier : Ajout d'un numéro unique à chaque thunk pour éviter toute confusion.

Answer 2

J'ai écrit un article sur ce sujet il y a quelque temps. Vous pouvez le trouver aquí .

Comme je l'ai mentionné, lisez le chapitre 14.2 du livre de Paul Hudak "The Haskell School of Expression", où il parle des flux récursifs, en utilisant l'exemple de Fibonacci.

Note : la queue d'une séquence est la séquence sans le premier élément.

|---+---+---+---+----+----+----+----+------------------------------------|
| 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)   |
|---+---+---+---+----+----+----+----+------------------------------------|

Ajoutez les deux colonnes : ajouter des fibres (queue des fibres) pour obtenir queue de la queue de la séquence de fibres

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

ajouter des fibres (fibres de queue) peut être écrit comme zipWith (+) fibres (fibres de queue)

Maintenant, il ne nous reste plus qu'à amorcer la génération en commençant par les 2 premiers nombres de Fibonacci pour obtenir la séquence complète de Fibonacci.

1:1 : zipWith (+) fibs (queue fibs)

Note : Cette définition récursive ne fonctionnera pas dans un langage typique qui fait une évaluation avide. Elle fonctionne en haskell car il fait une évaluation paresseuse. Donc, si vous demandez les 4 premiers nombres de Fibonacci, prendre 4 fibres haskell ne calcule que la quantité de séquence nécessaire.

Answer 3

Un exemple très proche peut être trouvé aquí Bien que je ne l'aie pas entièrement étudié, il pourrait vous être utile.

Je ne suis pas exactement sûr des détails de l'implémentation, mais je pense qu'ils devraient être sur les lignes de mon argument ci-dessous.

Prenez cela avec une pincée de sel, cela peut être inexact au niveau de la mise en œuvre, mais c'est juste une aide à la compréhension.

Haskell n'évalue rien à moins d'y être forcé, c'est ce qu'on appelle l'évaluation paresseuse, qui est un beau concept en soi.

Supposons qu'on nous demande seulement de faire une take 3 fibs Haskell stocke le fibs liste en tant que 0:1:another_list puisque nous avons été invités à take 3 nous pouvons tout aussi bien supposer qu'il est stocké comme fibs = 0:1:x:another_list y (tail fibs) = 1:x:another_list y 0 : 1 : zipWith (+) fibs (tail fibs) sera alors 0 : 1 : (0+1) : (1+x) : (x+head another_list) ...

Grâce au filtrage, Haskell sait que x = 0 + 1 Ce qui nous amène à 0:1:1 .

Je serais cependant très intéressé si quelqu'un connaissait des détails de mise en œuvre appropriés. Je peux comprendre que les techniques d'évaluation paresseuse peuvent être assez compliquées.

J'espère que cela vous aidera à comprendre.

Avis de non-responsabilité obligatoire : veuillez prendre ces informations avec une pincée de sel, elles sont peut-être inexactes sur le plan de la mise en œuvre, mais elles ne sont qu'une aide à la compréhension.

Answer 4

Jetons un coup d'œil à la définition de zipWith zipWith f (x:xs) (y:ys) = f x y : zipWith xs ys

Nos fibres sont : fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Para take 3 fibs en substituant la définition de zipWith y xs = tail (x:xs) on obtient 0 : 1 : (0+1) : zipWith (+) (tail fibs) (tail (tail fibs))

Para take 4 fibs En substituant une fois de plus, on obtient 0 : 1 : 1 : (1+1) : zipWith (+) (tail (tail fibs)) (tail (tail (tail fibs)))

et ainsi de suite.