darcs patch: Improve Control.Monad.filterM:

Simon Marlow simonmarhaskell at gmail.com
Tue Aug 8 08:18:51 EDT 2006


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

Cheers,
	Simon




More information about the Libraries mailing list