Why does this Haskell code not terminate?

Question

Why does the following Haskell code not terminate:

foldr (||) True $ repeat False -- never terminates

when something like this does:

foldr (||) False $ repeat True -- => True

To me, it's the second expression that looks to be in more trouble of not terminating. What's wrong with my view of Haskell's lazy evaluation?

Answer 1

I think your understanding of lazy is correct, but not for foldr. Let's look at its "specification"

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

Then look at your expression

foldr (||) True $ repeat False -- never terminates

As you see the True (z) which we are "looking for" to get || to terminate won't be reached until the whole list is consumed. And that won't happen as the list is infinite.

This should also explain for the actually terminating example.

Answer 2

The first expands to False || (False || (False || ...)), while the second expands to True || (True || (True || ...)). The second argument to foldr is a red herring - it appears in the innermost application of ||, not the outermost, so it can never actually be reached.