darcs patch: Improve Control.Monad.filterM:

[Jon Fairbairn]

On 2006-08-08 at 15:40BST I wrote:
> I'm curious to know how this performs:
> 
> > filterM p = fmap catMaybes . mapM (predMToMaybe p)

and the answer is "quite badly"...

> since this definition of filterM clearly shouldn't hold onto
> anything in the second half (. mapM (predMToMaybe p))

... because the above statement is wrong: mapM has the same
problem as the original filterM.

If we replace mapM thus:

> mapM f  = mapM' [] f
> mapM' acc p [] = return (reverse acc)
> mapM' acc p (h:t)
>     = do e <- p h
>          (mapM' $! (e:acc)) p t

then we get something that doesn't overflow the stack on
Spencer's fuse test, but which doesn't diverge on 

> do filterM (\x -> return undefined) [1]; return ()

The new mapM is spine-strict on the list, but so, I think,
is the old version -- at least

> (mapM (return . (+1)) [1..]) >>= print.head

diverges for both versions

The speed of my filterM leaves a lot to be desired: it seems
to be something like one eighth the speed of Spencer's on
the fuse benchmark and one quarter on "none".  Perhaps
someone who understands the ins and outs of these things
better than I do could explain?

[It's not the use of maybes, because 

> filterM_strict p = foldr cm (return []) . map (predMToMaybe p)
>     where cm x xs
>               = do c <- x
>                    case c of Just x -> xs >>= return . (x:)
>                              Nothing -> xs

is competetive with Spencer's version (and as strict)]

It does seem to be faster in at least some cases than
Monad.filterM.


   Jón

-- 
Jón Fairbairn                              Jon.Fairbairn at cl.cam.ac.uk