Wann kann ich mich darauf verlassen, dass Haskell eine Liste träge liest?

8

Warum erhalte ich hier einen Endlosschleifen ( <<loop>>) - Laufzeitfehler?

Datei feedback.hs:

plus1 :: [Int]->[Int] -- add 1 to input stream
plus1 [] = []
plus1 (x:xs) = (x+1): plus1 xs

to10 :: [Int] -> [Int] -- stop the input stream when it gets to 10
to10 (x:xs) | x < 10 = x : to10 xs
            | otherwise = []

to10plus :: [Int] -> ([Int], Int) -- like to10 but also return the count
to10plus (x:xs) | x < 10 = (x, 1) `merge` (to10plus xs)
            | otherwise = ([], 0)
  where merge (a, b) (as, bs) = (a:as, b+bs)

main = do
  let out = plus1 $ 1: to10 out
  putStrLn $ show out -- gives [2,3,4,5,6,7,8,9,10]


  let out = plus1 $ 1: out2
      out2 = to10 out
  putStrLn $ show out -- same as above

  let out = plus1 $ 1: out2
      (out2, count) = to10plus out
  putStrLn $ show (out, count) -- expect ([2,3,4,5,6,7,8,9,10], 8) 
                               -- but get runtime error: <<loop>>
$ ghc feedback.hs 
[1 of 1] Compiling Main             ( feedback.hs, feedback.o )
Linking feedback ...
$ ./feedback
[2,3,4,5,6,7,8,9,10]
[2,3,4,5,6,7,8,9,10]
feedback: <<loop>>
Daniel Patru
quelle

Antworten:

7

Sie können das Problem beheben, to10plusindem Sie eine unwiderlegbare Übereinstimmung (dh ein ~Präfix) in Ihrer Definition von merge:

merge (a, b) ~(as, bs) = (a:as, b+bs)

Der Grund für den Unterschied im Verhalten zwischen to10und to10plusist, dass to10das erste Element der Liste zurückgegeben werden kann, ohne dass eine Bewertung erforderlich ist, to10 xsund dies ohne Inspektion xs.

Im Gegensatz dazu muss, bevor es etwas zurückgeben kann, to10pluserfolgreich mergemit den Argumenten (x, 1)und aufgerufen werden to10plus xs. Damit dieser Aufruf erfolgreich ist, to10plus xsmuss er weit genug bewertet werden, um sicherzustellen, dass er mit dem (as, bs)in der Definition von verwendeten Muster übereinstimmt. Für diese mergeBewertung müssen jedoch Elemente überprüft werden xs, die noch nicht verfügbar sind.

Sie hätten das Problem auch vermeiden können, indem Sie es to10plusetwas anders definiert hätten:

to10plus (x:xs) | x < 10 = (x:as,1+bs)
                | otherwise = ([], 0)
  where (as,bs) = to10plus xs

Hier to10plusbieten kann das erste Element xdes ersten Teils des Tupels ohne zu bewerten zu versuchen as, und so ohne Mustererkennung versucht , to10plus xsmit (as,bs)der whereKlausel. Eine letKlausel hätte dasselbe getan:

to10plus (x:xs) | x < 10 = let (as,bs) = to10plus xs in (x:as,1+bs)
                | otherwise = ([], 0)

Wie @luqui hervorhebt, ist dies ein Unterschied im Timing für Musterübereinstimmungen von letund whereAnweisungen:

let (a,b) = expr in body
-- OR --
body where (a,b) = expr

versus caseAnweisungen / Funktionsdefinitionen:

case expr of (a,b) -> body
-- OR --
f (a,b) = body  -- AND THEN EVALUATING: -- f expr

Die letund where-Anweisungen stimmen träge mit Mustern überein, was bedeutet, dass sie exprerst dann mit dem Muster übereinstimmen, (a,b)wenn sie in der aoder bausgewertet werden body. Im Gegensatz dazu wird für die caseAussage sofort exprabgestimmt (a,b), bevor die bodyüberhaupt geprüft wird. Und die obige Definition für gegeben f, das Argument fwird angepasst werden (a,b), sobald der Ausdruck , f exprohne zu warten , bis bewertet wird aoder bin der Funktion benötigt body. Hier einige Arbeitsbeispiele zur Veranschaulichung:

ex1 = let (a,b) = undefined in print "okay"
ex2 = print "also okay" where (a,b) = undefined
ex3 = case undefined of (a,b) -> print "not okay"
ex4 = f undefined
f (a,b) = print "also not okay"

main = do
  ex1   -- works
  ex2   -- works
  ex3   -- fails
  ex4   -- fails

Durch Hinzufügen ~wird das Verhalten für case/ Funktionsdefinitionen geändert, sodass der Abgleich nur dann erfolgt, wenn aoder wenn Folgendes berforderlich ist:

ex5 = case undefined of ~(a,b) -> print "works fine"
ex6 = g undefined
g ~(a,b) = print "also works fine"

ex7 = case undefined of ~(a,b) -> print $ "But trying " ++ show (a+b) ++ " would fail"
KA Buhr
quelle
3
Der Hauptunterschied ist alles andere als selbstverständlich und sollte wahrscheinlich angegeben werden: Muster stimmen überein letund wheresind immer faul, aber Muster für Argumente sind standardmäßig streng, es sei denn, sie werden faul verwendet ~.
Luqui
Danke KA Buhr und Luqui!
Daniel Patru