Combining Lists, Monads & Applicative Functors

This is an updated version of a previous post called Combining Haskell lists with monads. This version includes discussion of how the purely monadic approach taken in that paper can be extended to applicative functors and other such things.

A common problem

Say I am writing some code in Haskell, and I have a value of type a and a list of type [b] that I want to convert into a list of type [(a,b)] where every entry is one of the pair of the a value and one of the values from the list. So I want a function:

pairThem :: a -> [b] -> [(a,b)]

the ‘obvious’ solution is one of

pairThem x ys = map (\y -> (x,y)) ys

or

pairThem x ys = zip (repeat x) ys

Simple enough, but they’re hard to generalise, the use of a lambda to do something so simple is rather ugly, and using infinite lists on such a problem seems rather excessive, I feel.

What I’m going to do here is take a detour via monad which helps motivate the concept of an applicative functor, which is not always well-explained, giving an elementary explanation for where they come from and why. So I’ll discuss monads, then applicative functors, always bearing in mind the example of the list, which is an instance of each.

Using a monad

It’s more illuminating to remember that lists form a monad. If we look for a monadic solution we see beyond the surface problem of manipulating lists and can get an insight into what’s really going on, as well as seeing just how powerful monads can be. So the natural function with the right signature is

pairThem x ys = liftM2 (,) [x] ys

But [x] = return x in the list monad, so in fact we could write this as

pairThem :: (Monad m) => a -> m b -> m (a,b)
pairThem x ys = liftM2 (,) (return x) ys

This works (see the illustration) but the point is that we’re not doing anything list-specific any more. This is a piece of extremely generic monadic code for pairing two monad values to get a monadic tuple value. One of the main goals in writing Haskell code is to make your code as generic as possible. Here I’ve gone from writing code which insists that I use lists to code that requires only a monad. This must be a good thing.

Why does it work?

liftM2 is usually defined as

liftM2 :: (Monad m) => (a -> b -> c) -> m a -> m b -> m c
liftM2 f mx my = do
  x <- mx
  y <- my
  return $ f x y

which can be rewritten in a more functional way as

liftM2 f mx my = mx >>= (\x -> my >>= (\y -> return (f x y)))

(it’s a good exercise to see why these are equivalent). So when m = [] and f = (,) let’s take this apart. First :

(\x -> my >>= (\y -> return (f x y)) = (\x -> concatMap (\y -> [(x,y)]) my)

and so

liftM2 (,) mx my = mx >>= (\x -> (\y -> concatMap [(x,y)]) my)
                 = concatMap (\x -> (\y -> concatMap [(x,y)]) my) mx

which, when mx = [x], reduces to

liftM2 (,) [x] my = concatMap (\y -> [(x,y)]) my = map (\y -> (x,y)) my

which is where we started.

Generalisations

We can see immediately that in fact the function

cartesian :: (Monad m) => m a -> m b -> m (a,b)
cartesian = liftM2 (,)

will, when applied to lists, produce their Cartesian product (all pairs with one value in the pair from each list). You would normally be taught to do that with a list comprehension

[(x,y) | x <- xs, y <- ys]

So the moral is, monads can do an awful lot that you might not expect, and much complex list manipulation can be made into simple monadic operations if you look at it the right way. And, as well as genericity, simplicity has to be our goal: mistakes are far easier in complex code.

Applicative Functors

Functors

We’re used to the idea of the Functor type. If a is a type and f is a parameterised type, then f is a functor if there is an operation

fmap :: (a -> b) -> f a -> f b

that lifts a function from bare types into a function between the f types that they parameterise. So if f = [] then fmap = map. If f is a monad then f = liftM. To see that these two definitions are consistent observe that

liftM f = (\ x -> do
  a <- x
  return $ f a

or, in the list monad,

liftM f $ x = x >>= (return f)
            = concatMap (return f) x
            = map f x

Applicative Functors

Now, functions are types too, so if f is a functor, I can quite easily form the type

f (a -> b)

For example this could be a list of functions. Now what would I do with a list of functions a -> b? Obviously, I could apply them to something in a to get a list of type [b], or I could apply them to a list [a] to get a list [b]. Let’s take these in reverse order.

Mapping a list to a new list

I want something like:

apply :: (Functor f) => f (a -> b) -> f a -> f b

Let’s take this apart. On lists I have to do this

apply gs xs = concatMap (\ g -> map g xs) gs

So I have to unwrap the list of functions fs to get at the individual functions within it, apply them individually to the data list xs and then concatenate the results.

More generally, I need a function something like:

(<*>) :: (Functor f) => f (a -> b) -> f a -> f b

such that

apply = (<*>)

Clearly therefore we must have

gs <*> xs = concatMap (\ g -> map g xs) gs
          = gs >>= (\g -> concatMap (return . g) xs)
          = gs >>= (\g -> xs >>= (return . g))
          = gs `ap` xs

Mapping a list to a new list

Now we want to do

apply :: f (a -> b) -> a -> f b

we already have <*>, so if we had a function

pure  :: (Functor f) => a -> f a

then we could take

apply f x = f <*> (pure x)

On lists we clearly have

pure x = [x]
       = return x

Defining the type

We have defined operations:

pure  :: (Functor f) => a -> f a
(<*>) :: (Functor f) => f (a -> b) -> f a -> f b

A Functor with these two operations is called an Applicative Functor. In general, any monad can be made into an applicative functor by taking

pure = return
<*>  = ap

just as we showed for lists above.

Let us take stock. In general, if we have a functor f and a function

g :: a -> b

Then we can form

fmap . g : f a -> f b

However, there is a much richer class of ‘functions’ related to f, i.e. objects like

h :: f (a -> b)

So if we take f = [] then fmap allows us to lift single functions to the monad, but applying lists of functions requires more machinery than just fmap. Similarly in the State monad then we can form

liftM g :: State s a -> State s b

which evaluates the monad and changes its value, but leaves the state alone. However there is a wider class of transformation

h :: State s (a -> b)

which combines a transformation of the value with a transformation of the state.

Now, I can do this in any monad with ap. The strength of applicative functors lies in the fact that they allow this extra richness in transformations without demanding the full structure of a monad.

A mathematical analogy

For those accustomed to simple algebra, here is an analogy. Say have a functor \mathfrak{F} that takes rings to rank 2 free modules over those rings. So if f:A\rightarrow B then \mathfrak{F}f is the natural map

(x,y)\mapsto (f x,f y)

This is precisely what fmap would do under the circumstances.

However, the full space of morphisms \mathfrak{F}A\rightarrow\mathfrak{F}B should allow the first and second components of a morphism to differ, so we want morphisms like

(x,y)\mapsto (f x,g y)

And hence, very naturally, a map

\mathfrak{F}\text{Mor}(A,B)\rightarrow\text{Mor}(\mathfrak{F}A,\mathfrak{F}B)

This is precisely what an applicative functor gives us.

Applying this to the problem

So, say f is an applicative functor. Clearly we have equivalents of liftM and liftM2:

liftA  :: (Applicative f) => (a -> b) -> f a -> f b
liftA g x = (pure g) <*> x

liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c
liftA2 g x y = ((pure g) <*> x) <*>  y

If f is a monad then

liftA g x = (pure g) <*>  x
          = (return g) `ap` x
          = (return g) >>= (\g' -> x >>= (\x' -> (return . g') x))
          = x >>= (\x' -> (return . g) x)
          = liftM g x

liftA2 g x y = ((pure g) <*>  x) <*>  y
             = (liftA g x) <*>  y
             = (liftM g x) `ap` y
             = (liftM g x) >>= (\g' -> y >>= (return . g'))
             = x >>= (\x' -> (return . g) x) >>=
                     (\g' -> y >>= (\y' -> (return . g') y'))
             = x >>= (\x' -> y >>= (\y -> return (g x y)))
             = liftM2 x y

So, in conclusion we can generalise our functions above still further to

pairThem :: (Applicative f) => a -> f b -> f (a,b)
pairThem x ys = liftA2 (,) (pure x) <*> ys

cartesian :: (Applicative f) => f a -> f b -> f (a,b)
cartesian = liftA2 (,)

this, it turns out, is the most general way of expressing the operations we started from.

Conclusion

So, what we have seen is first that it can always be worth looking for Monads, Functors and Applicative Functors lurking in apparently innocent problems, as they provide an extremely elegant way of reducing code to the most simple and minimal form.

In addition, I have used this to motivate the class of Applicative Functor, which is a Functor f that lets me take a value of type f (a -> b) and apply it to a value of type f a to get a f b, which is the natural generalisation of applying map across a list of functions. So Functors generalise applying a function to a list with map; Applicative Functors generalise using concatMap to apply a list of functions to a a list of values.

The point of all this is as follows: if f is a parameterised type, then there is every chance that functions f a -> f b are much richer than just a -> b, and so the functorial operator fmap only gives access to part of this structure. The way we access this wider structure is by understanding f (a -> b) and then using an applicative functor to transform this into functions f a -> f b.

Advertisements

12 thoughts on “Combining Lists, Monads & Applicative Functors

  1. Maybe I just dont get it, but could you please explain why using an infinite list is “excessive”?
    Also, what about “keep it simple, stupid”?

    1. I cannot help but think that invoking a structure of infinite extent in order to solve a rather simple finite problem is excessive. Finding oneself doing such a thing should be a warning that one is doing something seriously wrong.

      And surely the point about simplicity is that it is conceptual simplicity that matters. There is a great difference between simplicity, which can lead to new insights (as happens in this case) and crudity, from which one can learn nothing.

      1. You’re probably right about the style, but for the purposes of introducing the concept of the Applicative Functor, I think liftA2 is a bit easier to understand. Then you can move on to the clever short-cuts once you’re happy you understand what an Applicative Functor actually is.

  2. Hi! At page #2 there is this sentence: “Clearly for any function f :: a -> Id b we have f ≡ return ○ val ○ f ≡ return ○ g where g = val ○ f :: a -> b.”
    So I can’t understand why g = val ○ f:: a->b. Shouldn’t it be g = f:: a -> b or at least g = val ○ f:: a-> Id b ?
    I am a newbie in all this stuff so I may be wrong.

  3. Using the () operator from Control.Applicative gives a nice clean way to pair a single item to a functor, which of course the list is a member of that class as is of monad.

    pairThemF
    :: forall (f :: * -> *) a a1. Functor f => a1 -> f a -> f (a1, a)
    pairThemF x = (((,) x) )

    pairThemF 5 [10..18]
    [(5,10),(5,11),(5,12),(5,13),(5,14),(5,15),(5,16),(5,17),(5,18)]

    pairThemF “Integer” [1..7]
    [(“Integer”,1),(“Integer”,2),(“Integer”,3),(“Integer”,4),(“Integer”,5),
    (“Integer”,6),(“Integer”,7)]

    pairThemF “Integer” (Just 8)
    Just (“Integer”,8)

    pairThemF “Integer” Nothing
    Nothing

    =========
    The monadic attack would be something like:
    [1..5] >>= return . (\a -> ((,) “Integer”) a)
    [(“Integer”,1),(“Integer”,2),(“Integer”,3),(“Integer”,4),(“Integer”,5)]

    or if you like for getting the list on the other end of things and throwing in some arrow notation… just for fun!!:

    pairThemM
    :: forall (m :: * -> *) a b. Monad m => a -> m b -> m (a, b)
    pairThemM z xs = (((\a -> ((,) z) a) >>> return) =<<) xs

    Which allows the same as for the Applicative above:

    pairThemM "integer" [3..6]
    [("integer",3),("integer",4),("integer",5),("integer",6)]

    pairThemM "integer" (Just 12)
    Just ("integer",12)
    Lots of ways to skin a cat in Haskell, and none of them wrong.. even the bit of waste involved in producing a list to zip..

    — cheers, gene

  4. OOPs … looked at the reply AFTER SENDING… right at beginning the definition of pairThemF should have been:

    pairThemF x = (((,) x) )

    the applicative operator () got left out somehow..

    — gene

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s