Why does Sieve of Eratosthenes need extra helper function for merging infinite lists?

Question

I'm working with the Sieve of Eratosthenes code from Literate Programming (http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29), modified slightly to include edge cases on merge and diff:

primesInit = [2,3,5,7,11,13]
primes = primesInit ++ [i | i <- diff [15,17..] nonprimes]

nonprimes = foldr1 f . map g $ tail primes
        where g p = [n * p | n <- [p,p+2..]]
              f (x:xt) ys = x : (merge xt ys)

merge :: (Ord a) => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xs@(x:xt) ys@(y:yt)
    | x < y  = x : merge xt ys
    | x == y = x : merge xt yt
    | x > y  = y : merge xs yt

diff :: (Ord a) => [a] -> [a] -> [a]
diff [] ys = []
diff xs [] = xs
diff xs@(x:xt) ys@(y:yt)
    | x < y  = x : diff xt ys
    | x == y = diff xt yt
    | x > y  = diff xs yt

Both merge and diff on their own are lazy. So is nonprimes and primes. But if we change the definition of primes to remove f, as in:

nonprimes = foldr1 merge . map g $ tail primes
        where g p = [n * p | n <- [p,p+2..]]

Now nonprimes isn't lazy. I've also recreated this with take 20 $ foldr1 merge [[i*n | n <- [3,7..]] | i <- [5,9..]] (GHCI runs out of memory and exits).

Based on http://www.haskell.org/haskellwiki/Performance/Laziness , one easy source of non-laziness is recursing before returning a data constructor. But merge doesn't have this problem; it returns a cons-cell that contains the recursive call as the second item. Nor should the use of foldr be a culprit here by itself (It's foldl that can't do infinite lists).

So, why does merge need to be separated from foldr1 by f, which essentially does the first call to merge manually? All f does is return a cons cell that contains the call to merge as the second item, right?

NOTE: Someone else on Stack Overflow was working with similar code and ran into the same problem I did, but they accepted an answer that looked to me like basically different code. I'm asking why, not how, as it seems that laziness is somewhat important in Haskell.

Answer 1

Let's compare those two functions again:

merge [] ys = ys
merge xs [] = xs
merge xs@(x:xt) ys@(y:yt)
    | x < y  = x : merge xt ys
    | x == y = x : merge xt yt
    | x > y  = y : merge xs yt

and

f (x:xt) ys = x : (merge xt ys)

Let's ignore the semantic differences between the two, though they are significant - f is a lot more restricted as far as when it's valid to call. Instead, lets look at only the strictness properties.

Pattern matches in multiple equations are checked top-down. Multiple pattern matches within a single equation are checked left-to-right. So the first thing merge does is force the constructor of its first argument, in order to determine if the first equation matches. If the first equation doesn't match, it forces the constructor of the second argument, in order to determine if the second equation matches. Only if neither equation matches does it move to the third case. The compiler is smart enough to know it's already forced both arguments at this point, so it doesn't do it again - but those pattern matches would require the arguments to be forced if it hadn't already been.

But the important thing here is that the process of figuring out which equation matches causes both arguments to be forced before any constructor is produced.

Now, contrast that with f. In the definition of f, the only pattern-matching is on the first argument. As such, f is somewhat less strict than merge. It produces a constructor before examining its second argument.

And it turns out that if you closely examine the behavior of foldr, it works on infinite lists precisely when the function passed to it doesn't (always) examine its second argument before producing a constructor.

The parenthetical "always" there is interesting. One of my favorite examples of using foldr and laziness together is:

dropRWhile :: (a -> Bool) -> [a] -> [a]
dropRWhile p = foldr (\x xs -> if p x && null xs then [] else x:xs) []

This is a maximally-lazy function that works like dropWhile, except from the back (right) of the list. If the current element doesn't match the predicate, it's returned immediately. If it does match the predicate, it looks ahead until it finds something that either doesn't match, or the end of the list. This will be productive on infinite lists, so long as it eventually finds an element that doesn't match the predicate. And that is the source of the "always" parenthetical up above - a function that usually doesn't examine its second argument before producing a constructor still allows foldr to usually work on infinite lists.

Answer 2

To determine the first element of its output, merge needs to evaluate both arguments enough to determine if they are empty lists or not. Without that information it can't be determined which case of the function definition applies.

In combination with foldr1 it becomes a problem that merge tries to evaluate its second argument. nonprimes in an expression of this form:

foldr1 merge [a,b,c,...]

To evaluate this, first `foldr1 is expanded:

merge a (foldr1 merge [b,c,...])

To now evaluate merge, the cases of its function definition are checked. First a is evaluated, and it turns out to not be an empty list. So the first case of merge doesn't apply. Next, the second parameter of merge needs to be evaluated to see if it is an empty list and if the second case of the definition of merge applies. This second parameter is foldr1 merge [b,c,...].

But to evaluate this we are in the same situation as before with foldr1 merge [a,b,c,...], and we just the same end up with merge b (foldr1 merge [c,...]), where merge again needs to evaluate it's second parameter to check if it's an empty list.

And so on. Each evaluation of merge requires another evaluation of merge first, which ends up in infinite recursion.

With f that problem is avoided, since it doesn't need to look at its second parameter for the top level evaluation. foldr1 f [a,b,c...] is f a (foldr1 f [b,c,...]) which evaluates to a non-empty list a0 : merge a' (foldr1 f [b,c,...]). So foldr1 f ... never is an empty list. This can be determined without any infinite recursion.

Now also the evaluation of merge a' (foldr1 f [b,c,...]) isn't a problem, since the second parameter evaluates to some b0 : ..., which is all merge needs to know to start producing a result.