Haskell's `partition`
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 -&gt; Bool) -&gt; [a] -&gt; [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