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.