Gauche et Droite se pliant sur une liste infinie

Question

J'ai des problèmes avec le passage suivant de Vous Apprendre Un Haskell (le Grand livre de l'omi, pas dissing):

Une grande différence est que le droit plis travail sur l'infinité des listes, alors que la gauche qui n'en ont pas! Pour le mettre clairement, si vous prenez une liste infinie à un certain point, et vous le pliez sur la droite, vous aurez finalement atteindre le début de la liste. Toutefois, si vous prenez une liste infinie en un point et de vous essayer à la fois il en place à partir de la gauche, vous ne serez jamais arriver à une fin!

Je n'ai tout simplement pas l'obtenir. Si vous prenez une liste infinie et d'essayer de la plier à partir de la droite, alors vous aurez à commencer à le point à l'infini, ce qui n'est tout simplement pas le cas (Si quelqu'un sait d'une langue où vous pouvez le faire, faire dire :p). Au moins, tu aurais du commencer par là, selon Haskell mise en Haskell foldr et foldl ne prenez pas un argument qui détermine où dans la liste, ils devraient commencer à plier.

Je suis d'accord avec la citation iff foldr et foldl a pris arguments que déterminé où dans la liste qu'ils devraient commencer à plier, parce que c'est logique que si vous prenez une liste infinie et commencer à plier droite à partir d'un index définies, il va finalement mettre fin, alors qu'il n'a pas d'importance où vous commencez avec un gauche pli, vous serez en pliant vers l'infini. Cependant foldr et foldl ne pas prendre cet argument, et donc la citation n'a pas de sens. En Haskell, à la fois à gauche pli et un droit rabattre sur une liste infinie de ne pas interrompre.

Est ma compréhension correcte ou ai-je raté quelque chose?

Answer 1

La clé ici, c'est la paresse. Si la fonction que vous utilisez pour le pliage de la liste est stricte, alors ni une gauche pli ni d'un droit pli se terminer, étant donné une liste infinie.

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

Toutefois, si vous essayez de plier un moins stricte fonction, vous pouvez obtenir une terminaison de résultat.

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

Vous pouvez même obtenir un résultat qui est infini structure de données, de sorte alors qu'il n'en sens pas la fin, c'est encore 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]

Toutefois, cela ne fonctionnera pas avec foldl, que vous ne serez jamais en mesure d'évaluer les ultrapériphériques de l'appel de fonction, paresseux ou pas.

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

Notez que la différence essentielle entre une gauche et une droite pli n'est pas l'ordre dans lequel la liste est traversée, qui est toujours de gauche à droite, mais plutôt la manière dont les applications de fonctions sont imbriquées.

• Avec foldr, elles sont imbriquées l'une sur "l'intérieur"

  foldr f y (x:xs) = f x (foldr f y xs)
  

  Ici, la première itération entraînera la ultrapériphériques de l'application de l' f. Ainsi, f a la possibilité d'être paresseux, de sorte que le deuxième argument n'est pas toujours évalué ou il peut produire une partie d'une structure de données sans forcer son deuxième argument.

• Avec foldl, ils sont imbriqués "de l'extérieur"

  foldl f y (x:xs) = foldl f (f x y) xs
  

  Ici, nous ne pouvons pas évaluer rien jusqu'à ce que nous avons atteint la limite extérieure de l'application de la f, ce qui nous permettra de ne jamais atteindre dans le cas d'une liste infinie, indépendamment de si f est stricte ou non.

Answer 2

La phrase clé est "à un certain point".

si vous prenez une liste infinie à un certain point, et vous vous pliez à partir de la droite, vous finirez par atteindre le début de la liste.

Oui tu as raison, on ne peut pas commencer par la "dernière" élément d'une liste infinie. Mais l'auteur de la question est la suivante: supposons que vous pourriez. Il suffit de choisir un point de waaay loin là-bas (pour les ingénieurs, c'est "assez proche" à l'infini) et commencer à plier vers la gauche. Vous arrivez finalement au début de la liste. Ce n'est pas vrai de la gauche fois, si vous choisissez un point de sa réputation (et de l'appeler "assez près" au début de la liste), et de commencer à plier rightwards, vous avez toujours une infinité de façons de le faire.

Donc, l'astuce est, parfois, vous n'avez pas besoin d'aller à l'infini. Vous ne pouvez pas même besoin d'aller à sa réputation. Mais vous ne pouvez pas savoir à quelle distance vous devez aller à l'avance, auquel cas infini listes sont assez pratique.

La simple illustration est - foldr (:) [] [1..]. Nous allons effectuer le pli.

Rappelons qu' foldr f z (x:xs) = f x (foldr f z xs). Sur une liste infinie, il ne fait pas d'importance ce z est donc, je suis juste le garder 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..] )

Voir comment foldr, malgré théoriquement être une fois de la droite, dans ce cas effectivement manivelles des éléments individuels de la liste de départ à la gauche? Donc, si vous take 3 à partir de cette liste, vous pouvez clairement voir qu'il va être en mesure de produire de l' [1,2,3] et n'a pas besoin d'évaluer à la fois plus loin.

Answer 3

Rappelez-vous en Haskell vous pouvez utiliser infini des listes en raison de l'évaluation différée. Donc, head [1..] est à seulement 1, et head $ map (+1) [1..] 2, même si " [1..] est infiniment longue. Si vous n'obtenez pas, arrêter de et de jouer avec elle pendant un certain temps. Si vous ne obtenez ce que, lire la suite...

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

foldr a une définition très simple

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

pourquoi cela peut-il mettre fin à l'infini les listes, bien essayer

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

ici nous passons en foldr " (puisque la valeur n'a pas d'importance) et la liste infinie des nombres naturels. Est-ce à mettre fin? Oui.

La raison pour laquelle il met fin est parce que Haskell évaluation est l'équivalent de paresseux de la réécriture de termes.

Donc

 testFold = foldr dumbFunc "" [1..]

devient (pour permettre la correspondance de modèle)

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

qui est la même que (à partir de notre définition de fois)

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

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

 testFold = "always returns the same string"

C'est plus intéressant quand nous avons des fonctions que faire quelque chose, mais sont parfois paresseux. Par exemple

foldr (||) False 

est utilisé pour savoir si une liste contient des True - éléments. Nous pouvons l'utiliser pour définir l'ordre supérieur fonctionn any qui renvoie True si et seulement si la fonction est vrai pour certains élément de la liste

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

La bonne chose à propos de l'évaluation différée, est que cela va s'arrêter quand il rencontre le premier élément e tels que f e == True

D'autre part, ce n'est pas vrai de foldl. Pourquoi? Bien une, très simple, foldl ressemble

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

Maintenant, ce qui serait arrivé si nous avons essayé de notre exemple ci-dessus

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

cela devient maintenant:

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

donc

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

et ainsi de suite et ainsi de suite. Nous ne pouvons jamais aller n'importe où, parce que Haskell évalue toujours la ultrapériphériques fonction première (c'est-évaluation différée dans un mot).

Un cool conséquence de cela est que vous pouvez mettre en oeuvre foldl de foldr mais pas vice-versa. Cela signifie que, dans certains profondément foldr est le plus fondamental de tous à l'ordre supérieur de la chaîne de fonctions, car il est celui que nous utilisons pour mettre en œuvre presque toutes les autres. Vous pourriez encore envie d'utiliser un foldl parfois, parce que vous pouvez mettre en oeuvre foldl de la queue de manière récursive, et d'obtenir un peu de gain de performance de que.

Answer 4

Votre compréhension est correcte. Je me demande si l'auteur essaie de parler du système d'évaluation paresseux de Haskell (dans lequel vous pouvez transmettre une liste infinie à diverses fonctions sans compter le pli, et il ne fera qu'évaluer le peu qu'il faudra faire pour obtenir la réponse). mais je conviens avec vous que l'auteur ne fait pas un bon travail en décrivant quoi que ce soit dans ce paragraphe, et ce qu'il dit est faux.