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.

25 comments:

  1. Kevin,

    I hope you didn't cheat!

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

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

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

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

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

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

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

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

    ReplyDelete
  10. What prevents anybody from writing an unwrapper:

    unwrap W x = x

    Or something?

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

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

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

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

    ReplyDelete
  15. typo:
    We we need to provide

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

    ReplyDelete
  17. 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')

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

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

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

    ReplyDelete
  21. 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?

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

    ReplyDelete
  23. I just got to exercise one, and was unable to solve it. I went to the solutions and saw the =>> operator. This is not explained in the text leading up to the exercise.

    Is there a prerequisite reading for this article?

    I've been reading "LYaHfGG" before coming to this article but had to throw the towel once hitting functors and monads (which is why I ended up here).

    I saw that other users ran into the same issue. Would it not be good for future readers, to add an explanation of =>> before the exercises? Or maybe a link to a place where it's well explained?

    ReplyDelete
  24. Why would anyone write a function of type Int -> W Int ? Why not just lift Int -> Int to W Int -> W Int using fmap ?

    ReplyDelete