Comportement de foldl contre foldr avec des listes infinies

124

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?

titane
la source

Réponses:

231

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 .

CA McCann
la source
6
Je suis venu ici parce que je suis curieux de savoir pourquoi foldrest meilleur que foldldans Haskell , alors que l'inverse est vrai dans Erlang (que j'ai appris avant Haskell ). Depuis Erlang n'est pas paresseux et les fonctions ne sont pas curry , donc foldldans Erlang se comporte comme foldl'ci-dessus. C'est une excellente réponse! Bon travail et merci!
Siu Ching Pong -Asuka Kenji-
7
C'est surtout une excellente explication, mais je trouve la description de foldl«en arrière» et foldrde «en avant» problématique. Ceci est en partie dû au flipfait qu'il est appliqué (:)dans l'illustration de la raison pour laquelle le pli est en arrière. La réaction naturelle est, "bien sûr, c'est à l'envers: vous flippédalez la concaténation de liste!" Il est également étrange de voir ce qu'on appelle «en arrière» puisque foldls'applique fau premier élément de la liste en premier (le plus profond) dans une évaluation complète. C'est foldrque "marche en arrière", s'appliquant fd'abord au dernier élément.
Dave Abrahams
1
@DaveAbrahams: Entre juste foldlet foldret ignorer la rigueur et les optimisations, signifie d'abord "le plus extérieur", pas "le plus profond". C'est pourquoi foldrpeut traiter des listes infinies et foldlne peut pas - le pli de droite s'applique fd'abord au premier élément de la liste et au résultat (non évalué) du pliage de la queue, tandis que le pli de gauche doit parcourir toute la liste pour évaluer l'application la plus externe de f.
CA McCann
1
Je me demande simplement s'il existe un cas où foldl serait préféré à foldl ', pensez-vous qu'il y en a un?
kazuoua
1
@kazuoua où la paresse est essentielle, par exemple last xs = foldl (\a z-> z) undefined xs.
Will Ness
28
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.

Artelius
la source
10

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 ...

Romain
la source
0

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.

leppie
la source
3
C'est différent à Haskell à cause de la paresse.
Lifu Huang