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])
  • 1
    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] – abuzittin gillifirca May 12 '14 at 11:21
  • @abuzittingillifirca You've found a bug. I think that's worthy of an answer, not a comment. – 200_success May 12 '14 at 12:00
  • thank you, @abuzittingillifirca, for finding this bug. thanks too, 200_success. – Kevin Meredith May 14 '14 at 0:03
up vote 4 down vote accepted

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 – Kevin Meredith May 17 '14 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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.