Évaluation paresseuse des termes dans une liste infinie en Haskell

Question

Je suis curieux de la performance d'exécution d'une liste infinie comme celle ci-dessous :

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

Cela créera une liste infinie de la séquence de Fibonacci.

Ma question est que si je fais ce qui suit :

takeWhile (<5) fibs

combien de fois évalue fibs chaque terme dans la liste ? Il semble que puisque takeWhile vérifie la fonction prédicat pour chaque élément dans la liste, la liste fibs évaluera chaque terme plusieurs fois. Les deux premiers termes sont donnés gratuitement. Lorsque takeWhile veut évaluer (<5) sur le 3ème élément, nous aurons :

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

Maintenant, une fois que takeWhile veut évaluer (<5) sur le 4ème élément : la nature récursive de fibs reconstruira la liste à nouveau comme suivant :

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

Il semblerait que le 3ème élément doit être calculé à nouveau lorsque nous voulons évaluer la valeur du 4ème élément. De plus, si le prédicat dans takeWhile est grand, cela indiquerait que la fonction fait plus de travail que nécessaire car elle évalue chaque élément précédent dans la liste plusieurs fois. Mon analyse est-elle correcte ici ou est-ce que Haskell fait une mise en cache pour éviter les évaluations multiples ici ?

Answer 1

Il s'agit d'une structure de données paresseuse auto-référentielle, où les parties "ultérieures" de la structure font référence aux parties antérieures par leur nom.

Initialement, la structure n'est qu'un calcul avec des pointeurs non évalués renvoyant vers elle-même. Lorsqu'elle est dépliée, des valeurs sont créées dans la structure. Les références ultérieures aux parties déjà calculées de la structure peuvent trouver la valeur déjà présente et les attendre. Pas besoin de réévaluer les éléments, et aucun travail supplémentaire à faire !

La structure en mémoire commence tout simplement par un pointeur non évalué. Une fois que nous regardons la première valeur, elle ressemble à ceci :

> take 2 fibs

(un pointeur vers une cellule `cons`, pointant vers '1', et une queue contenant le deuxième '1', et un pointeur vers une fonction qui contient des références de retour vers `fibs`, et la queue de `fibs`.

Évaluer une étape de plus développe la structure et déplace les références le long du chemin :

Et ainsi de suite, nous déplions la structure, chaque fois produisant une nouvelle queue non évaluée, qui est une fermeture contenant les références aux 1er et 2ème éléments de la dernière étape. Ce processus peut continuer indéfiniment :)

Et parce que nous faisons référence aux valeurs précédentes par leur nom, GHC les conserve joyeusement en mémoire pour nous, donc chaque élément n'est évalué qu'une seule fois.

Answer 2

Illustration :

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 ("Ajout de " ++ show x ++ "et" ++ show y
                                   ++ "pour obtenir " ++ show s)
                        s

Qui produit

*TraceFibs> fibs !! 5
Ajout de 0 et 1 pour obtenir 1
Ajout de 1 et 1 pour obtenir 2
Ajout de 1 et 2 pour obtenir 3
Ajout de 2 et 3 pour obtenir 5
5
*TraceFibs> fibs !! 5
5
*TraceFibs> fibs !! 6
Ajout de 3 et 5 pour obtenir 8
8
*TraceFibs> fibs !! 16
Ajout de 5 et 8 pour obtenir 13
Ajout de 8 et 13 pour obtenir 21
Ajout de 13 et 21 pour obtenir 34
Ajout de 21 et 34 pour obtenir 55
Ajout de 34 et 55 pour obtenir 89
Ajout de 55 et 89 pour obtenir 144
Ajout de 89 et 144 pour obtenir 233
Ajout de 144 et 233 pour obtenir 377
Ajout de 233 et 377 pour obtenir 610
Ajout de 377 et 610 pour obtenir 987
987
*TraceFibs>

Answer 3

Lorsqu'une valeur est évaluée en Haskell, elle reste évaluée, tant qu'elle est référencée par le même nom1.

Dans le code suivant, la liste l n'est évaluée qu'une seule fois (ce qui peut être évident) :

let l = [1..10]
print l
print l -- Aucun des éléments de la liste n'est recomputé

Même si quelque chose est partiellement évalué, cette partie reste évaluée :

let l = [1..10]
print $ take 5 l -- Évalue l en [1, 2, 3, 4, 5, _]
print l          -- De 1 à 5 est déjà évalué; évalue uniquement 6..10

---

Dans votre exemple, lorsqu'un élément de la liste fibs est évalué, il reste évalué. Comme les arguments de zipWith font référence à la liste fibs réelle, cela signifie que l'expression de zipping utilisera la liste fibs partiellement calculée lorsque les prochains éléments de la liste sont calculés. Cela signifie qu'aucun élément n'est évalué deux fois.

1Ce n'est bien sûr pas strictement nécessaire selon la sémantique du langage, mais en pratique c'est toujours le cas.

Answer 4

Pensez-y de cette façon. La variable fib est un pointeur vers une valeur paresseuse. (Vous pouvez penser à une valeur paresseuse en dessous comme une structure de données comme (pas de syntaxe réelle) Lazy a = IORef (Non Évalué (IO a) | Évalué a); c'est-à-dire qu'il commence comme non évalué avec un thunk; puis quand il est évalué, il "change" en quelque chose qui se souvient de la valeur.) Parce que l'expression récursive utilise la variable fib, elles ont un pointeur vers la même valeur paresseuse (elles "partagent" la structure de données). La première fois que quelqu'un évalue fib, il exécute le thunk pour obtenir la valeur et cette valeur est mémorisée. Et parce que l'expression récursive pointe vers la même structure de données paresseuse, quand elles l'évaluent, elles verront déjà la valeur évaluée. En traversant la "liste infinie" paresseuse, il n'y aura qu'une seule "liste partielle" en mémoire; zipWith aura deux pointeurs vers des "listes" qui ne sont simplement que des pointeurs vers les membres précédents de la même "liste", en raison du fait qu'il a commencé avec des pointeurs vers la même liste.

Remarquez que ce n'est pas vraiment de la "mémoïsation"; c'est juste une conséquence de se référer à la même variable. Il n'y a généralement pas de "mémoïsation" des résultats de fonction (ce qui suivra sera inefficace):

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