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

Question

J'ai un code Haskell que ne fonctionne que sur une liste infinie, mais je ne comprends pas pourquoi il peut le faire avec succès. (J'ai modifié mon code d'origine - qui ne gérait pas des listes infinies - pour incorporer quelque chose d'un autre code en ligne, et tout à coup, je vois que cela 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

D'après ce que je sais, foldr va parcourir tous les éléments de la liste (et peut-être que cette compréhension est incomplète). Si tel est le cas, la procédure "étape" ne doit pas avoir d’importance. la fonction est libellée ... le code ne devrait pas être capable de gérer des boucles infinies.

Cependant, les travaux suivants:

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

Aidez-moi à comprendre: pourquoi ??

Answer 1

Faisons un peu dans notre tête comment Haskell évaluera votre expression. En substituant des égaux pour des égaux sur chaque ligne, l'expression passe assez rapidement à 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 que acc est transmis en tant que thunk non évalué (évaluation lazy), mais également parce que la fonction || est stricte dans son premier argument.

Donc cela se termine:

True || and (repeat True)

Mais cela ne veut pas:

and (repeat True) || True

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

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

Answer 2

  

D'après ce que je comprends, le foldr   passera en boucle tous les éléments du   liste (et peut-être cette compréhension   est incomplet).

foldr (contrairement à foldl ) n'a pas à parcourir en boucle chaque élément de la liste. Il est instructif de voir comment foldr est défini.

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

Lorsqu'un appel à foldr est évalué, il force l'évaluation d'un appel à la fonction f . Mais notez comment l'appel récursif à foldr est incorporé dans un argument de la fonction f . Cet appel récursif n'est pas évalué si f n'évalue pas 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 ne peuvent pas être entièrement évalués avant de pouvoir être utilisés. Ceci permet évidemment une évaluation paresseuse, qui est "une technique pour retarder un calcul jusqu'à ce que le résultat soit requis".

Commencez par cet article du wiki

Answer 4

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

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