Monads by Motivation

My background (long, long ago) is in functional programming.  Back in the 80s and early 90s, there were no monads, but there was a lot of research into how to make state easier to deal with in functional programs.  I did some of that research.

After I had left University and gone out into the real world, my supervisor sent me a couple of Phil Wadler's papers introducing the idea of monads.  The idea seemed genius, but the presentation put me off.  Because I've not really done anything more with pure functional languages over the years, I've never really wrangled with monads.  And thus I've never really understood them.  I've even regretted over the years not studying Category Theory when I was an undergraduate, on the grounds that that might have helped.

A friend recently pointed out that maybe I was just all too theoretical on the subject and maybe I should just try and "use" monads.  I demurred, on the grounds that I like to understand what it is I'm doing, but then I went to Liam Griffin-Jowett's talk on "the bank kata in Haskell" and realized that he was just assuming practical knowledge of monads in order to solve a problem.  And in following along, I felt I learnt a lot about monads - but not enough.

So, here, now, I'm going to try and put two and two together for the first time, and I'm going to do it by winding back the clock to 1990, declaring that monads don't exist and building a cafe loyalty card in a pure functional language.  I'm going to use Haskell rather than Miranda, because that's what we do these days, and it will make the transition easier.

First off, make sure you have Haskell installed.

Secondly, if you want to follow along with code, you'll want my code which can be downloaded from github:

$ git clone git@github.com:gmmapowell/ignorance-may-be-strength.git

OK, let's get started.

A simple, purely functional, loyalty card

Let's consider a simple loyalty card - you know, the ones that you collect in coffee shops and have 10 pictures of coffee beans on them.  Every time you go, you receive one stamp.  When the card is full, you can have a free coffee and start again.

In Haskell, we can represent such a card quite simply:

data Loyalty = Card Int

And we can fairly easily represent the act of stamping a card like so:

stamp (Card n)

 | stamped < 10 = ("You have " ++ (show stamped) ++ " stamps", Card stamped)

 | otherwise    = ("You have earned a free beverage", Card 0)

 where
  stamped = n+1

This takes a card and returns a pair - a message about the new state of the card and either an updated card, or a brand new one if the free beverage was earned.

So far, so good.

Visiting more than Once

Assume that Adam and I go for coffee and he collects both stamps.  Using the definition above, that's easy, right?  We just do:

stamp (stamp (Card 0))

Except when we do this, we see the following:

   • Couldn't match expected type ‘Loyalty’

                 with actual type ‘([Char], Loyalty)’

   • In the first argument of ‘stamp’, namely ‘(stamp (Card 0))’

     In the expression: stamp (stamp (Card 0))

     In an equation for ‘it’: it = stamp (stamp (Card 0))

The problem here is that we are returning both a message and the "current card" but when we go to apply the second stamp, stamp is only expecting a card to be passed in. We can work around this by pulling apart the pair and then returning a list of messages together with the final card, but this is starting to look ugly.

stampTwice c =

  ([msg1, msg2], card)

    where

      (msg1, tmp) = stamp c

      (msg2, card) = stamp tmp

Fundamentally, this is a problem of composition.  What we want to be able to do is to create a function stampTwice which can either be defined intuitively as the earlier (failing) example or using the compose operator as

stampTwiceC = stamp . stamp

I know function signatures can quickly get out of hand, and never more so than when composing functions, but let's look at this in a bit of detail.  The simplest function signature is always a->b, and thus the simplest signature for compose is going to be (b->c)->(a->b)->(a->c).

In (almost) plain English, this is a function which takes two functions and returns a function.  The input of the returned function is the same as that accepted by the second function (which is actually applied first); its return type will be the same as that of the first function; and the return type of the second function must match the input type of the first function.  Again, so far, so good.

Our problem here is with that last clause.  Our first function is returning the tuple (String, Card) and the second function is expecting just a Card.  We somehow need to use sleight of hand to pass the card from one invocation to the next while collecting up the messages.

Card/0

stamp

1 stamp

Card/1

stamp

2 stamps

Card/2

A Composition Function of our Own

Of course, as any good computer scientist would tell you, there's more than one way to break down a problem - and more than one way to hide the complexity.

For me, one of the great things about Functional Languages has always been the cunning use of nested functions, helper functions, scopes and recursion to keep on moving the complexity off until it turns out it was never there in the first place: it's just a graph of obvious and simple steps.

But we have the ability here to shunt off some of the complexity by extracting stamp from the definition above.  Quietly doing a small amount of concomitant renaming, we suddenly have:

composeState :: (c -> (b, d)) -> (a -> (b, c)) -> (a -> ([b], d))

composeState f g x =

  ([r1,r2], state)

    where

      (r1, tmp) = g x

      (r2, state) = f tmp

This appears very similar to the above, but is in fact a composition function that takes two arbitrary functions which return tuples; the first element of the two tuples must be composable in a list, and the second arguments follow the same pattern as compose.

Applying this more general function to stamp and stamp behaves like so:

*Main> composeState stamp stamp (Card 0)

(["You have 1 stamps","You have 2 stamps"],Card 2)

Monads are all about Composition

Avid monad spotters will by now have noticed what we've done (of course, I wouldn't expect an avid monad spotter to be reading a basic introduction to the topic like this).  We've recreated the State monad, albeit in a weird, limited and ugly form.

This is in fact, the very purpose of a monad.  Monads are all about composition.  Monads exist precisely to solve problems like this by wrapping up and "hiding" some ugly portion of the processing while allowing the "user" code to focus on the desired interactions - in this case the action of stamping cards and informing users how their rewards are stacking up.

So let's have a quick look at how we would do this in Haskell using the real State monad.

stampm :: State Loyalty String

stampm = do

  card <- get

  let (msg, next) = stamp card

  put next

  return msg

*Main> evalState ((++) <$> stampm <*> stampm) (Card 0)

"You have 1 stampsYou have 2 stamps"

You are probably thinking right now, "that looks pretty complicated and what does half of it mean?"; and you'd be right.  But that's often the way with computer science solutions: for a simple example, the more general solution is more complex than a more specific solution.  The payback comes as the system grows and you are only interested in the interactions, not the plumbing.

In future episodes, we'll come back (again and again) to the topic of monads, exploring what this means, what you can do and why it all works.