# Implementation of partitionM

I needed a monadic version of partition today. I settled on the following version:

partitionM :: Monad m => (a -> m Bool) -> [a] -> m ([a], [a])
partitionM p xs = bimap (map fst) (map fst) . partition snd . zip xs <$> mapM p xs  Then I realized it's already implemented here: partitionM :: Monad m => (a -> m Bool) -> [a] -> m ([a], [a]) partitionM f [] = return ([], []) partitionM f (x:xs) = do res <- f x (as,bs) <- partitionM f xs return ([x | res]++as, [x | not res]++bs)  This second version doesn't have to pull in extra packages and doesn't create intermediate lists, but mine is shorter and doesn't have explicit recursion. What do you think of my solution in comparison with the library's implementation? • I don't see why you couldn't use foldM and get the best of all worlds: no explicit recursion, no extra dependencies, and no need for an extra <$> over top of mapM. – Alec Feb 24 '19 at 17:15
• foldM would end up with reversed lists if you appended to the front of the accumulator, would you not? – Roxy Feb 24 '19 at 20:39

This second version doesn't have to pull in extra packages…

Data.Bifunctor is part of base since 4.8.0.0, so I'm not sure where you get the "extra packages" from. Yes, Data.Bifunctor was originally in the bifunctors package, but it was transferred into base in 2015.

However, compared to the extras version, your variant is easy to read, as the [x | res] … [x | not res] slightly obfuscates the result. I'd probably bind map fst, but that's personal preference.

and doesn't create intermediate lists

It generates a lot of intermediate lists. I haven't checked yet, but as [x|res]++as depends on res cannot get simplified to x:as or as at compile time by rules, so it might create a thunk […]++as. In the end, you have $$\\mathcal O(n) \$$ additional $$\\mathcal O(1)\$$-sized lists.

Since this is a hidden implementation detail, I don't really like Neil's solution too much. Something along

partitionM :: Monad m => (a -> m Bool) -> [a] -> m ([a], [a])
partitionM f [] = return ([], [])
partitionM f (x:xs) = do
res <- f x
(as,bs) <- partitionM f xs
return $if res then (x : as, bs) else ( as, x : bs)  would at least support the optimizer and get rid of those intermediate lists, but is even more verbose. Your variant uses an additional list, sure, but it's easier to read and to understand IMHO. This version uses only base, doesn't create extra lists and has no explicit recursion. The amount of plumbing this requires disturbs me - there ought to be a library out there that makes these building blocks fit together without naming acc and res. partitionM f = foldrM (\x acc -> (\res -> bool second first res (x:) acc) <$> f x) ([], [])