Learn You a Haskell mentions the
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])