Plier à gauche et à droite sur une liste infinie

J’ai des problèmes avec le passage suivant de Learn You A Haskell (Grand livre imo, pas dissuader):

Une grande différence est que les plis droits fonctionnent sur des listes infinies, alors que les gauches ne le font pas! Pour le dire clairement, si vous prenez une liste infinie à un moment donné et que vous la pliez de la droite, vous finirez par atteindre le début de la liste. Cependant, si vous prenez une liste infinie à un moment donné et que vous essayez de la replier par la gauche, vous n’arriverez jamais à une fin!

Je ne comprends tout simplement pas Si vous prenez une liste infinie et essayez de la replier à partir de la droite, vous devrez commencer au point à l’infini, ce qui ne se produit tout simplement pas (si quelqu’un connaît une langue où vous pouvez faire cela, dites: p ). Au moins, vous devrez commencer par l’implémentation de Haskell car dans Haskell, foldr et foldl ne prennent pas un argument qui détermine où ils doivent commencer à se plier.

Je suis d’accord avec la citation ssi foldr et foldl ont pris des arguments qui ont déterminé où ils devraient commencer à se plier, car il est logique que si vous prenez une liste infinie et commencez à plier directement à partir d’un index défini Peu importe où vous commencez avec un pli gauche; vous plierez vers l’infini. Cependant, foldr et foldl ne prennent pas cet argument, et la citation n’a donc aucun sens. Dans Haskell, un pli gauche et un pli droit sur une liste infinie ne se terminent pas .

Est-ce que ma compréhension est correcte ou est-ce que je manque quelque chose?

La clé est la paresse. Si la fonction que vous utilisez pour plier la liste est ssortingcte, alors un pli gauche ou un pli droit ne se terminera pas, étant donné une liste infinie.

 Prelude> foldr (+) 0 [1..] ^CInterrupted. 

Cependant, si vous essayez de plier une fonction moins ssortingcte, vous pouvez obtenir un résultat final.

 Prelude> foldr (\xy -> x) 0 [1..] 1 

Vous pouvez même obtenir un résultat qui est une structure de données infinie, alors même s’il ne se termine pas, il est toujours capable de produire un résultat qui peut être consommé paresseusement.

 Prelude> take 10 $ foldr (:) [] [1..] [1,2,3,4,5,6,7,8,9,10] 

Cependant, cela ne fonctionnera pas avec foldl , car vous ne pourrez jamais évaluer l’appel de fonction le plus externe, paresseux ou non.

 Prelude> foldl (flip (:)) [] [1..] ^CInterrupted. Prelude> foldl (\xy -> y) 0 [1..] ^CInterrupted. 

Notez que la différence de clé entre un pli gauche et un pli droit n’est pas l’ordre dans lequel la liste est parcourue, qui est toujours de gauche à droite, mais plutôt comment les applications de fonction résultantes sont nestedes.

  • Avec foldr , ils sont nesteds “à l’intérieur”

     foldr fy (x:xs) = fx (foldr fy xs) 

    Ici, la première itération entraînera l’application la plus externe de f . Ainsi, f a la possibilité d’être paresseux pour que le second argument ne soit pas toujours évalué, ou il peut produire une partie de la structure de données sans forcer son second argument.

  • Avec foldl , ils sont nesteds sur “l’extérieur”

     foldl fy (x:xs) = foldl f (fyx) xs 

    Ici, nous ne pouvons rien évaluer avant d’avoir atteint l’application la plus externe de f , que nous n’atteindrons jamais dans le cas d’une liste infinie, que f soit ssortingct ou non.

La phrase clé est “à un moment donné”.

Si vous prenez une liste infinie à un moment donné et que vous la pliez de la droite, vous atteindrez éventuellement le début de la liste.

Donc, vous avez raison, vous ne pouvez probablement pas commencer par le “dernier” élément d’une liste infinie. Mais le sharepoint l’auteur est le suivant: supposez que vous pourriez. Il suffit de choisir un point loin de là (pour les ingénieurs, c’est assez proche de l’infini) et commencer à plier vers la gauche. Finalement, vous vous retrouvez au début de la liste. La même chose n’est pas vraie pour le pli gauche, si vous choisissez un point là-bas (et appelez-le assez proche du début de la liste), et que vous commencez à plier à droite, vous avez encore un chemin infini.

Donc, le tour est que parfois vous n’avez pas besoin d’aller à l’infini. Vous n’avez peut-être même pas besoin de vous y rendre. Mais vous ne savez peut-être pas à quelle distance vous devez aller au préalable, auquel cas les listes infinies sont très pratiques.

La simple illustration est foldr (:) [] [1..] . Réalisons le pli.

Rappelez-vous que foldr fz (x:xs) = fx (foldr fz xs) . Sur une liste infinie, peu importe ce que z est, je le garde juste comme z au lieu de [] qui encombre l’illustration

 foldr (:) z (1:[2..]) ==> (:) 1 (foldr (:) z [2..]) 1 : foldr (:) z (2:[3..]) ==> 1 : (:) 2 (foldr (:) z [3..]) 1 : 2 : foldr (:) z (3:[4..]) ==> 1 : 2 : (:) 3 (foldr (:) z [4..]) 1 : 2 : 3 : ( lazily evaluated thunk - foldr (:) z [4..] ) 

Voyez comme foldr , bien qu’étant théoriquement un repli de la droite , dans ce cas, fait apparaître des éléments individuels de la liste résultante à partir de la gauche ? Donc, si vous take 3 de cette liste, vous pouvez clairement voir qu’elle sera capable de produire [1,2,3] et n’a pas besoin d’évaluer le pli plus loin.

Rappelez-vous que dans Haskell, vous pouvez utiliser des listes infinies en raison de l’évaluation paresseuse. Donc, la head [1..] est juste 1 et la head $ map (+1) [1..] est 2, même si [1 ..] est infiniment long. Si vous n’obtenez pas cela, arrêtez-vous et jouez avec pendant un moment. Si vous obtenez cela, lisez la suite …

Je pense qu’une partie de votre confusion est que le foldl et le foldr commencent toujours d’un côté ou de l’autre, vous n’avez donc pas besoin de donner une longueur.

foldr a une définition très simple

  foldr _ z [] = z foldr fz (x:xs) = fx $ foldr fz xs 

pourquoi cela pourrait-il se terminer sur des listes infinies, essayez bien

  dumbFunc :: a -> b -> Ssortingng dumbFunc _ _ = "always returns the same ssortingng" testFold = foldr dumbFunc 0 [1..] 

nous passons ici à foldr a “” (puisque la valeur n’a pas d’importance) et à la liste infinie de nombres naturels. Est-ce que cela se termine? Oui.

La raison pour laquelle il se termine est que l’évaluation de Haskell équivaut à une réécriture par terme paresseuse.

Alors

  testFold = foldr dumbFunc "" [1..] 

devient (pour permettre la correspondance de motif)

  testFold = foldr dumbFunc "" (1:[2..]) 

qui est la même que (de notre définition de fold)

  testFold = dumbFunc 1 $ foldr dumbFunc "" [2..] 

maintenant, par la définition de dumbFunc nous pouvons conclure

  testFold = "always returns the same ssortingng" 

Ceci est plus intéressant lorsque nous avons des fonctions qui font quelque chose, mais sont parfois paresseuses. Par exemple

 foldr (||) False 

est utilisé pour trouver si une liste contient des éléments True . Nous pouvons l’utiliser pour définir la fonction d’ordre supérieur qui renvoie True si et seulement si la fonction passée est vraie pour certains éléments de la liste.

 any :: (a -> Bool) -> [a] -> Bool any f = (foldr (||) False) . (map f) 

La bonne chose à propos de l’évaluation paresseuse, c’est que cela s’arrêtera quand il rencontrera le premier élément e tel que fe == True

D’un autre côté, ce n’est pas vrai pour foldl . Pourquoi? Eh bien, un simple foldl ressemble à

 foldl fz [] = z foldl fz (x:xs) = foldl f (fzx) xs 

Maintenant, que se serait-il passé si nous avions essayé notre exemple ci-dessus

 testFold' = foldl dumbFunc "" [1..] testFold' = foldl dumbFunc "" (1:[2..]) 

cela devient maintenant:

 testFold' = foldl dumbFunc (dumbFunc "" 1) [2..] 

alors

 testFold' = foldl dumbFunc (dumbFunc (dumbFunc "" 1) 2) [3..] testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) [4..] testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) 4) [5..] 

Ainsi de suite. Nous ne pouvons jamais arriver nulle part, car Haskell évalue toujours la fonction la plus externe en premier (c’est-à-dire l’évaluation paresseuse en un mot).

Une conséquence intéressante de ceci est que vous pouvez implémenter foldl out of foldr mais pas l’inverse. Cela signifie que foldr est d’une certaine manière la plus fondamentale de toutes les fonctions de chaîne de caractères supérieures, puisque c’est celle que nous utilisons pour implémenter presque toutes les autres. Vous voudrez peut-être toujours utiliser un foldl parfois, car vous pouvez implémenter le foldl tail de manière récursive et en tirer un gain de performance.

Il y a une bonne explication sur le wiki Haskell . Il montre la réduction pas à pas avec différents types de fonctions de pliage et d’accumulateur.

Votre compréhension est correcte. Je me demande si l’auteur essaie de parler du système d’évaluation paresseux d’Haskell (dans lequel vous pouvez passer une liste infinie à diverses fonctions sans inclure le pli, et il évaluera seulement si beaucoup est nécessaire pour retourner la réponse). mais je suis d’accord avec vous pour dire que l’auteur ne fait pas un bon travail pour décrire quoi que ce soit dans ce paragraphe, et ce qu’il dit est faux.