Editing Maintaining laziness (section)

=== Strict pattern matching in a recursion ===

Consider the <hask>partition</hask> function which sorts elements, that match a predicate, into one list and the non-matching elements into another list.
This function should also work on infinite lists, but the implementation shipped with GHC up to 6.2 [http://www.haskell.org/pipermail/libraries/2004-October/002645.html failed on infinite lists].
What happened?

The reason was that pattern matching was too strict.

Let's first consider the following correct implementation:
<haskell>
partition :: (a -> Bool) -> [a] -> ([a], [a])
partition p =
   foldr
      (\x ~(y,z) ->
         if p x
           then (x : y, z)
           else (y, x : z))
      ([],[])
</haskell>
The usage of <hask>foldr</hask> seems to be reserved for advanced programmers.
Formally <hask>foldr</hask> runs from the end to the start of the list.
However, how can this work if there is a list without an end?
That can be seen when applying the definition of <hask>foldr</hask>.
<haskell>
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ b [] = b
foldr f b (a:as) = f a (foldr f b as)
</haskell>
Now we expand this once for an infinite input list, we get
<haskell>
partition p (a:as) =
   (\ ~(y,z) -> if p a then (a:y, z) else (y, a:z)) (foldr ... ([],[]) as)
</haskell>
We see that the whether <hask>a</hask> is prepended to the first or the second list, does only depend on <hask>p a</hask>, and neither on <hask>y</hask> nor on <hask>z</hask>.
The laziness annotation <hask>~</hask> is crucial, since it tells, intuitively spoken,
that we can rely on the recursive call of <hask>foldr</hask> to return a pair and not <hask>undefined</hask>.
Omitting it, would require the evaluation of the whole input list before the first output element can be determined.
This fails for infinite lists and is inefficient for finite lists, and that was the bug in former implementations of <hask>partition</hask>.
Btw. by the expansion you also see, that it would not help to omit the tilde and apply the above 'force' trick to the 'if-then-else' expression.

However, there still remains a small laziness break:
There is an unnecessary decision between the pair constructor of the initial accumulator value <hask>([],[])</hask> and the pair constructors within the <hask>if</hask>.
This can only be avoided by applying a <hask>force</hask> function to the result of <hask>foldr</hask>:
<haskell>
partition :: (a -> Bool) -> [a] -> ([a], [a])
partition p =
   (\ ~(ys,zs) -> (ys,zs)) .
   foldr
      (\x ~(y,z) ->
         if p x
           then (x : y, z)
           else (y, x : z))
      ([],[])
</haskell>