# Mapping a list of optional values to an optional list of values

I have encountered the following pattern while programming in Haskell (but the pattern could occur in any language supporting lists, option types, and mapping of a function over a list). I have types `a` and `b` and a function

``````f :: a -> Maybe b
``````

Now I want to define a function that maps f on a list of type `[a]`, but I am not interested to have a result of type `[Maybe b]`. Rather, I want to have `Just [y1, ..., yn]`, if `[f(x1), ..., f(xn)] == [Just y1, ..., Just yn]`, and `Nothing` otherwise (i.e. if `f(xi) == Nothing` for at least one i). So the result must be of type `Maybe [b]`.

I solved this by using the following helper function:

``````combine :: Maybe b -> Maybe [b] -> Maybe [b]
combine me ml = do
l <- ml
e <- me
Just (e : l)
``````

and then

``````g :: (a -> Maybe b) -> [a] -> Maybe [b]
g f xs = foldr combine (Just []) (map f xs)
``````

So, for example, if I have

``````f x = if x > 0 then Just x else Nothing
xs0 = [1, 2, 3, 4]
xs1 = [-1, -2, 3, 4]
xs2 = [-1, -2, -3, -4]
``````

then

``````map f xs0 = [Just 1, Just 2, Just 3, Just 4]
g f xs0   = Just [1, 2, 3, 4]
map f xs1 = [Nothing, Nothing, Just 3, Just 4]
g f xs1   = Nothing
map f xs2 = [Nothing, Nothing, Nothing, Nothing]
g f xs2   = Nothing
``````

The solution with `combine` and `foldr` works, but I wanted to ask if you know of a more compact solution for turning a `[Maybe a]` into a `Maybe [a]` as described above.

• I think the general concept you're looking for isn't in the monad, rather it's hiding in monoid / monadplus -> You basically want mempty/mzero or m [a] which is what bind usually gives you over monoids/monadplus, this is called "left zero"" - given a generic implementation of the left zero rule as described there you can generally implement something that will go from [a] -> m [a] wherein you'll get mzero/mempty if any of the [m a] has that. I think mconcat will give you this offhand if you `mconcat . return (map yourfunc yourlist)` – Jimmy Hoffa Feb 3 '14 at 23:39
• actually mconcat won't do this, rather it would drop the memptys if I'm not mistaken... so you need to rely on the bind function's left zero because mappend doesn't give you left zero, which is why mapM is what you want. You want mapM on a monad which implements monoid or monadplus basically. – Jimmy Hoffa Feb 3 '14 at 23:44

You want a function with this signature:

``````(a -> Maybe b) -> [a] -> Maybe [b]
``````

Entering this into hoogle gives this possibility:

``````Prelude mapM :: Monad m => (a -> m b) -> [a] -> m [b]
``````

A look at the Hackage documentation for `mapM` says it is the same as:

``````mapM f = sequence . map f
``````

and that the definition of `sequence` is:

``````sequence       :: Monad m => [m a] -> m [a]
sequence ms = foldr k (return []) ms
where
k m m' = do { x <- m; xs <- m'; return (x:xs) }
``````

which is pretty much your `foldr` solution.

The best way to approach this is to go to FP Complete's Hoogle and type in the signature you're looking for, `(a -> Maybe b) -> [a] -> Maybe [b]`. The first hit is a function called `mapM` which is exactly what you are looking for. In fact it works for all `Monad`s, not just `Maybe`. (If you want to be even more general you can use `traverse`)

• I'm not sure hoogle is anything to do with FP complete, I certainly can't see a relevant link from the page you have linked – jk. Feb 4 '14 at 9:06
• Right, I meant fpcomplete.com/hoogle -- it's just a deployment of Neil Mitchell's Hoogle that happens to be run by FP Complete. The reason to prefer it to hoogle.com is that it searches more packages by default. I'll update my link. – Tom Ellis Feb 4 '14 at 14:31