darcs patch: Improve Control.Monad.filterM:

[Simon Marlow]

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