Haskell's `partition`

Question

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

Answer 1

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

Answer 2

Why not just use filter -- unless you are trying to avoid using filter? Filter would remove the need for ++.

Check out this SO question.