Evaluation paresseuse des termes dans une liste infinie en Haskell

Question

Je suis curieux de connaître les performances d'exécution d'une liste infinie comme celui ci-dessous:

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

Cela va créer une liste infinie de la suite de fibonacci.

Ma question est que si je ne les suivants:

takeWhile (<5) fibs

combien de fois n' fibs évaluer chaque terme de la liste? Il semble que depuis takeWhile vérifie la fonction de prédicat pour chaque élément dans la liste, l' fibs liste permettra d'évaluer chaque terme à de multiples reprises. L' les 2 premiers termes sont donnés gratuitement. Lors de l' takeWhile veut évaluer (<5) sur le 3ème élément, nous aurons:

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

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

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 voulez évaluer la valeur de la 4ème élément. En outre, si l' prédicat en takeWhile est grand, il peut indiquer que la fonction est faire plus de travail est nécessaire, car il est de l'évaluation de chaque précédant élément dans la liste plusieurs fois. Mon analyse est ici correct ou est Haskell faire quelques mise en cache pour éviter que plusieurs évaluations ici?

Answer 1

C'est une auto-référentielle, paresseux structure de données, où "plus tard" parties de la structure consulter parties précédentes par son nom.

D'abord, la structure est juste un calcul avec des pointeurs non évaluée à lui-même. Comme il est déplié, les valeurs sont créés dans la structure. Références ultérieures déjà calculé les parties de la structure sont en mesure de trouver la valeur déjà là en attente pour eux. Pas besoin de re-évaluer les morceaux, et pas de travail supplémentaire à faire!

La structure en mémoire commence comme un pointeur non évaluée. Une fois que nous regardons la première valeur, il ressemble à ceci:

> take 2 fibs

(un pointeur vers un des inconvénients de la cellule, pointant vers '1', et la queue de la tenue de la deuxième '1', et un pointeur vers une fonction qui détient des références de bobards, et la queue de bobards.

L'évaluation d'une étape de plus se développe la structure, les diapositives et les références:

Et donc, nous allons de déplier la structure, à chaque fois ce qui donne un nouveau non évaluée queue, qui est une fermeture holding références retour à la 1ère et de la 2ème éléments de la dernière étape. Ce processus peut se poursuivre à l'infini :)

Et parce que nous sommes se référant à des valeurs antérieures par nom, GHC heureusement conserve en mémoire, pour nous, de sorte que chaque élément 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 ("Adding " ++ show x ++ " and " ++ show y
                                   ++ "to obtain " ++ show s)
                        s
 

Qui produit

 *TraceFibs> fibs !! 5
Adding 0 and 1 to obtain 1
Adding 1 and 1 to obtain 2
Adding 1 and 2 to obtain 3
Adding 2 and 3 to obtain 5
5
*TraceFibs> fibs !! 5
5
*TraceFibs> fibs !! 6
Adding 3 and 5 to obtain 8
8
*TraceFibs> fibs !! 16
Adding 5 and 8 to obtain 13
Adding 8 and 13 to obtain 21
Adding 13 and 21 to obtain 34
Adding 21 and 34 to obtain 55
Adding 34 and 55 to obtain 89
Adding 55 and 89 to obtain 144
Adding 89 and 144 to obtain 233
Adding 144 and 233 to obtain 377
Adding 233 and 377 to obtain 610
Adding 377 and 610 to obtain 987
987
*TraceFibs>
 

Answer 3

Quand quelque chose est évaluée en Haskell, il reste évalué, tant qu'il est référencé par le même nom¹.

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 -- None of the elements of the list are recomputed

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

let l = [1..10]
print $ take 5 l -- Evaluates l to [1, 2, 3, 4, 5, _]
print l          -- 1 to 5 is already evaluated; only evaluates 6..10

---

Dans votre exemple, lorsqu'un élément de l' fibs liste est évalué, il reste à évaluer. Depuis la arguments au zipWith référence de la réelle fibs liste, cela signifie que la compression de l'expression utilisera le déjà partiellement calculées fibs liste lors du calcul de la prochaine éléments dans la liste. Cela signifie qu'aucun élément est évalué deux fois.

¹bien sûr Ce n'est pas strictement nécessaire par le langage, la sémantique, mais dans la pratique c'est toujours le cas.

Answer 4

Pensez-y de cette façon. La variable fib est un pointeur vers un paresseux valeur. (Vous pouvez penser à un paresseux de la valeur au-dessous comme une structure de données comme (pas de réel syntaxe) Lazy a = IORef (Unevaluated (IO a) | Evaluated a); c'est à dire qu'il commence comme non évaluée avec un thunk; puis, quand il est évalué de "changements" à quelque chose qui se souvient de la valeur.) Parce que le récursive expression utilise la variable fib, ils ont un pointeur vers la même paresseux valeur (ils "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 le récursive expression de points de la même paresseux structure de données, lors de l'évaluation de cela, ils vont voir la valeur évaluée déjà. Comme ils traversent les paresseux "liste infinie", il n'y aura qu'une "liste partielle" dans la mémoire; zipWith aura deux pointeurs vers des "listes", qui sont simplement des pointeurs vers des anciens membres de la même "liste", en raison du fait qu'il a commencé avec des pointeurs de la même liste.

Notez que ce n'est pas vraiment "memoizing"; c'est simplement une conséquence de se référer à la même variable. Il n'y a généralement pas de "memoizing" des résultats de la fonction (la suite sera inefficace):

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