confusion en ce qui concerne la paresse

Question

I ont une fonction

myLength = foldl (\ x _ -> x + 1) 0 

qui échoue avec débordement de pile avec une entrée à environ 10^6 éléments (MaLongueur [1..1000000] échoue). Je crois que cela est dû à l'accumulation de thunk depuis quand je remplace foldl avec foldl ', ça marche. Jusqu'ici tout va bien.

Mais maintenant j'ai une autre fonction d'inverser une liste:

myReverse = foldl (\ acc x -> x : acc) [] 

qui utilise la version paresseuse foldl (au lieu de foldl ')

Quand je fais myLength . myReverse $ [1..1000000]. Cette fois, cela fonctionne très bien. Je ne comprends pas pourquoi foldl fonctionne pour le cas plus tard et pas pour l'ancien?

Pour clarifient ici MaLongueur utilise foldl » tandis que myReverse utilise foldl

Answer 1

Voici ma meilleure estimation, bien que je ne suis pas un expert en Haskell (encore internals). Lors de la construction du thunk, Haskell alloue toutes les variables d'accumulateur intermédiaires sur le tas .

Lors de l'addition comme dans myLength, il faut utiliser la pile pour les variables intermédiaires. Voir this page. Extrait:

Le problème commence quand nous évaluons enfin z1000000:

Notez que z1000000 = z999999 + 1000000. Alors 1000000 est poussé sur la pile. Ensuite, z999999 est évalué.

Notez que z999999 = z999998 + 999999. Donc 999999 est poussé sur la pile. Alors z999998 est évalué:

Notez que z999998 = z999997 + 999998. Donc 999998 est poussé sur la pile. Ensuite z999997 est évaluée:

Cependant, lors de l'exécution de construction de la liste, voici ce que je pense arrive (c'est là que devinettes commence):

Lors de l'évaluation z1000000:

Notez que z1000000 = 1000000: z999999. Alors 1000000 est stocké à l'intérieur z1000000, avec un lien (pointeur) à z999999. Ensuite, z999999 est évalué.

Notez que z999999 = 999999: z999998. Ainsi 999999 est stocké à l'intérieur z999999, avec un lien vers z999998. Ensuite z999998 est évalué.

etc.

Notez que z999999, z999998 etc.Le changement d'une expression non encore évaluée en un seul élément de liste est une chose quotidienne de Haskell :)

Puisque z1000000, z999999, z999998, etc. sont tous sur le tas, ces opérations n'utilisent pas d'espace de pile. QED.