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

Chris Kuklewicz wrote:

Simon Marlow wrote:

...

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).

The new one looks better to me.

It may well be better, but it doesn't have the same laziness properties, so it isn't the same function. eg. try this: do filterM (\x -> return undefined) [1]; return () Of course we may discuss whether the extra laziness is useful, but I can't apply the patch as it stands because it would break Haskell 98.

But the foldr is not needed:

The foldr was there to allow fusion, I believe. Cheers, Simon