Functional programming newbie and something something monad something

Let me get one thing straight: I know absolutely nothing about monads. I have never intentionally used something I’ve recognised as a monad. I am dangerously unqualified to enhance your understanding of monads in any way. In fact reading this may damage you and prevent you from ever learning what a monad actually is!!!

The first reason I’m posting anything about monads at all is that I watched one of Robert “Uncle Bob” Martin’s entertaining NDC 2011 talks titled “WTF is a monad” (video available from the NDC site). I’m unsure how approximated or mathematically correct he was intending the presentation to be, but I found it really interesting and was able to implement something I can only hope was vaguely monadic based on my interpretation of the information he presented. So I thought I’d share it with you in case you could correct me (it should go without saying, but any mistakes here are mine and have nothing to do with Bob or his presentation). Worst case is it gets you interested enough to look into the topic and find out all the stuff I got wrong. (Was that alright OJ? ;))

The second reason is that I like writing words like monad, monadic, and monoid because for a brief, shining moment it makes me feel like a real computer scientist. This moment generally comes crashing down as soon as I realise I have no idea what any of these terms mean, but it is a good couple of milliseconds. :)

Did I mention I don’t know what I’m talking about? For this post especially I mean. Yes? Good, you should be safe to read on then…

Something something monad something

As far as I can gather, a monad is a structure that will let you use functions that take arguments of a certain type, and apply it to values from an another type (I’ll call this the monadic type, but I could be misusing the term). We need to be able to map back and forth between these types. Bob roughly approximates a monad to an adapter; a monad is a way of adapting one type to another.

It is the form of this adapter that makes it a monad. A monad can be expressed as two functions: the unit function, normally called return or result, that takes an argument of the original type and returns the monadic type; and a bind function that takes the monadic type and a function that works on original types. (Technically monads should also obey the monad laws. I’m sure I’ve missed other important points about them too, but let’s run with this for now.)

This structure has a few useful properties, mainly to do with being able to chain a sequence of functions that take arguments of the original type, then apply arguments of the monadic type to that chain. I think.

A dot monad?

Uncle Bob’s first example was using a monad to manipulate a dots type using functions that normally work with integers. The dots type is simply a representation of an integer using ‘.’ characters, so 5 maps to ‘…..’ and back again. We’d like to be able to be able to use dots with standard integer operations like add, so that ‘..’ + ‘…’ gives ‘…..’.

Let’s look at an example in Python:

class DotMonad:
    def result(self, i):
        return '.' * i
    def bind(self, dots, f):
        return f(len(dots))
Aside: If you haven’t used Python before, the self arguments to the functions is required due to how instance methods work in Python. You can safely ignore them for this post, but if you know C# or Java self basically becomes like this in the context of an instance method.

Here our result function just translates integers (i) into dots. The bind function takes some dots and a function f that takes an integer. First it converts dots to integers (using the length of the string of dots) then calls f using the result.

This means that if we have an add function which takes integers, we can use our monad to adapt that function to take dots.

# Integer add function
def add(a, b):
    return a+b

# Monadic add function for dots
def addM(dotsA, dotsB):
    m = DotMonad()
    return m.bind(dotsA, 
        lambda a: m.bind(dotsB, 
        lambda b: m.result(a+b)

I’ve used a and b as the plain integer types, and dotsA and dotsB to represent our monadic dots type. We can now call addM('..', '...') and get '.....'.

So how’s this work? Well remember that bind takes a dot for a first argument, and calls the function provided as a second argument after converting the dot to an int. The function we provide will be called with dotsA converted to integer a, then recursively call bind to convert dotsB in the same way. The last function in the chain is to the monad’s result method which will convert the result of a+b back to dots.

Let’s expand out and trace through the addM('..', '...') example to make sure we’ve got a handle on this:

return m.bind(dotsA,    # dotsA is '..', which is converted to int and passed to fn in 2nd arg
    lambda a:           # bind calls function with a = len('..'), which is 2 
        m.bind(dotsB,   # dotsB is '...', which is converted to int and passed to fn in 2nd arg
    lambda b:           # 2nd bind calls function with b = len('...'), which is 3 
        m.result(a+b)   # a+b is 2+3=5. m.result converts this back to '.....'

I think this is called lifting the add (+) function to work with our monad.

Lifting functions using monads

So we’ve now got a version of the basic integer add function that can work with our monadic dots type. But we’d like to be able to apply all integer functions to work with dots. In fact, we can generalise our addM function from before to lift any function which takes two arguments using a monad that can bind to that function’s argument type .

Aside: We could also generalise to support functions with any number of arguments, but I’m struggling to keep up as it is. :\ :)

def liftm(m, op):
    return lambda a,b: m.bind(a,
            lambda ax: m.bind(b,
            lambda bx: m.result(op(ax, bx))

This is pretty much identical to our addM function, but we can now do some neat stuff. Let’s import some standard Python operators and dot-erise them:

import operator

addM = liftm(DotMonad(), operator.add)
subM = liftm(DotMonad(), operator.sub)
divM = liftm(DotMonad(), operator.div)
mulM = liftm(DotMonad(), operator.mul)

#Interactive python session
>>> addM('..', '.')
>>> subM('....', '...')
>>> divM(mulM('..', '...'), subM('...', '.'))

Should we try again? Maybe…

Let’s try another monad (again, from one Bob showed in his talk). This time we’re going to try and represent a type that can either have or be missing a value as a monadic type. So something very similar to .NET’s nullable types, Nullable<T>. The difference with the monadic form is that, because of the way we chain sequences of bind operations, we can actually perform operations involving missing values without throwing null reference exceptions everywhere.

class MaybeMonad:
    def result(self, x):
        return x
    def bind(self, maybe, f):
        if (maybe is None):
            return None
            return f(maybe)

Here our result function just returns whatever value it is given. If it has a value it will return that value; otherwise it will return None (Python’s null or nil value).

Now we can lift our standard operators to work with our Maybe type:

>>> addm = liftm(MaybeMonad(), operator.add)
>>> mulm = liftm(MaybeMonad(), operator.mul)
>>> addm(2, 3)
>>> addm(4, None)
>>> mulm(6, 7)
>>> mulm(None, None)

Or we can lift null-safe versions of other functions:

def string_lens(a, b):
    return len(a) + len(b)

#Interactive python session
>>> string_lens("Hello", "World")
>>> string_lens("Hello", None)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in string_lens
TypeError: object of type 'NoneType' has no len()

>>> safe = liftm(MaybeMonad(), string_lens)
>>> safe("Hello", "World")
>>> safe("Hello", None)

Here string_lens throws when we pass in None, but our safe lifted version takes them in its stride.

Real-world monads

Monads can actually be spotted out in the wild. They particularly enjoy frolicking with pure functional languages, where they can be used for (among other things) getting around the pesky limitation of not allowing side-effects in functions. Mutable state can be simulated by passing a State monad between functions. The I/O monad is used to encapsulate the side-effects of reading and writing from input and output.

Reading through the examples in the Wikipedia entry shows some collections can even be regarded as monads (for example, result can return a list from a single item, bind can map a function to each element in a list). In some instances LINQ statements can also be used as monads. I’ve even seen JQuery accused on monadishness (yes, I just made up a word).

So where’s this leave us? If you’re like me: dazed, confused, craving a cup of tea, and also quite eager to resume working through the excellent Learn you a Haskell tutorial. :)