darcs patch: Improve Control.Monad.filterM:
simonmarhaskell at gmail.com
Tue Aug 8 11:24:33 EDT 2006
Chris Kuklewicz wrote:
> Simon Marlow wrote:
>> Spencer Janssen wrote:
>>> Fri Aug 4 13:49:57 CDT 2006 Spencer Janssen <sjanssen at cse.unl.edu>
>>> * 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
>> 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
>> 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) ; 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.
More information about the Libraries