Data.List.partition on infinite lists
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]
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.
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
This mail pretty much sums up the situation: http://www.haskell.org/pipermail/glasgow-haskell-bugs/2004-October/004389.ht ml This will be fixed in GHC 6.4. /Josef
-----Original Message----- From: libraries-bounces@haskell.org [mailto:libraries-bounces@haskell.org] On Behalf Of Lemming Sent: den 31 oktober 2004 18:37 To: libraries@haskell.org Subject: Data.List.partition on infinite lists
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]
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
participants (4)
-
Iavor S. Diatchki -
Josef Svenningsson -
Lemming -
Remi Turk