Why is GHC sometimes refusing to be lazy?

Question

This goes into an infinite loop on tryhaskell.org. I am not sure why.

last $ filter (<100) $ [2..] >>= (\a -> if 0 == (length $ filter (== 0) $ map (mod a) $ [2..a-1]) then (return a) else [])

Answer 1

It's not refusing to be lazy, it's just there's no way for it to know that after you get all the primes < 100, there aren't any more.

What if the sequence looked like

1, 2, ... 99, 100, 101, 102, 5, 103, ...

In other words, last can't predict the future. Oh how I wish.

Answer 2

Let's take things apart, working from the inside out. Starting from this:

last $ filter (<100) $ [2..] >>= (\a -> if 0 == (length $ filter (== 0) $ map (mod a) $ [2..a-1]) then (return a) else [])

First consider map (mod a) [2..a-1]. This is just a transformation of a finite list, so no problems here, and we'll ignore it from here on, putting [..] in its place. Since we only care about termination, any finite list as good as another.

Same goes for filter (== 0) [...]. This can only make the list shorter, so we may end up with an empty list instead, but definitely finite. So ignore this as well. Now consider length [..]--we know the list is finite, so this will terminate just fine, giving some answer of 0 or more. We'll ignore the specific answer and put ? in its place. Still fine so far.

The lambda \a -> if 0 == ? then return a else [] is using return in the list monad, so this replaces a with either [a] or [], which is incidentally equivalent to Maybe, but that's another matter. Again, we know this much will work, so we ignore the details and use \a -> [a?].

The monadic bind [2..] >>= \a -> [a?] is more interesting. (>>=) here is concatMap, and the first argument is an infinite list. Mapping each element to a singleton list and concatenating obviously changes nothing, while mapping to the empty list removes an element, so this is essentially just filter. Things are not as simple here, however, because we're filtering an infinite list with no obvious assurance that anything will pass the filter. If you do filter (const False) [0..] the "result" will have no elements, but the computation will never finish; the [] in the output of filter comes from finding the end of the input list, and this has none, and since it will never find a first element, the result is just _|_.

So things are problematic already. The next part, filter (<100), makes things worse--we're filtering elements out of a strictly-increasing list, then filtering it based on being under some value, so by the above argument if we go past 100 in the result the computation will hang.

And the final insult is last--the list in question is still infinite, but will diverge at some point rather than produce more elements, so when we ask for the last element we can see that it will fail to terminate for multiple reasons!

What you want to do here is, first, apply your knowledge that the list is strictly increasing, and rather than filtering the list, simply take a prefix of it up to the desired point--e.g., takeWhile (<100) rather than filter (< 100). Note that this would still diverge if there are no elements greater than 100 in the result, since takeWhile won't know when to stop.