JP Embedded Solutions

Combining Haskell lists with monads

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)) my

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.

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.

ghci session
GHCI session illustrating use of liftM2

Why does it work?

liftM2 is usually defined as

liftM2 :: (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 >>= return (\y -> f x)) = (\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.

About these ads

Filed under: Functional Programming, Haskell, Techniques, , , , , ,

One Response

  1. [...] 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 [...]

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

Copyright © 2011, JP Embedded Solutions, All rights reserved

All content is subject to the BSD license

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: