When can I rely on Haskell to read a list lazily?

Question

Why do I get an infinite loop (<<loop>>) runtime error here?

file 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>>

Answer 1

You can fix to10plus by using an irrefutable match (i.e., a ~ prefix) in your definition of merge:

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

The reason for the difference in behavior between to10 and to10plus is that to10 can return the first element of the list without having to evaluate to10 xs and so without inspecting xs.

In contrast, before it can return anything, to10plus must successfully call merge with the arguments (x, 1) and to10plus xs. For this call to succeed, to10plus xs must be evaluated far enough to ensure it matches the pattern (as, bs) used in the definition of merge, but that evaluation requires inspecting elements of xs, which aren't available yet.

You could also have avoided the problem by defining to10plus a little differently:

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

Here, to10plus can provide the first element x of the first part of the tuple without trying to evaluate as, and so without trying to pattern match to10plus xs with (as,bs) in the where clause. A let clause would have done the same thing:

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

As @luqui points out, this is a difference in the timing for pattern matches made by let and where statements:

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

versus case statements / function definitions:

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

The let and where statements match patterns lazily, meaning that expr isn't matched to the pattern (a,b) until a or b are evaluated in the body. In contrast, for the case statement, expr is matched to (a,b) right away, before the body is even examined. And given the above definition for f, the argument to f will be matched to (a,b) as soon as the expression f expr is evaluated without waiting until a or b is needed in the function body. Here are some working examples to illustrate:

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

Adding ~ changes the behavior for case / function definitions so the matching takes place only when a or b are needed:

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"