Data.List.partition on infinite lists
Iavor S. Diatchki
diatchki at cse.ogi.edu
Mon Nov 1 13:03:57 EST 2004
hi,
the foldr definition can be fixed by putting a ~ on the pattern in 'select'.
-iavor
Remi Turk wrote:
>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
>
>
>
More information about the Libraries
mailing list