It is caused by foldr merge
having to look through all the lists to find the minimal element at the head of one of the lists. If foldr merge
is given a infinite list of finite lists, foldr merge
cannot ever compute the first element of the list - it keeps looking for the minimal element of the rest of the list of lists, before it can compare it to the first element of the first list - 2
. On the other hand, if foldr merge
is given a finite list of infinite lists, foldr merge
can determine the first element of the merged list, and moves on to the next one. That way you can produce an arbitrary number of elements in the first case, but not a single one in the second case.
Let's expand foldr merge []
:
foldr merge [] (xs0:xs1:xs2:...:[]) =
merge xs0 (merge xs1 (merge xs2 (merge xs3 ... [])))
Clearly, if (xs0:xs1:xs2:...:[])
is infinite, the "nested" calls to merge will form an infinite chain. But what about haskell being "lazy"? primes
is also defined in terms of itself, yet it produces output? Well, there is actually a rule of foldr
: it can produce output for infinite lists only if the function passed to foldr
is not strict in its second argument - i.e. sometimes it can produce output without having to evaluate the result of foldr
for the rest of the list.
The merge
pattern-matches the second argument - that alone can cause non-termination - and uses a strict function <=
, so merge
is strict in the second argument, and the infinite chain will have to evaluate the first element of every list before the top level merge
can produce any result.
Because merge
is strict, and because merge
is associative, you can - and should - use foldl'
instead of foldr
to merge the finite list of infinite lists.