Warum hat diesen Code Haskell Arbeit erfolgreich mit unendlichen Listen?

Question

ich einige Haskell-Code haben, dass nicht Arbeit korrekt auf eine unendliche Liste, aber ich verstehe nicht, Warum kann es so erfolgreich tun. (I geändert meinen ursprünglichen Code - die nicht unendliche Listen Griff hat - Online etwas von einem anderen Code zu übernehmen, und plötzlich sehe ich, dass es funktioniert, aber weiß nicht, warum).

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

Mein Verständnis von foldr ist, dass es in einer Schleife durch jedes Element in der Liste (und vielleicht das Verständnis ist unvollständig). Wenn ja, sollte es keine Rolle, wie die „Stufe“ Funktion formuliert wird ... soll der Code nicht in der Lage sein, Endlosschleifen zu behandeln.

Allerdings sind die folgenden Werke:

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

Bitte helfen Sie mir zu verstehen: warum ??

Answer 1

Lassen Sie uns ein wenig zu Spur in unseren Köpfen, wie Haskell Ihren Ausdruck auswerten. Substituierende für equals auf jeder Linie entspricht der Ausdruck recht schnell ausgewertet 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

Das funktioniert, weil acc als unevaluierten thunk (lazy evaluation) übergeben wird, sondern auch, weil die || Funktion ist streng in seinem ersten Argumente.

Also das endet:

True || and (repeat True)

Aber das bedeutet nicht:

and (repeat True) || True

Schauen Sie sich die Definition von || um zu sehen, warum dies der Fall ist:

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

Answer 2

  

Mein Verständnis von foldr ist, dass es   Schleife wird durch jedes Element in der   Liste (und vielleicht das Verständnis   ist unvollständig).

foldr (im Gegensatz zu foldl) nicht durch jedes Element der Liste Schleife. Es ist lehrreich zu sehen, wie foldr definiert ist.

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

Wenn ein Anruf an foldr ausgewertet wird, zwingt sie die Auswertung von einem Aufruf der Funktion f. Beachten Sie aber, wie der rekursive Aufruf zu foldr in ein Argument an die Funktion f eingebettet ist. Der rekursive Aufruf wird nicht ausgewertet, wenn f nicht zweites Argument nicht auswertet.

Answer 3

Der entscheidende Punkt hier ist, dass Haskell eine nicht-strenge Sprache. „Nicht-strikte“ bedeutet, dass es nicht-strenge Funktionen ermöglicht, was wiederum bedeutet, dass die Funktionsparameter nicht vollständig ausgewertet werden, bevor sie verwendet werden kann. Dies ermöglicht es offensichtlich für faule Auswertung, die „eine Technik der Verzögerung eine Berechnung, bis das Ergebnis ist erforderlich“ ist.

Starten von diesem Wiki-Artikel

Answer 4

Ich weiß nicht, Haskell, aber ich vermute, dass wegen der faulen Auswertung in Ihrem Fall, es funktioniert. Weil es Ihnen erlaubt, mit der Liste zu arbeiten unendlich lange, wenn Sie darauf zugreifen, wird es das Ergebnis berechnen, wie Sie es brauchen.

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