Re: darcs patch: Improve Control.Monad.filterM:

Spencer Janssen wrote:

Fri Aug 4 13:49:57 CDT 2006 Spencer Janssen * Improve Control.Monad.filterM: * filterM is defined in terms of foldr, making it a good consumer in GHC's fusion framework * filterM uses linear stack space with respect to the number of items that the predicate returns true, rather than the total number of elements in the input. ... hunk ./Control/Monad.hs 151 -filterM _ [] = return [] -filterM p (x:xs) = do - flg <- p x - ys <- filterM p xs - return (if flg then x:ys else ys) +filterM p = foldr f (return []) + where + f x xs = do + flg <- p x + if flg + then xs >>= return . (x:) + else xs }

The new definition looks less lazy than the original, so it's not a drop-in replacement. Also, we would need some measurements to test whether this version doesn't lose efficiency - it probably fuses better, but might be slower when it doesn't fuse. Rules to turn the foldr version back into the recursive version might be needed (or aggressive inlining). Cheers, Simon