Haskell monads form a type class. And Haskell type classes are essentially interfaces shared by some types. So the

`Monad`type class is a common API for talking to a bunch of different types. So the question is this: what's so special about this API?

One way to grasp an API is to see concrete examples. Usually the monad API is introduced through containers or IO. But I think that the prototypical monad through which all others can be understood is much simpler - it's the trivial monad.

APIs often capture design patterns, and the design pattern here is a one-way wrapper. We can wrap things but we can't unwrap them. We still want to be able to whatever we like to the wrapped data, but anything that depends on anything wrapped should itself be wrapped.

Without further ado, here's a wrapper type:

data W a = W a deriving Show

(The

`Show`bit is just so we can play with these things interactively.)

Note how it doesn't add anything except some wrapping. And the first thing we need is to be able to wrap anything we like. We can do that easily with this function:

return :: a -> W a

return x = W x

(We could have just used

`W`instead of

`return`. But I'm heading towards a common API that will work with other types too, so it obviously can't be called

`W`.)

And now we need one more thing - a way to manipulate wrapped data leaving it wrapped. There's an obvious idea. Given any function

`a -> b`we write a function that converts it to a function

`W a -> W b`. This is guaranteed to keep things under wraps. So here goes

.

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

fmap f (W x) = W (f x)

It seems that we've finished. For example we can wrap a number and then increment it:

a = W 1

b = fmap (+1) a

But here's something we can't do. Define a function

`f`like this:

f :: Int -> W Int

f x = W (x+1)

It increments and returns a wrapped result. Now suppose we want to apply the underlying operation here twice, ie. we'd like to increment a number twice and return a wrapped result. We can't simply apply

`f`twice because (1) it'll doubly wrap our result and (2) it'll attempt to add 1 to a wrapped result, something that doesn't make sense.

`fmap`doesn't do what we want either. Try it in an interactive Haskell session. It seems we need a way to apply

`f`, unwrap the result and apply

`f`again. But we've already said that we don't want to allow people to unwrap these things. We we need to provide a higher order function that does the unwrapping and application for us. As long as this function always gives us back something that is wrapped, our end users will never be able to unwrap anything. Here's an idea for such a function:

bind :: (a -> W b) -> (W a -> W b)

bind f (W x) = f x

Notice how it's very similar to

`fmap`but is even simpler. So now we can try doubly, or triply, incrementing

c = bind f (f 1)

d = bind f (bind f (f 1))

Notice how

`bind`is more general than

`fmap`. In fact,

`fmap f = bind (return . f)`.

And that's it. Using

`return`and

`bind`we have achieved our goal of wrapping objects and freely manipulating wrapped objects while keeping them wrapped. What's more, we can chain functions that wrap without getting bogged down in multiple layers of wrapping. And that, really, sums up what a Haskell monad is all about.

So here are a couple of exercises:

(1) define a function

`g :: Int -> W Int -> W Int`so that

`g x (W y) = W (x+y)`. Obviously that definition won't do - the left hand side has a

`W y`pattern so it's actually unwrapping. Rewrite this function so that the only unwrapping that happens is carried out by

`bind`.

(2) define a function

`h :: W Int -> W Int -> W Int`so that

`h (W x) (W y) = W (x+y)`. Again, no unwrapping.

I'm hoping that after you've done these exercises you'll see how you can still work freely with data even though it's wrapped.

In Haskell, it is more usual to use the operator

`>>=`instead of

`bind`where

`bind f x = x >>= f`.

So the last question is this: why would you ever wrap data like this? In practice people tend not to use the trivial monad very much. Nonetheless, you can see how it might be used to represent tainted data. Wrapped data is considered tainted. Our API never lets us forget when data is tainted and yet it still allows us to do what we like with it. Any time we try to do anything with tainted data the result is also tainted, exactly as we might expect. What I find interesting is that almost every monad, including IO, lists and even probability, can be thought of quite naturally as variations on taint. I hope to say more about this in the near future.

Anyway, code above fails to compile because of some namespace clashes. Here's a complete definition of

`W`that really works. Note also that

`fmap`, which we showed we don't really need, allows us to make

`W`an instance of

`Functor`too:

> data W x = W x deriving Show

> instance Functor W where

> fmap f (W x) = W (f x)

> instance Monad W where

> return x = W x

> W x >>= f = f x

Exercise 3: Prove the three monad laws for

`W`. This should be almost trivial.

Exercise 4: We can't completely unwrap things using the monad API. But we

*can*unwrap one layer from things that are wrapped twice. So here's a nice puzzle: define a function

`join :: W (W a) -> W a`using the

`Monad`API and no explicit unwrapping.

In conclusion, most monad tutorials show what monads are, and how to use them. I hope I've given some additional insight into why the

`Monad`interface consists precisely of the two functions it does. That insight should become clearer when I say more about taint.

PS I've been a bit busy lately with planning for kitchen remodelling, lots of work and a new cat(!). I probably won't be posting very frequently for a few months.

### Solutions to Exercises

Some people have found the exercises tricky so I'm posting some solutions. I think it's a good sign that they're tricky, it means that there is some non-trivial stuff to be learnt from playing with this monad. It ought to figure more strongly in tutorials. In a sense it allows people to learn about monadicity in its purest form.

Anyway, enough of that.

Exercise 1: We want

`g :: Int -> W Int -> W Int`so that

`g x (W y) = W (x+y)`. Start the definition like this

g x y = ...

We want to apply (+x) to y. But y is wrapped so we must use

`>>=`to apply it. But

`(+1)`doesn't have the right type to be applied with

`>>=`, it's an

`Int -> Int`not an

`Int -> W Int`. So we must compose with

`return`and we get

g x y = y >>= (return . (+x))

Exercise 2: We want

`h :: W Int -> W Int -> W Int`so that

`h (W x) (W y) = W (x+y)`. But

`g`is already fairly close. So again write

h x y = ...

The difference from

`g`is that

`x`is wrapped. So we want to apply

`\x -> g x y`to our wrapped value. This function is already of type

`Int -> W Int`. So we can just write

h x y = x >>= (\x -> g x y)

or just

`h x y = x >>= flip g y`.

Exercise 3: I'll just do the last one:

`(m >>= f) >>= g = m >>= (\x -> f x >>= g)`

`m`is of the form

`W x`for some

`x`:

(W x >>= f) >>= g

= (f x) >>= g

W x >>= (\x -> f x >>= g)

= (\x -> f x >>= g) x

= f x >>= g

So the LHS equals the RHS.

Incidentally, you can get a long way with these problems by not thinking about what's going on! Instead, just write out the type signatures of all of the functions involved and try to stick them together like a jigsaw puzzle so that the final result has the right type. At each stage the arguments of each function must match the signature of the function so it really is like fitting the shapes of jigsaw pieces together. This isn't a foolproof strategy, but it often works.

Anyway, feel free to ask questions if you're still stuck. Some of your questions may be answered here.

## 23 comments:

join m = m >>= id

Kevin,

I hope you didn't cheat!

Maybe he looked at the source for

Control.Monad.Identity.Thanks for the exercises. Defining h really got me to appreciate the functions in Control.Monad, especially the liftM* family =)

The problem with liftM* is, imho, the ugliness of having to use different functions depending on the arity of the lifted function. Perhaps that's what Control.Applicative is for?

instance Applicative W where

pure = return

ff <*> fx = ap ff fx

g x wy = pure (+) <*> pure x <*> wy

h wx wy = pure (+) <*> wx <*> wy

Yes! Beautiful.

Niclas,

'Applicative' is nice. If you dig out the original paper you'll see they propose a great syntax for applicatives, but I don't think it ever made its way into official release of Haskell.

I think the biggest thing waiting to be invented for Haskell is a way to apply things like liftM implicitly. I think 'Applicative' is a step in the right direction.

I have the paper on my desk. Had to consult it to define <*>. *blush*

Applicative and Traversable are already included in GHC, but I don't know if they are included by the other compilers. It would be a shame if they weren't included in a future set of standard haskell libraries though.

I've skimmed the paper a couple of times, but haven't used the ideas in real code yet. They seem to promise very elegant code. And that, to me, is probably the most important thing with haskell.

Automatically lifted functions and values would be sweet. It could perhaps lead to some obfuscation a la operator overloading in c++. I already feel a bit confused over what >>= does sometimes since it depends on what monad I'm in at the moment. I guess I would be similarly confused by automatic lifting. Then again, perhaps both >>= and automatic lifting are things you just get used to.

> I guess I would be similarly confused by automatic lifting.

So would I. This is why I think it's still a challenge for programming languages. Someone needs to find a way to do this that isn't confusing and still allows explicit control when needed.

I feel hopelessly stupid, as I've been stuck on defining h for more than an hour now. I even know that :

h = liftM2 (+)

but I'll be damned if I can actually define it from first principles.

Chuck,

I only just got around to doing my own exercises(!!) and I have to admit that they made me pause for a bit. Here's a hint: use 'g' in the definition of 'h'. If you do that then 'h' looks a lot like 'g'.

I'll put the answers in my next blog post - mainly because I'll be using them.

I took the long way around with looking up liftM2's definition in 'do' syntax, untangling the 'do' notation, then smacking my head for not realizing how to unwrap that first monad. From there it was pretty simple to see how g fit in there.

Monads click with me, thanks in no small part to all these tutorials ... now to learn Monad Transformers, Arrows and Comonads. And fundeps, and GADTs and a Partridge in a Pear Tree... It's weightlifting for the brain, Haskell is.

What prevents anybody from writing an unwrapper:

unwrap W x = x

Or something?

Moritz,

When I talk about managing tainted data I'm not describing some kind of secure programming, just as a 'private' member of a C++ class doesn't prevent people accessing private members through pointer trickery. The point is that if you have a block of code that uses only the monad interface you can reason about what data is 'tainted' really easily. You're free to access that data directly, rather than through the monad API. But at that point the useful theorems about monads no longer apply so it's going to be harder to figure out what is and isn't tainted.

Thanks, this article has been a huge help. In particular it has helped clarify the relationship between >>= and composition. I still don't like the syntax of >>= but, I can get around that now. I did suffer some frustration from not understanding that type definitions cannot be entered interactively and wasted a little time getting around that. A little note in the next revision might be of help. Anyway, I look forward to the next installment.

For exercises 1 and 2, using only functions defined up to those exercises:

exercise 1:

g x my = fmap (+x) my

exercise 2:

h w1 w2 = bind (\x -> fmap (+x) w2) w1

I have an apologetic blog entry discussing those solutions, the loquacious review process may be helpful to monad neophytes, should they be looking for an alternative approach to the solutions given here.

Hi, great post and very helpful in developing an intuition. One difficulty is that at the point you introduced the exercises, you had defined 'bind' but not (>>=), yet you give the solutions in terms of (>>=).

typo:

We we need to provide

@Moritz: In this case, nothing prevents people from writing an unwrapper, but often the data constructor will not be exported from a module, and so not be visible, as it is here.

for the 2nd question, defining h, the use of monad is overkill (and cumbersome). a discussion of applicative is warranted, since making W an instance of Applicative would allow you to define h quite naturally:

h x y = (+) <$> x <*> y

which looks a lot more like simple addition ((+) x y) than any of the monadic equivalents:

h x y = x >>= \x' -> y >>= y' -> return (x' + y')

Matthew,

It's cool that people are now identifying places where they can use Applicative instead of Monad. (Scroll up, you're not the first.) But this is intended as a Monad tutorial. I haven't written an Applicative tutorial yet. :-)

ur right, and it's an awesome tutorial. sorry I didn't say that in the first place!

Thank you! I really, really enjoyed the exercises, especially proving the Monad laws and writing "join": that was the only one where I got so stuck that I had to write the types out on paper.

Luckily I had the intuition to write out the type for bind, then try to get m (m a) on one side and m a on the other! It was fun.

When you define the increment and wrapping function, f :: Int -> W Int, you say that we can't do this. However, I can define this in Haskell. Is this a typo?

I think one can gain some intuition seeing h implemented without using g or >>= or other trickery, sort of the raw thing:

h :: W Int -> W Int -> W Int

h wx wy = bind (\x -> bind (\y -> return (x + y)) wy) wx

the most primitive way to use binds to gain access to multiple unwrapped values.

Post a Comment