foldl contre le comportement des foldr avec des listes infinies

Question

Le code de la fonction myAny dans cette question des utilisations fOLDR. Il arrête le traitement d'une liste infinie lorsque le prédicat est satisfait.

Je récrit à l'aide 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 sont pas inversées correctement.)

Cependant, il ne cesse de traiter des listes infinies.

I essayé de tracer l'exécution de la fonction que dans réponse de 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 les fonctions se comporte. Comment est-ce mal?

Answer 1

Comment folds diffèrent semble être une source fréquente de confusion, voici donc une vue d'ensemble plus générale:

Considérons le pliage d'une liste de n valeurs [x1, x2, x3, x4 ... xn ] avec une fonction f et semences z.

foldl est:

• associative gauche : f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Tail récursive : Elle parcourt la liste, la production de la valeur après
• Lazy : Rien n'est évalué jusqu'à ce que le résultat est nécessaire
• Backwards :. foldl (flip (:)) [] inverse une liste

foldr est:

• Droit associatif : f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
• récursif dans un argument :. Chaque itération applique f à la prochaine valeur et le résultat de plier le reste de la liste
• Lazy : Rien n'est évalué jusqu'à ce que le résultat est nécessaire
• Attaquants :. foldr (:) [] retourne une liste inchangée

Il y a un point un peu subtile ici que les gens voyages parfois: Parce que foldl est arrière chaque application de f est ajouté au à l'extérieur du résultat; et parce qu'il est paresseux , rien est évalué jusqu'à ce que le résultat est nécessaire. Cela signifie que pour calculer une partie du résultat, Haskell première itère par la ensemble construire une expression d'applications de fonctions imbriquées, évalue alors la externe fonction, évaluer ses arguments nécessaire. Si f utilise toujours son premier argument, ce moyen Haskell doit récursifs tout le chemin jusqu'au terme le plus intérieur, puis travail de calcul en arrière chaque application de f.

Ceci est évidemment loin de la queue-récursion efficace les programmeurs les plus fonctionnels connaissent et aiment!

En fait, même si foldl est techniquement récursive, parce que l'expression entière de résultat est construit avant d'évaluer quoi que ce soit, foldl peut provoquer un débordement de pile!

D'autre part, envisager foldr. Il est aussi paresseux, mais parce qu'il court avant , chaque application de f est ajouté à la dans du résultat. Donc, pour calculer le résultat, Haskell construit un application unique de fonction , le second argument qui est le reste de la liste pliée. Si f est paresseux dans son second argument - un constructeur de données, par exemple - le résultat sera progressivement paresseux , à chaque étape du pli calculée que si une partie du résultat qui en a besoin est évaluée.

On peut donc voir pourquoi foldr fonctionne parfois sur des listes infinies quand foldl n'a pas: L'ancien peut paresseusement convertir une liste infinie dans une autre structure de données infinie paresseuse, alors que celui-ci doit inspecter toute la liste pour générer une partie du résultat . D'autre part, foldr avec une fonction qui a besoin des deux arguments immédiatement, tels que (+), œuvres (ou plutôt, ne fonctionne pas) un peu comme foldl, la construction d'une grande expression avant de l'évaluer.

Ainsi, les deux points importants à noter sont les suivants:

• foldr peut transformer une structure de données récursive paresseuse dans un autre.
• Dans le cas contraire, les plis paresseux se bloque avec un débordement de pile sur les listes grandes ou infinies.

Vous avez sans doute remarqué que cela ressemble à foldr peut tout faire foldl peut, et plus encore. C'est vrai! En fait, foldl est presque inutile!

Mais si nous voulons produire un résultat non paresseux en pliant sur une grande (mais pas infinie) la liste? Pour cela, nous voulons un fold stricte , which les bibliothèques standard fournir pensivement :

foldl' est:

• associative gauche : f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Tail récursive : Elle parcourt la liste, la production de la valeur après
• Strict : Chaque application de fonction est évaluée sur le chemin
• Backwards :. foldl' (flip (:)) [] inverse une liste

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

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

Le wiki Haskell a une page en discuter , ainsi.

Answer 2

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, foldl est toujours « à l'extérieur » ou sur la « gauche » de sorte qu'il s'élargi d'abord. Ad infinitum.

Answer 3

Vous pouvez voir dans la documentation Haskell ici foldl est récursive et ne finira jamais si elle est adoptée une liste infinie, puisqu'elle se demande au paramètre suivant avant de retourner une valeur ...

Answer 4

Je ne sais pas Haskell, mais dans le schéma, fold-right toujours le fera « agir » sur le dernier élément d'une première liste. est donc ne fonctionnera pas pour la liste cyclique (qui est identique à un infini).

Je ne sais pas si fold-right peut être écrit récursif queue, mais pour une liste cyclique vous devriez obtenir un débordement de pile. fold-left OTOH est normalement mis en œuvre avec récursion de queue, et tout simplement se retrouver coincé dans une boucle infinie, sinon terminer tôt.