Haskell's partition

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

• Your current version is not equivalent to the partition of Data.List. take 10 $fst$ partition' (\x -> (x mod 2 == 0)) [1..] gives a runtime error. Where as take 10 $fst$ partition (\x -> (x mod 2 == 0)) [1..] is [2,4,6,8,10,12,14,16,18,20] May 12, 2014 at 11:21
• @abuzittingillifirca You've found a bug. I think that's worthy of an answer, not a comment. May 12, 2014 at 12:00
• thank you, @abuzittingillifirca, for finding this bug. thanks too, 200_success. May 14, 2014 at 0:03

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

• Excellent! I used your helpful answer to write your "spoiler" answer. It's so concise - thanks 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.