Pourquoi ce code Haskell fonctionne-t-il avec succès avec des listes infinies?

Question

J'ai quelques Haskell code qui ne fonctionne correctement sur une liste infinie, mais je ne comprends pas pourquoi elle ne peut le faire avec succès. (J'ai modifié mon code d'origine -- qui n'a pas de poignée infini listes -- d'incorporer quelque chose à partir d'une autre ligne de code, et tout à coup je vois que ça fonctionne mais je ne sais pas pourquoi).

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

Ma compréhension de foldr, c'est qu'il passe en boucle sur chaque élément de la liste (et peut-être que la compréhension est incomplète). Si oui, il ne devrait pas d'importance comment les "étape" de la fonction est formulé ... le code doit être incapables de gérer les boucles infinies.

Cependant, les ouvrages suivants:

*Main Data.List> myAny even [1..]
True

S'il vous plaît aidez-moi à comprendre: pourquoi??

Answer 1

Nous allons faire un peu de trace dans nos têtes de comment Haskell permettra d'évaluer votre expression. La substitution est égal égaux sur chaque ligne, l'expression assez rapidement évalue à True:

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

Cela fonctionne parce qu' acc est passé comme une non évaluée thunk (lazy evaluation), mais aussi parce que l' || fonction est stricte dans son premier argument.

Alors, cela met fin à l':

True || and (repeat True)

Mais ce n'est pas:

and (repeat True) || True

Regardez la définition de || à voir pourquoi c'est le cas:

True  || _ =  True
False || x =  x

Answer 2

Ma compréhension de foldr, c'est qu'il passe en boucle sur chaque élément de l' liste (et peut-être que la compréhension de est incomplète).

foldr (contrairement à foldl) ne dispose pas d'une boucle sur chaque élément de la liste. Il est instructif d'examiner comment, en foldr est défini.

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

Lors d'un appel foldr est évalué, les forces de l'évaluation d'un appel à la fonction f. Mais notez comment l'appel récursif à l' foldr est intégré dans un argument à la fonction f. Que l'appel récursif n'est pas évalué si f ne permet pas d'évaluer son deuxième argument.

Answer 3

Le point clé ici est que Haskell est un langage non strict. "Non strict" signifie qu'il autorise les fonctions non strictes, ce qui signifie que les paramètres de fonction peuvent ne pas être entièrement évalués avant d'être utilisés. Cela permet évidemment une évaluation paresseuse, qui est "une technique pour retarder un calcul jusqu'à ce que le résultat soit requis".

Commencer à partir de cet article Wiki

Answer 4

Je ne connais pas Haskell, mais je soupçonne que dans votre cas, cela fonctionne à cause d'une évaluation paresseuse. Parce qu'il vous permet de travailler avec une liste infiniment longue, lorsque vous y accédez, il calcule le résultat selon vos besoins.

Voir http://en.wikipedia.org/wiki/Lazy_evaluation