CODEWITHSUNDEEP
haskell
Bob
Bob

Reputation: 33

Looking for the name of a special map function

I'm new to Haskell and looking for the name of a function (or generally, the name of the concept) that acts as such:

The function takes two arguments:
1. A list of elements [T]
2. A function that takes a T, and returns a Maybe U.

The function's output is as follows:
If all elements in the list map to Some U, then return Some [U].
Otherwise, return None.

i.e. if any of the mapped values are null, then return null, otherwise just return the mapped values.

Upvotes: 3

Views: 192

Answers (5)

Zeta
Zeta

Reputation: 105905

The Haskell report calls it sequence . map f, also called mapM f. Nowadays you can call it traverse f (GHC 7.10+).

Map and sequence

Let us think about the type of your function:

withList :: (a -> Maybe b) -> [a] -> Maybe [b]

The canonical function for mapping a list to another one is map, so we can use that as starting point:

withListNotYet :: (a -> Maybe b) -> [a] -> [Maybe b]
withListNotYet f xs = map f xs

Now we have a list of Maybe b, but we want to get the Maybe outside. This is essentially what sequence does:

sequence :: Monad m => [m a] -> m [a]
sequence []     = return []
sequence (x:xs) = do
  y  <- x
  ys <- sequence xs
  return (y : ys)

Since Maybe is an instance of Monad, we can use sequence after withListNotYet and end up with our implementation for withList:

withList f xs = sequence (map f xs)

Since this is a common operation, it has has a name: mapM:

withList f xs = mapM f xs
-- or
withList = mapM

Traversable

During the "burning bridges proposal", mapM's type changed from 

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

to

mapM     :: (Monad m, Traversable t)       => (a -> m b) -> t a -> m (t b)

There was already a similar function at that time, called traverse:

traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)

As you can see, the type signature is very similar. The same GHC version that changed mapM's type also made Applicative a base class of Monad, see Functor-Applicative-Monad-Proposal. So nowadays you can usually use traverse or mapM. The former is the younger, more general variant, while the latter is the older, historical variant.

And if you have a look at the Traversable class, you will notice that mapM = traverse by default.

Upvotes: 7

Redu
Redu

Reputation: 26191

While Data.Traverable.traverse seems to be the right answer, You may also implement a similar functionality by yourself.

isJust :: Maybe a -> Bool
isJust (Just _) = True
isJust _        = False

withList :: (a -> Maybe b) -> [a] -> Maybe [b]
withList f xs | all isJust js = Just (map (\(Just x) -> x) js)
              | otherwise     = Nothing
              where js = map f xs

*Main> withList (\xs -> if all (<10) xs then (Just (sum xs)) else Nothing) [[1,2,3],[4,5,6],[7,8,9]] 
Just [6,15,24]
*Main> withList (\xs -> if all (<9) xs then (Just (sum xs)) else Nothing) [[1,2,3],[4,5,6],[7,8,9]]
Nothing

Upvotes: 1

danidiaz
danidiaz

Reputation: 27766

The function is called traverse, from Data.Traversable.

The type might surprise at first because it is quite abstract:

traverse :: (Applicative f,Traversable t) => (a -> f b) -> t a -> f (t b)

Applicative and Traversable are two interfaces (typeclasses in Haskell terms).

  • The Applicative abstracts over the effects we want to perform. In your case it is failure (Maybe) but it could also be failure-with-cause (Either), input/ouput (IO), concurrent input/ouput (Concurrently) and many others.

  • The Traversable abstracts over the type of container. In your case it is a list ([]). But other containers are also Traversable: finite containers that have a shape independent of its own values. Trees and Maps are examples. (Sets are not an example, because their "shape" depends on their values: changing all the elements into the same value will reduce the size of the set.)

Traversable is a interface for containers that support "internal iteration". It's basically the forEach of other languages. But it also provides you with a result container of the same shape as the original which holds the transformed values.

If you don't care for the transformed container, the related traverse_ function discards the result and is only executed for the effects.

The mapM function is a synonym for traverse that exists for historical reasons.

Upvotes: 5

Love T&#228;tting
Love T&#228;tting

Reputation: 221

These are all really good answers. I just want to add to the board that you can find this information much faster with hoogle. If you know what you are looking for good enought that you can produce the type signature for your sought after expression, hoogle will search for it. It is smart enough to understand type variables etc (ie it doesn't matter if you write T and U as you did, or a and b as is common in Haskell).

Taking your example verbatim, [T] -> (T -> Maybe U) -> Maybe [U], you will find among others traverse and mapM, both of which have been mentioned by other peers. Happy hoogling!

Upvotes: 2

Lee
Lee

Reputation: 144176

This is traverse defined in the Traversable class:

traverse :: Traversable t, Applicative f => (a -> f b) -> t a -> f (t b)

in your example t is list and f is Maybe e.g.

traverse (\x -> if x < 5 then Just x else Nothing) [1,2,3]
> Just [1,2,3]

traverse (\x -> if x < 5 then Just x else Nothing) [1,2,3, 9]
> Nothing

Upvotes: 12

Related Questions