[Haskell-beginners] partitionM

[Daniel Fischer]

Am Donnerstag 03 Dezember 2009 21:33:53 schrieb 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])

Before thinking much about it, I believe, a lazy pattern would help:

partitionHelper p ~(ts,fs) x = do ...

The reverse in partitionM still forbids infinite lists, I'll come to that later.

> > 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?