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