Re: Data.List.partition on infinite lists

On Sun, Oct 31, 2004 at 06:37:20PM +0100, Lemming wrote:
> 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)

Ah, IIRC one of my very first haskell-posts was about this :)

Actually, AFAICS this isn't just a could-be-better, but a real
Bug(TM). According to The Report the definition is:

partition p xs = (filter p xs, filter (not . p) xs)

which doesn't have any trouble with infinite lists.

> 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)

Cheers,
Remi

-- 
Nobody can be exactly like me. Even I have trouble doing it.