Data.List.partition on infinite lists

Lemming schlepptop at henning-thielemann.de
Sun Oct 31 12:37:20 EST 2004


I encountered that the implementation of 'partition' in GHC 6.2.1 fails
on infinite lists:

> partition :: (a -> Bool) -> [a] -> ([a],[a])
> partition p xs = foldr (select p) ([],[]) xs

> select p x (ts,fs) | p x       = (x:ts,fs)
>                    | otherwise = (ts, x:fs)


With the following definition we don't have this problem:

> partition :: (a -> Bool) -> [a] -> ([a], [a])
> partition _ [] = ([],[])
> partition p (x:xs) =
>    let (y,z) = partition p xs
>    in  if p x then (x : y, z)
>               else (y, x : z)


Prelude> take 10 $ fst $ partition even [0..]
[0,2,4,6,8,10,12,14,16,18]
Prelude> take 10 $ snd $ partition even [0..]
[1,3,5,7,9,11,13,15,17,19]





More information about the Libraries mailing list