[Haskell-beginners] partitionM

[Tom Tobin]

While working on some filesystem traversal code, I found myself
wanting to use the 'partition' function from Data.List, but with the
function 'doesDirectoryExist' in System.Directory (with type Filepath
-> IO Bool).  I noticed that there was no 'partitionM' in
Control.Monad, so I set out to write one.

Here's what I ended up with:

> import Control.Monad (foldM)

> partitionMHelper :: Monad m => (a -> m Bool) -> ([a],[a]) -> a -> m ([a],[a])
> partitionMHelper p (ts,fs) x = do
>     b <- p x
>     return (if b then (x:ts,fs) else (ts,x:fs))

> partitionM :: (Monad m) => (a -> m Bool) -> [a] -> m ([a], [a])
> partitionM p xs = foldM (partitionMHelper p) ([],[]) $ reverse xs

This works for my trivial cases, but can fail with extremely large
lists (not to mention being unable to take an infinite list and work
properly when passed to something like 'take 5').  Is there a way to
change the function to avoid having to traverse to the end of the list
(via reverse) just to get the output in the proper order?  I started
trying to write a "foldrM", but haven't gotten anywhere useful yet.

Can someone point me in the right direction?