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?