Good Math, Bad Math

Time for more monads. In this article, I’m going to show you how to implement a very simple
state monad – it’s a trivial monad which allows you to use a mutable state
consisting of a single integer. Then we’ll expand it to allow a more interesting
notion of state.

Let’s get the trivial stuff out of the way. To start off, we’ll use a simple fixed
state type which is just a wrapper for a single integer


>data State = State Int deriving (Show)

A monad over that would be written:

	
>data SimpleStateMonad a = SSMon (State -> (a,State))

To understand that, just remember that the monad is really a transition function for
executing a sequence of computations that use a state. In fact, we’ll describe the sequence of steps
chained together that way as a single monad operation as a monadic sequence. In a monadic sequence, each step of the computation is going to take the current state, do something with it, and return both a value and an updated state.

Given the monad type – the basic type of the step function for the sequences we want to build – the first thing that we need to do is implement the fundamental monadic operators. There are two of them: the sequencing operator (>>=), and the return function that brings a non-monadic value into a monad.

We’ll implement the (>>=) operator, which we’ll implement as a function named chain:


>chain :: (SimpleStateMonad a) -> (a -> SimpleStateMonad b) 
>          -> SimpleStateMonad b
>chain (SSMon state) stepfun =
>      SSMon (\s -> let (carried, stateBefore) = state s
>                       SSMon stateMonadAfter = stepfun carried
>                   in stateMonadAfter stateBefore)

The way that chain works is crucial, and so we’ll take some time and tease it apart. Chain is a function that takes the result of the previous computation step of the sequence, and
chains it into the next step of the sequence. The way to understand the code is to look at the basic
pieces, and how they’re put together:

  • The first binding of the let: (carried,stateBefore) = state s. This looks
    mysterious – so we’ll take the time to look at it carefully. state is the
    function inside of the monad that carries hidden monadic state and the result of the previous
    step. So all we’re really doing here is unwrapping the results of the previous step – extracting the state and the return values, and binding them to separate variables. carried is the result of the previous step, and stateBefore is the
    state returned by the previous step – that is, the state before we chain in
    the next step of the monadic sequence.
  • The second binding of the let: SSMon stateMonadAfter = stepfun carried. Again,
    it looks mysterious, but it’s really pretty simple. The monad is a step function – we’re
    creating a step function from the result of the previous step, so that we can
    use that to run the next step. stepfun carried is just a function which
    passes the state and return value of the first step into the second step of our
    chain.
  • The main expression of the let: stateMonadAfter stateBefore. This just
    runs the step function we generated on the result of the previous step.
  • The λ wrapping the whole shebang: monads are a bit of a trap – you don’t
    get to get out of them without using a type-specific operation that isn’t part of the
    monad class. The monadic chain operator needs to result in a monad value – the wrapping
    lambda expression just encapsulates the stepping sequence we’ve built into a monadic
    function wrapper.

Return is trivial, so we’ll just write it inline in the declaration of our monad type as an instance of the monad typeclass. The typeclass declaration looks like:


>instance Monad SimpleStateMonad where
>    statemonad >>= statefun = chain statemonad statefun	
>    return nonMonadValue = SSMon (\state -> (nonMonadValue, state))

Nothing complicated there. The next thing we need to do is to write some functions usable
inside of a monadic computation to access and update the state hidden inside the
monad. Let’s start with retrieving the state value:

	
>getState :: SimpleStateMonad Int
>getState = SSMon (\s@(State i) -> (i,s))

That’s it! It’s just a monadic step function that takes the value hidden in the state,
and puts it into the “return value” slot of the monad result. So the monadic state is
unmodified, and the result passed to the next state is the value that was wrapped up in the monad.

Updating is almost as easy:


>putState ::  (Int -> Int) -> SimpleStateMonad ()
>putState updateFun = 
>     let stateUpdateFun = (\(State i)  -> State (updateFun i)) 
>     in SSMon (\s -> ((), stateUpdateFun s))

putState takes a function that performs a modification of the state value. Since
we want people to treat the state as an integer, we do a little bit of wrapping, to translate an Int -> Int function to a State -> State function. The real meat is just
executing the state update function to produce the new state value, and wrapping it up in a monad
that returns the unit value and the updated state.

Finally, we need a function that takes an initial state value, and a monadic sequence of operations, and executes the monadic sequence starting with the state value.

		
>runWithState :: Int -> SimpleStateMonad a ->  (a,State)
>runWithState f (SSMon c) = c (State f)

And voila! We have a state monad. Let’s try a simple test of it. Here’s
a monadic sequence that plays with the state a bit.


>testState :: SimpleStateMonad Int 
>testState = do
>	           putState (3*)
>	           putState (1+)
>	           i <- getState
>	           return (i+2)

Running that in GHCI gives us:

 *Main> runWithState 3 testState 
(12,State 10) 
*Main> runWithState 10 testState (33,State 31)
*Main> 

I ran it twice, with different values for the initial state. The code takes whatever the initial
state is, multiplies it by three, and adds one. That’s the final value of the state. And then the do
block finishes with a value of the current state plus two. What’s actually returned at the end of the
do block is a pair of the return value of the last statement in the block, and the final state. As you can see, it does exactly the right thing. It looks almost like a piece of imperative code,
except that the “assignment” operator, putState takes a function on the current
value of the state instead of just a new value.

So, now we’ve seen the basic method that we can use t make a monad that can encapsulate a kind of
state. But so far, it’s a pretty trivial kind of state: how much good is one integer? Suppose we
wanted something more than that. In fact, suppose we wanted an arbitrary set of named variables
encapsulated in a state. We do almost the same thing as the simple state monad; we just use a more
complicated value inside the monad, and a different set of functions for working with the value in
the state. We’ll start by just building a trivial non-monadic implementation of a name/value
list.


>type NameValueMap = [(String,Int)]
>	
>getValueFromList :: NameValueMap -> String -> Int
>getValueFromList ((n,v):rest) name 
>             | n == name = v
>              otherwise = getValueFromList rest name
>getValueFromList [] name = -1
>
>setValueInList :: NameValueMap -> String 
                    -> Int -> [(String,Int)]
>setValueInList ((n,v):rest) name newval 
>          | n == name = ((n,newval):rest)
>          | otherwise = ((n,v):(setValueInList rest name newval))
>setValueInList [] name newval = [(name,newval)]

Now, we’re going to wrap that as a monad. The declaration of the monad type
and the chain and return functions are going to be essentially identical to the integer
state monad.


>data MapStateMonad a = MapMon (NameValueMap -> (a,NameValueMap))
>
>mchain :: (MapStateMonad a) -> 
>          (a -> MapStateMonad b) -> 
>          MapStateMonad b
>mchain (MapMon state) stepfun = 
>        MapMon (\s -> let (carried, stateBefore) = state s
>                          MapMon stateMonadAfter = stepfun carried
>                      in stateMonadAfter stateBefore)
>
>
>instance Monad MapStateMonad where
>    statemonad >>= statefun = mchain statemonad statefun	
>    return nonMonadValue = 
>            MapMon (\state -> (nonMonadValue, state))

Here’s where we do something a little bit different. Instead of having “getState” and “putState” functions for working on the state in the monad, we need operations that fit the new name-map state.


>getFromState :: String -> MapStateMonad Int
>getFromState name = 
>      MapMon (\statemap -> (getValueFromList statemap name, 
>                            statemap))
>
>setInState :: String -> Int -> MapStateMonad ()
>setInState  name newval = 
>       MapMon (\statemap -> 
>                   ((), 
                    setValueInList statemap name newval))

And, just as in the case of the simple integer state monad, we need a way of running a monadic sequence with a particular initial state. And while we’re at it, we’ll write a test sequence.


>runWithMapState :: NameValueMap -> 
>                   MapStateMonad a ->  
>                   (a,NameValueMap)
>runWithMapState f (MapMon c) = c f
>
>testMapMonad = do
>                  setInState "x" 3
>                  setInState "y" 5
>                  z <- getFromState "a"
>                  x <- getFromState "x"
>                  return (x*z)

Now, aside from a bit of syntax, that looks like an imperative program, doesn’t it? Except that we’ve implemented it in a pure functional way – using a hidden state parameter. That’s the basic idea of what we do with monads – they allow us to create mini-languages with different
semantics based on the idea of chaining things together into monadic sequences. We write most of the program in the general functional language; but when we need to, we have multiple custom languages at our disposal in the form of the monad system. We can easily use monads for IO, for imperative programming, for Prolog-style backtracking, for non-determinism… All there, in Monads.

Next up, we’ll look at the theory of monads: what they are in category theory, and how that relates to what we’ve seen in programming, and what rules are required by the monadic semantics to make a new monad work correctly.

Comments

  1. #1 Neil Bartlett
    January 29, 2007

    Hi Mark,

    Really good post, thanks. But please, please, could you make your blog posts a little bit more print-friendly? This one is particularly problematic, because the wide code samples have pushed the content of the post below all the ads and banners and navigation bars and search bars and links and more ads and yet more ads ;-)

    In fact this is simply unprintable in IE – I get half a page of truncated content and then 7 pages of gunk. Maybe Firefox will work better…

    Regards
    Neil

  2. #2 Mark C. Chu-Carroll
    January 29, 2007

    Neil:

    Sorry about that; I keep forgetting about how the side-banners can interact with page formatting if I’m not careful. I just did a quick edit to reformat so that the code should not overflow into the banners in a normal-sized window – is it better now?

  3. #3 Neil Bartlett
    January 29, 2007

    It’s a little better, in that I can now read the first 90% (or thereabouts) of each line of text. Generally I can infer the rest.

  4. #4 Xanthir, FCD
    January 29, 2007

    I regularly have problems viewing GM in my IE-derived browser. I get the same problems with, say, Pharyngula whenever PZ quotes something. However, it always appears perfectly for Firefox.

    My guess is that Scienceblogs doesn’t give a damn about IE’s retarded quirks, and just throws out proper code so that browsers which know what the hell they’re doing can render it appropriately.

  5. #5 Brent
    January 29, 2007

    just remember that the monad is really a transition function for executing a sequence of computations that use a state.

    When I read that sentence, suddenly everything made sense! =)

  6. #6 Joe Jones
    January 29, 2007

    A couple errors in the post when trying to use it in a literate haskell file:

    > otherwise = getValueFromList rest name

    should be (missing bar)

    > | otherwise = getValueFromList rest name

    and

    >setValueInList :: NameValueMap -> String
    -> Int -> [(String,Int)]

    should be (missing > at beginning of statement)

    >setValueInList :: NameValueMap -> String
    > -> Int -> [(String,Int)]

  7. #7 Justin
    January 29, 2007

    Good article overall – the parallels between the initial State monad with an Int and the next with a NameValue pair make it obvious there is a generalization coming – at least I hope there is!

    However, in the first portion, I think you should really emphasize that state is a function, and the signature is (State -> (a,State)) – from the SSMon constructor. Showing that connection would help make chain a bit clearer.

  8. #8 Rev. BigDumbChimp
    January 29, 2007

    OT but the uber power shell left out of the Vista release is called “Monad”.

    and that’s all my non-math brain can add

  9. #9 Pseudonym
    January 30, 2007

    As Mark will no doubt mention next time, “monad” in this sense is a conflation of the words “monoid” and “triad”. The term comes from category theory, where a monad is a kind of generalisation of a monoid.

    The Vista shell thingy takes its name directly from philosophy. Wordnet defines it as “a singular metaphysical entity from which material properties are said to derive”. I think they’re reaching a bit.

The site is currently under maintenance and will be back shortly. New comments have been disabled during this time, please check back soon.