Hi.
I'm not sure which forum this belongs in, because I was only in a
position to test it with Hugs 98 (Nov 99), which defines partition the
same way as GHC does.
Anyway...
Simon Peyton-Jones writes:
> [...]
>
> I'm not sure how partition could be made much more efficient
> without also making it stricter.
>
> In general, though, we have not devoted a great deal of effort
> to performance-tuning the GHC prelude. If anyone finds a definition
> of a prelude function that out-performs the one that comes with
> GHC, please send it and we'll plug it in.
>
> Simon
It appears that partition can be made lazier, at the expense of an
increase in the number of cells used.
Method:
import List(partition)
partition' :: (a -> Bool) -> [a] -> ([a], [a])
partition' p [] = ([], [])
partition' p (x:xs) = if p x then (x:ts, fs) else (ts, x:fs)
where (ts, fs) = partition' p xs
test n = sum $ snd $ partition (==1) [0..n]
test' n = sum $ snd $ partition' (==1) [0..n]
lazinessTest = head $ fst $ partition (==1) [0..]
lazinessTest' = head $ fst $ partition' (==1) [0..]
Results:
Main> test 99
4949
(2547 reductions, 4030 cells)
Main> test' 99
4949
(2538 reductions, 4453 cells)
Main> test 999
499499
(25039 reductions, 39108 cells)
Main> test' 999
499499
(25038 reductions, 44104 cells)
Main> lazinessTest
(35927 reductions, 63879 cells)
ERROR: Control stack overflow
Main> lazinessTest'
1
(36 reductions, 73 cells)
Any ideas about why this happens, please?
Regards,
Tom
