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

partitionM :: Monad m =&gt; (a -&gt; m Bool) -&gt; [a] -&gt; m ([a], [a])
partitionM p xs = bimap (map fst) (map fst) . partition snd . zip xs &lt;$&gt; mapM p xs


Then I realized it's already implemented here:


partitionM :: Monad m =&gt; (a -&gt; m Bool) -&gt; [a] -&gt; m ([a], [a])
partitionM f [] = return ([], [])
partitionM f (x:xs) = do
    res &lt;- f x
    (as,bs) &lt;- 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?
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 =&gt; (a -&gt; m Bool) -&gt; [a] -&gt; m ([a], [a])
partitionM f [] = return ([], [])
partitionM f (x:xs) = do
    res &lt;- f x
    (as,bs) &lt;- 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.