Saturday, April 28, 2007

The Trivial Monad

Update: I've added some solutions to exercises below.

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.

21 comments:

Kevin said...

join m = m >>= id

sigfpe said...

Kevin,

I hope you didn't cheat!

Anonymous said...

Maybe he looked at the source for Control.Monad.Identity.

Niclas said...

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.

sigfpe said...

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.

Niclas said...

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.

sigfpe said...

> 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.

Chuck said...

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.

sigfpe said...

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.

Chuck said...

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.

Moritz said...

What prevents anybody from writing an unwrapper:

unwrap W x = x

Or something?

sigfpe said...

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.

Ralph said...

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.

geophf said...

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.

Mike M. said...

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 (>>=).

Anonymous said...

typo:
We we need to provide

BorisTheBlade said...

@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.

Matthew Kane Parker said...

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

sigfpe said...

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. :-)

Matthew Kane Parker said...

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

openid said...

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.

Blog Archive