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

Question

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"](http://www.haskell.org/haskellwiki/MonadPlus)" - 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 03 '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 03 '14 at 23:44

score 9 · Accepted Answer · answered Feb 03 '14 at 21:51

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.

Tom Ellis · Answer 2 · 2014-02-04T14:31:35.550

5

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 Monads, not just Maybe. (If you want to be even more general you can use traverse)

edited Feb 04 '14 at 14:31

answered Feb 03 '14 at 21:49

Tom Ellis

177
5

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 04 '14 at 09:06
1

Right, I meant https://www.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 04 '14 at 14:31

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

2 Answers2