### 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 `Value`s). 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 `Value`s each function computes. Note that `g` need not know about the `Value`s computed by `f`, `h` need now know about the `Value`s 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 `dbind`s, 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.

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, `struct`s and `union`s 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.

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