Is there a lazy mapM?

问题:

At first glance I thought these two functions would work the same:

firstM _ []     = return Nothing
firstM p (x:xs) = p x >>= \r -> if r then return (Just x) else firstM p xs

firstM' p xs    = fmap listToMaybe (mapM p xs)

But they don't. In particular, firstM stops as soon as the first p x is true. But firstM', because of mapM, needs the evaluate the whole list.

Is there a "lazy mapM" that enables the second definition, or at least one that doesn't require explicit recursion?

回答1:

One solution is to use ListT, the list monad transformer. This type interleaves side effects and results, so you can peek at the initial element without running the whole computation first.

Here's an example using ListT:

import Control.Monad
import qualified ListT

firstM :: Monad m => (a -> Bool) -> [a] -> m (Maybe a)
firstM p = ListT.head . mfilter p . ListT.fromFoldable

(Note that the ListT defined in transformers and mtl is buggy and should not be used. The version I linked above should be okay, though.)

回答2:

If there is, I doubt it's called mapM.

As I recall, mapM is defined in terms of sequence:

mapM :: Monad m => (a -> b) -> [a] -> m [b]
mapM f = sequence . map f

and the whole point of sequence is to guarantee that all the side-effects are done before giving you anything.

As opposed to using some alternate mapM, you could get away with just using map and sequence, so you could change the container from [a] to Just a:

firstM p xs = sequence $ listToMaybe (map p xs)

or even:

firstM p xs = mapM f $ listToMaybe xs

Now that mapM and sequence can operate on generic Traversables, not just lists.

回答3:

There isn't (can't be) a safe, Monad-polymorphic lazy mapM. But the monad-loops package contains many lazy monadic variants of various pure functions, and includes firstM.