On Monads, Part II

Recap

As promised, we will now talk about how we can exploit the monadic style of programming to:

  • Introduce sequentiality into an programmings environment that lack the concept of time
  • Propagate some hidden data through a sequence of expressions.

Last time, we talked about how the monadic style of programming (note that we still have not discussed what a Monad really is) can be used to transparently handle errors, by leveraging off the type system. We can also use a similar style to pass some state through, and ensure sequential evaluation of a list of expressions.

Imposing An Ordering

The whole framework of ensuring sequential evaluation of expressions revolves around the only kind of ordering we can have in stateless languages – that of data dependence. In some abstract manner, we can assert something on the lines of “x needs to be computed before x + y is computed”.

First we will talk about how we can thread some state through a list of computations. Let us, as an example, construct a scenario where we have 2 expressions, f and g, both of the type State->Value->State. We define f as:

  (defun f (state x)
    (* state x)) ;; * is some operation

and g as:

  (defun g (state x)
    (*' state x)) ;; *' is some operation

Now, we need some (general) way to combine the expressions f and g, into another expression h, such that we can put thread state through f and g. This is trivial enough to actually question its relevance:

  (defun combined (state x y)
    (g (f state x) y))

About its relevance: for one thing, this approach is close to what is used by Haskell’s IO Monad to sequence input and output operations. Secondly, it is often easier to build up complex concepts on top of simple examples.

While function composition will let us get away for now, we try to build a better (read more powerful and more general) abstraction which does the same thing, but also applies to more sticky situations. Consider something like this:

  (defun after (a b x y state)
    (b (a state x) y))

Once this is in place, we change the problem a little bit: we now have three expressions, f, g and h, which we need to sequence. We do this by:

  (defun combined (state x y z)
    (after f
           state
           x
           (after g h y z)))

With some knowledge of currying, we can see how this reduces:

  (combined state x y z)

= ((after g h y z) (f state x))

= ((defun (state)
     (h (g state y)
        z))
   (f state x))

= (h (g (f state x) y) z)

Which is exactly what we wanted. But isn’t functional programming supposed to be cleaner? Why can’t we directly go the composition way? The reason is that composing functions may not always be possible (or be clean, even if possible).

A More Involved Example

Let us try to construct a Monad (well, not really, but we’re quite close now) which allows us to solve the following problem:

You have a series of functions (expressions, computations – they all mean the same in a stateless language): f, g, h and so on. Each of these have the signature State->([Value], State) (where [Value] is a list of Values). We need to write a function combined, which runs f on an initial state, g on the derived state, and so on; and needs to build a total list of Values each function computes. Note that g need not know about the Values computed by f, h need now know about the Values computed by g and so on. It is in these kinds of problems the monadic style of programming really shines.

It is immediately obvious that a direct function composition won’t work (it works only if each function is of the type X->X). We can probably hack something up using a bunch of dbinds, but the result will be ugly. To solve this problem elegantly, we re-define after to look like the following:

  (defun after (a b)
    (dbind ((v s) a)
      (dbind ((v' s' (b s)))
        ((append v v') s'))))

Don’t let the dbind (short-form for destructuring-bind) construct confuse you, (dbind ((a b) c) body) is valid if c is a list with two elements, and assigns (first c) to a and (second c) to b in body. Also, the append can easily be implemented in a functional, stateless manner.

after takes an frobnicator (for the lack of a better term), and an expression which maps a State to a frobnicator. A frobnicator is simply a tuple (or a constant function) ([Value], State) in this case, but may be anything in general. It then takes the state of the first frobnicator, uses it to generate the second one (from the mapping), and creates a tuple (as shown above). Now, to actually use this Monad (well, this is still not the complete Monad, yet), we do this:

  (defun combined (state-begin)
    (after (f state-begin)
       (lambda (s)
         (after (g s)
           (lambda (s)
             (after (h s)
               (...)))))))

A natural question is, where does this end? It must end somewhere, since we only have a finite number of expressions we want to combine. To end this, cascading, we have another abstraction, called return (don’t confuse this with the return in imperative programming languages). We define return this way:

  (defun return (state)
    '(nil state))

Using return, the above combine becomes:

  (defun combined (state-begin)
    (after (f state-begin)
       (lambda (s)
         (after (g s)
           (lambda (s)
             (after (h s)
               (lambda (s)
                 (return s))))))))

Note that (lambda (s) (return s)) is equivalent to return in every way, and the former was used for clarity. It might make sense to use some pen and paper to visualize out how the above example actually works, even though it should not be very difficult if the previous examples were clear.

The Monad

We now define what a Monad really is. While the initial inspiration of a Monad comes from category theory, knowledge of category theory is not necessary to understand and use Monads in regular stateless functional programming languages.

A Monad consists of three things: a type constructor, a bind operation and a return operation, all three which we’ve defined above (the first implicitly, and the last two explicitly).

The Type Constructor

A monad needs a type constructor, (typically referred to as M) which maps a regular type to the concerned monadic type. A type constructor is simply an expression which constructs a new type from one or more existing types. For instance, in C, structs and unions are type constructors.

In this case, the type constructor M can be denoted by M t = ([Value], t). It will soon become clear why we made this (seemingly arbitrary) decision – the two other components impose certain restrictions on the nature of M. Note that this is a very specific monad, perhaps too specific to be useful. A better solution would have a constructor for the monadic type constructor itself, polymorphic on Value.

The Bind Operation

The bind operation is an operation (function) of the type (M t)->(t -> M u)->(M u). We have been calling this after till now. In this specific example use of the monad, t = u = State.

The Return Operation

The return operation (also named return here) maps a value into the monadic type’s unit value, where what a unit is is monad-dependent. In this case, since we’re constructing a list, it makes sense to have (nil, foo) as the unit in the monadic type system.

The above three rules are not all there is, there are also three axioms which dictate how the above constructs are to be chosen. You can look them up here. Hopefully, after reading this post, one will be able to make sense out of them.

Advertisements
This entry was posted in Computers and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s