S.D.Mechveliani wrote:
| partition1 p xs = (filter p xs, filter (not . p) xs)
:
| and optimized implementations, like, say,
|
| partition2 p = foldr (\x (ys, zs) -> if p x then (x:ys,zs) else (ys,x:zs))
| ([],[])
|
| may be not equivalent.
Why is this an optimized implementation?
I'm asking because:
1. It is clearly not, but
2. the original poster (Joe Fasel) seemed to assume that there
was some standard transformation to get form the first to the second
(he called it currying).
Still, Sergey's original question is still insteresting ("how much
more/less lazy than the specifications can implementations be?").
I think the answer should be "no more/no less", but there have been other
examples of functions which could have been more lazy than the Haskell
report says (I recall "transpose").
Regards,
Koen.
PS. By the way, several people have already pointed out that, if the
example is rewritten as:
partition2 p = foldr (\x ~(ys, zs) -> if p x then (x:ys,zs) else (ys,x:zs))
([],[])
(one twiddle more), the implementations are in fact equivalent.
--
Koen Claessen http://www.cs.chalmers.se/~koen
phone:+46-31-772 5424 e-mail:[EMAIL PROTECTED]
-----------------------------------------------------
Chalmers University of Technology, Gothenburg, Sweden
