Simon Peyton-Jones <[EMAIL PROTECTED]> wrote:
> First, partition is defined in the List library:
>
> partition p xs = foldr select ([],[]) xs
> where
> selet x (ts,fs) | p x = (x:ts,fs)
> | otherwise = (ts,x:fs)
> Several people have pointed out that this is not equivalent
> to the "standard" definition
>
> partition p xs = (filter p xs, filter (not . p) xs)
>
> because the current H98 defn is strict in the spine of
> the argument list.
>
> I do not know how this change came about, but it seems entirely
> wrong to me. The "standard" (lazier) defn should be the one in the H98
> report.
>
> PROPOSAL: use the filter/filter defn of partition
Is the filter/filter definition semantically equivalent to:
partition p xs = foldr select ([],[]) xs
where
select x ~(ts,fs) | p x = (x:ts,fs)
| otherwise = (ts, x:fs)
(that is, the current definition in the Library report
with an extra twiddle added)?
Operationally, the 'foldr' version makes half as many
calls to 'p' as the 'filter/filter' version, so the former
may be preferable if the two are in fact semantically
equivalent.
--Joe English
[EMAIL PROTECTED]
