Learn You a Haskell mentions the partition function:
partition takes a list and a predicate and returns a pair of lists. The first list in the result contains all the elements that satisfy the predicate, the second contains all the ones that don't.
How's my implementation? I'd prefer to avoid the ++ function, but I'm not sure how to avoid it here.
partition' :: (a -> Bool) -> [a] -> ([a], [a])
partition' f [] = ([], [])
partition' f ys = partition'' f ys [] []
where partition'' f [] as bs = (as, bs)
partition'' f (x:xs) as bs
| f x = partition'' f xs (as ++ [x]) bs
| otherwise = partition'' f xs as (bs ++ [x])
2 Answers 2
As @aled1027 suggests, partition' is just a fancy form of filter. Therefore, it would be useful to study how filter can be implemented without ++.
filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' f (x:xs)
| f x = x:rest
| otherwise = rest
where rest = filter' f xs
The key to avoiding ++, I think, is to force yourself to write x: first, then figure out how to fill in everything surrounding it. The next logical step would be to write
| f x = x:filter' f xs
... and the rest should follow naturally.
Here's what I came up with for partition' (hover for spoiler):
partition' :: (a -> Bool) -> [a] -> ([a], [a]) partition' _ [] = ([], []) partition' f (x:xs) | f x = ((x:accepted), rejected) | otherwise = (accepted, (x:rejected)) where (accepted, rejected) = partition' f xs
-
\$\begingroup\$ Excellent! I used your helpful answer to write your "spoiler" answer. It's so concise - thanks \$\endgroup\$Kevin Meredith– Kevin Meredith2014年05月17日 14:50:57 +00:00Commented May 17, 2014 at 14:50
Why not just use filter -- unless you are trying to avoid using filter? Filter would remove the need for ++.
Check out this SO question.
partitionofData.List.take 10 $ fst $ partition' (\x -> (x `mod` 2 == 0)) [1..]gives a runtime error. Where astake 10 $ fst $ partition (\x -> (x `mod` 2 == 0)) [1..]is[2,4,6,8,10,12,14,16,18,20]\$\endgroup\$