Comportement de foldl contre foldr avec des listes infinies

Le code de la fonction myAny dans cette question utilise foldr. Il arrête de traiter une liste infinie lorsque le prédicat est satisfait.

Je l'ai réécrit en utilisant foldl:

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldl step False list
   where
      step acc item = p item || acc

(Notez que les arguments de la fonction step sont correctement inversés.)

Cependant, il n'arrête plus de traiter des listes infinies.

J'ai tenté de retracer l'exécution de la fonction comme dans la réponse d'Apocalisp :

myAny even [1..]
foldl step False [1..]
step (foldl step False [2..]) 1
even 1 || (foldl step False [2..])
False  || (foldl step False [2..])
foldl step False [2..]
step (foldl step False [3..]) 2
even 2 || (foldl step False [3..])
True   || (foldl step False [3..])
True

Cependant, ce n'est pas la façon dont la fonction se comporte. En quoi est-ce mal?

La folddifférence semble être une source fréquente de confusion, voici donc un aperçu plus général:

Envisagez de plier une liste de n valeurs [x1, x2, x3, x4 ... xn ]avec une fonction fet une valeur de départ z.

foldl est:

• Associatif gauche :f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Queue récursive : elle parcourt la liste, produisant ensuite la valeur
• Paresseux : rien n'est évalué tant que le résultat n'est pas nécessaire
• En arrière : foldl (flip (:)) []inverse une liste.

foldr est:

• Associatif droit :f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
• Récursif en argument : chaque itération s'applique fà la valeur suivante et au résultat du pliage du reste de la liste.
• Paresseux : rien n'est évalué tant que le résultat n'est pas nécessaire
• En avant : foldr (:) []renvoie une liste inchangée.

Il y a un point un peu subtile ici que les gens voyages parfois: Parce que foldlest en arrière chaque application de fest ajouté à l' extérieur du résultat; et comme il est paresseux , rien n'est évalué tant que le résultat n'est pas requis. Cela signifie que pour calculer n'importe quelle partie du résultat, Haskell effectue d'abord une itération dans toute la liste en construisant une expression d'applications de fonction imbriquées, puis évalue la fonction la plus externe , évaluant ses arguments si nécessaire. Si futilise toujours son premier argument, cela signifie que Haskell doit récurer jusqu'au terme le plus profond, puis travailler à rebours en calculant chaque application de f.

C'est évidemment loin de la récursivité de queue efficace que la plupart des programmeurs fonctionnels connaissent et aiment!

En fait, même si elle foldlest techniquement récursive en queue, parce que l'expression de résultat entière est construite avant d'évaluer quoi que ce soit, foldlpeut provoquer un débordement de pile!

D'un autre côté, considérez foldr. C'est aussi paresseux, mais comme il s'exécute vers l'avant , chaque application de fest ajoutée à l' intérieur du résultat. Ainsi, pour calculer le résultat, Haskell construit une application de fonction unique , dont le deuxième argument est le reste de la liste pliée. Si fest paresseux dans son deuxième argument - un constructeur de données, par exemple - le résultat sera paresseux de manière incrémentielle , chaque étape du repli étant calculée uniquement lorsqu'une partie du résultat qui en a besoin est évaluée.

Nous pouvons donc voir pourquoi foldrfonctionne parfois sur des listes infinies alors que ce foldln'est pas le cas: le premier peut convertir paresseusement une liste infinie en une autre structure de données infinie paresseuse, tandis que le second doit inspecter la liste entière pour générer n'importe quelle partie du résultat. D'un autre côté, foldravec une fonction qui a besoin des deux arguments immédiatement, comme (+), fonctionne (ou plutôt ne fonctionne pas) un peu comme la foldlconstruction d'une énorme expression avant de l'évaluer.

Les deux points importants à noter sont donc les suivants:

• foldr peut transformer une structure de données récursive paresseuse en une autre.
• Sinon, les plis paresseux planteront avec un débordement de pile sur des listes volumineuses ou infinies.

Vous avez peut-être remarqué qu'il semble que tout foldrpeut faire foldl, et plus encore. C'est vrai! En fait, foldl est presque inutile!

Mais que se passe-t-il si nous voulons produire un résultat non paresseux en repliant une grande liste (mais pas infinie)? Pour cela, nous voulons un pli strict , que les bibliothèques standard fournissent bien :

foldl' est:

• Associatif gauche :f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Queue récursive : elle parcourt la liste, produisant ensuite la valeur
• Strict : chaque application de fonction est évaluée en cours de route
• En arrière : foldl' (flip (:)) []inverse une liste.

Parce que foldl'c'est strict , pour calculer le résultat, Haskell évaluera f à chaque étape, au lieu de laisser l'argument de gauche accumuler une énorme expression non évaluée. Cela nous donne la récursion de queue habituelle et efficace que nous voulons! En d'autres termes:

• foldl' peut plier efficacement de grandes listes.
• foldl' se bloque dans une boucle infinie (ne provoque pas de débordement de pile) sur une liste infinie.

Le wiki Haskell a également une page traitant de cela .

myAny even [1..]
foldl step False [1..]
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]

etc.

Intuitivement, il foldlest toujours à «l'extérieur» ou à «gauche» afin qu'il s'agrandisse en premier. À l'infini.

Vous pouvez voir dans la documentation de Haskell ici que foldl est récursif et ne se terminera jamais s'il est passé une liste infinie, car il s'appelle sur le paramètre suivant avant de renvoyer une valeur ...

Je ne connais pas Haskell, mais dans Scheme, fold-rightil «agira» toujours d'abord sur le dernier élément d'une liste. Ainsi, cela ne fonctionnera pas pour une liste cyclique (qui est identique à une liste infinie).

Je ne sais pas si fold-rightpeut être écrit tail-recursive, mais pour toute liste cyclique, vous devriez obtenir un débordement de pile. fold-leftOTOH est normalement implémenté avec la récursivité de la queue, et restera simplement coincé dans une boucle infinie, si ce n'est pas le terminer tôt.