The first part of this series generated a lot of responses, both very positive ones and very negative ones. I’m quite happy to accept that I just don’t understand monads very well, but so far, no one was able to convince me of that. One of the negative responses claimed it was not possible to actually implement monadic structures using my (simple) definition, which I took as meaning that the idea I was trying to convey was not very clear.
This second part of the series will show an application of the explanation I gave in the first part. I’ll start with a concrete problem and implement it in Python, slowly building up to the ideas encapsulated within monads. I assume you to have a good understanding of Python to be able to focus on the new concepts introduced.
Please Note: This article is not going to help you one bit if you are trying to understand monads in Haskell. The intended audience is software engineers wondering what this concept of monads is useful for in other languages, especially dynamically typed ones. Chances are that if you are trying to learn Haskell, this will do the opposite of helping. Haskell has very different needs from other languages, and uses monads very differently than I do here. Trying to apply things you learn in other languages to Haskell usually is a recipe for disaster.
Quick summary of the differences for functional programming enthusiasts which happen to come across this for some reason or other: We use methods instead of functions, so you need to subclass a monad to be able to bind new functions to it. This also means that you can not have a chain of applications without having a monadic value first. Also, we do not differentiate between the monadic value and the value stored within, as without static type systems, the difference is mostly irrelevant.
Source Code
I put the source code used below in a repository on github for easier use.
https://github.com/jorgenschaefer/monads-for-normal-programmers
Finding Monads
Let’s start with a concrete problem. What I would like is a class which encapsulates chained mathematical operations.
>>> MathOp(5)
<MathOp 5>
>>> MathOp(5).mul(2)
<MathOp 10>
>>> MathOp(5).mul(2).add(17)
<MathOp 27>
>>> MathOp(5).mul(2).add(17).sub(4)
<MathOp 23>
So far, so simple, but let’s add a twist. If there is a div(0)
anywhere in the chain, we don’t want to raise an exception, but to
have the whole chain return a NaN.
>>> MathOp(5).div(0)
<MathOp NaN>
>>> MathOp(5).div(0).mul(2)
<MathOp NaN>
>>> MathOp(5).div(0).mul(2).add(17)
<MathOp NaN>
>>> MathOp(5).div(0).mul(2).add(17).sub(4)
<MathOp NaN>
Step 1: Trivial Implementation
The first implementation of this is straightforward and simple.
class MathOp(object):
def __init__(self, value=None, is_nan=False):
self.value = value
self.is_nan = is_nan
def __repr__(self):
if self.is_nan:
return "<MathOp NaN>"
else:
return "<MathOp {}>".format(self.value)
def div(self, denum):
if self.is_nan:
return self
elif denum == 0:
return MathOp(is_nan=True)
else:
return MathOp(self.value / denum)
def mul(self, multiplicand):
if self.is_nan:
return self
else:
return MathOp(self.value * multiplicand)
def add(self, multiplicand):
if self.is_nan:
return self
else:
return MathOp(self.value + multiplicand)
def sub(self, multiplicand):
if self.is_nan:
return self
else:
return MathOp(self.value - multiplicand)
Step 2: Bind
When you look at that code, you will notice that all the methods
implementing math operations share the same test for is_nan. This
repetitive code could be abstracted out into a common pattern, maybe
using a decorator.
def mathop(method):
@wraps(method)
def math_method(self, *args, **kwargs):
if self.is_nan:
return self
else:
return method(self, *args, **kwargs)
return math_method
This lets us write the class a bit more succinctly:
class MathOp(object):
def __init__(self, value=None, is_nan=False):
self.value = value
self.is_nan = is_nan
def __repr__(self):
if self.is_nan:
return "<MathOp NaN>"
else:
return "<MathOp {}>".format(self.value)
@mathop
def div(self, denum):
if denum == 0:
return MathOp(is_nan=True)
else:
return MathOp(self.value / denum)
@mathop
def mul(self, multiplicand):
return MathOp(self.value * multiplicand)
@mathop
def add(self, addend):
return MathOp(self.value + addend)
@mathop
def sub(self, subtrahend):
return MathOp(self.value - subtrahend)
This common pattern is called bind in monad theory. If you remember my last article, I noted that bind is method application. This here now is the implementation of that idea. Bind influences how methods are applied.
To make the idea more general, we could define a bind method in our class and make our decorator call that instead.
def bound(method):
@wraps(method)
def bound_method(self, *args, **kwargs):
return self.bind(method, args, kwargs)
return bound_method
By defining the bind magic in the class itself, we can re-use this
decorator in different subclasses.
class MathOp(object):
def __init__(self, value=None, is_nan=False):
self.value = value
self.is_nan = is_nan
def __repr__(self):
if self.is_nan:
return "<MathOp NaN>"
else:
return "<MathOp {}>".format(self.value)
def bind(self, method, args, kwargs):
if self.is_nan:
return self
else:
return method(self, *args, **kwargs)
@bound
def div(self, denum):
if denum == 0:
return MathOp(is_nan=True)
else:
return MathOp(self.value / denum)
@bound
def mul(self, multiplicand):
return MathOp(self.value * multiplicand)
@bound
def add(self, addend):
return MathOp(self.value + addend)
@bound
def sub(self, subtrahend):
return MathOp(self.value - subtrahend)
This is the main part of the monad design pattern: We can abstract away some specifics related to method application by using a decorator that calls the bind method for us first.
Admittedly, the name bind is terrible, but it’s what the monad theory uses. Use something more intuitive when you actually use this pattern.
Note: It is possible to use metaclasses to make all methods of a class use bind by default. This then requires a decorator for methods that should not be passed through bind. It also adds a lot of magic which I do not think helps understanding at all.
Step 3: Maybe Monad
You can probably see that what we implemented here is again an example of a generic pattern: A chain of operations continues until a “bad” value happens, then all following operations just pass on the bad value. This is useful for mathematical operations, but it could be useful for other things, too, if throwing an exception is not a sensible solution. Some languages even implement exceptions using this pattern.
This generic pattern is called the maybe monad.
class MaybeMonad(object):
is_nothing = False
def bind(self, method, args, kwargs):
if self.is_nothing:
return self
else:
return method(self, *args, **kwargs)
We can subclass this to implement our math operation. As the
is_nothing field is now available on the class level, we can simply
define our NaN value as a subclass of MathOp. This would be a good
place for a singleton, but that’s a bit outside of the topic of this
article.
class MathOp(MaybeMonad):
is_nothing = False
def __init__(self, value):
self.value = value
def __repr__(self):
return "<MathOp {}>".format(self.value)
@bound
def div(self, denum):
if denum == 0:
return MathOpNaN()
else:
return MathOp(self.value / denum)
@bound
def mul(self, multiplicand):
return MathOp(self.value * multiplicand)
@bound
def add(self, addend):
return MathOp(self.value + addend)
@bound
def sub(self, subtrahend):
return MathOp(self.value - subtrahend)
class MathOpNaN(MathOp):
is_nothing = True
def __init__(self):
super(MathOpNaN, self).__init__(None)
def __repr__(self):
return "<MathOp NaN>"
Step 4: Monads!
So our MathOp class is an instance of a generic design pattern,
called the Maybe Monad. The same design pattern can be used for
other purposes.
A step further though, the Maybe Monad is itself an instance of an even more generic design pattern. This more generic design pattern is about the ability to chain method calls, and to override what method application does, exactly. This more general design pattern is, as you likely guessed, the Monad.
class Monad(object):
def bind(self, method, args, kwargs):
return method(self, *args, **kwargs)
def bound(method):
@wraps(method)
def bound_method(self, *args, **kwargs):
result = self.bind(method, args, kwargs)
assert(isinstance(result, Monad))
return result
return bound_method
This example code for bound enforces that the result of bind
actually is a monad itself. That’s not something we need to do in a
dynamically typed language like Python, but it highlights one of the
theoretical requirements of monads.
We can now use this meta-pattern to define our MaybeMonad.
class MaybeMonad(Monad):
is_nothing = False
def bind(self, method, args, kwargs):
if self.is_nothing:
return self
else:
return method(self, *args, **kwargs)
And in turn, we can use this MaybeMonad pattern to define the
MathOp class.
class MathOp(MaybeMonad):
is_nothing = False
def __init__(self, value):
self.value = value
def __repr__(self):
return "<MathOp {}>".format(self.value)
@bound
def div(self, denum):
if denum == 0:
return MathOpNaN()
else:
return MathOp(self.value / denum)
@bound
def mul(self, multiplicand):
return MathOp(self.value * multiplicand)
@bound
def add(self, addend):
return MathOp(self.value + addend)
@bound
def sub(self, subtrahend):
return MathOp(self.value - subtrahend)
class MathOpNaN(MathOp):
is_nothing = True
def __init__(self):
super(MathOpNaN, self).__init__(None)
def __repr__(self):
return "<MathOp NaN>"
Conclusions
In a sense, we have now created an abstraction tower.
The term monad refers to a very generic pattern about objects whose methods return monadic objects so that method calls can be chained, together with a generic way with which the application of those methods can be influenced.
Using this general pattern, we can define more specific patterns that use the general pattern for more specific purposes. The Maybe Monad is one example of this, but there are many others. These are still patterns, not concrete, useful classes, though.
We then can take this monadic pattern and create a specific class which implements this pattern and finally have something useful.
Monads are meta patterns for specific monadic structures, which are patterns for actually useful classes.
And just like with other design patterns, the important part is not that you create the full abstraction tower in your code, it’s that you use the pattern. A class that implements a singleton is still a singleton, even if it does not inherit from a singleton abstract class. A factory method is still a factory method, even if it does not implement an abstract factory method interface.
This is especially true for dynamically-typed languages, and probably the greatest source of confusion for people coming from the statically typed world. Python objects do not need a rigid type hierarchy and type checks to implement patterns that require careful consideration for the type system in other languages.
The first implementation we used here is still monadic, even though we did not make bind explicit. It’s useful to see that there is a common pattern there, but it’s not necessary to actually make this pattern explicit in your code. If you have your software engineer hat on, your goal is to create programs that solve problems, and this is the most important thing you care about.
On the other hand, if you are wearing your computer scientist hat, your focus is on analyzing the patterns in programs first, and solving real-world problems only second. This is where it becomes important to split up those patterns, to make sure you know exactly what you are talking about and how the different concepts interact.
State Monad
Let’s add some complexity. The state monad is a design pattern where you use method chaining to create a computation. The resulting computation then can be run against various inputs (initial states). This is a very handy pattern for all sorts of tasks, like creating a pattern matcher from a pattern specification or pre-computing a composable sequence of actions.
The basic idea is that we define methods in our monad instances that add computations. At the end, we call the accumulated function with an initial state. That state then is passed through the accumulated computation.
Our goal is a simple game (courtesy of haskell.org). This game is played in moves. Each move is either an a, a b, or a c. If the game is on, an a will add one point and b will deduce one point. If the game is off, neither one does anything. A c will toggle the game between on and off. The game starts in the off state.
>>> start_state = (False, 0)
>>> Game().move('a').move('b').run(start_state)
(False, 0)
>>> game = Game().move('c').move('a')
>>> game.run(start_state)
(True, 1)
>>> game.move('b').move('c').move('a').run(start_state)
(False, 0)
We can start by defining a very skeleton StateMonad class. We want
to store a computation (function), and when we’re done building the
computation, we want to run that computation on a start state.
class StateMonad(Monad):
def __init__(self, function=lambda x: x):
self.function = function
def run(self, state):
return self.function(state)
This isn’t too exciting yet. The default computation even is a real no-op, simply returning what we pass in. But we’re still looking for this generic pattern, not so much writing it down right away.
The first attempt below defines a method in move, which represents
the computation which we simply accumulate during the chaining
process. Once the game is done, we simply run the resulting game by
applying the function to the initial state.
class Game(StateMonad):
def move(self, char):
def transformer(state):
on, score = self.function(state)
if char == 'a' and on:
return (on, score + 1)
elif char == 'b' and on:
return (on, score - 1)
elif char == 'c':
return (not on, score)
else:
return (on, score)
return Game(transformer)
Each computation calls the former computation (self.function), and
adds something to its result.
The pattern you can see here is the nested method. On the first pass,
when the methods are chained, only move is called, passing in the
char parameter. On the second pass, when the resulting game function
is applied to the initial state, the inner transformer function is
called and actually does the state transition. This is a perfectly
fine solution for us, and probably all you’ll ever use in Python when
you use this kind of pattern, but as we’re looking at formalizing
design patterns, we can try and abstract this further.
The following bind implementation captures the pattern we
established above, making the code a bit cleaner:
class Game(StateMonad):
def bind(self, method, args, kwargs):
def transformer(old_state):
current_state = self.run(old_state)
new_state = method(self, current_state,
*args, **kwargs)
return new_state
return Game(transformer)
@bound
def move(self, state, char):
on, score = state
if char == 'a' and on:
return (on, score + 1)
elif char == 'b' and on:
return (on, score - 1)
elif char == 'c':
return (not on, score)
else:
return (on, score)
So far, so good. For a general pattern, though, it would be really
nice if our move method could return a whole series of transitions,
not just a single new state. But if this method can return a chained
game, then we need a state to run that returned value on.
def bind(self, method, args, kwargs):
def transformer(old_state):
current_state = self.run(old_state)
new_game = method(self, current_state,
*args, **kwargs)
new_state = new_game.run(???)
return new_state
return Game(transformer)
The ??? there can be solved by having run return two values, a value
and a state. The value is passed to the method, and the state to the
run method of the response of the game.
def bind(self, method, args, kwargs):
def transformer(old_state):
value, current_state = self.run(old_state)
new_game = method(self, value, *args, **kwargs)
new_value, new_state = new_game.run(current_state)
return new_value, new_state
return Game(transformer)
So a run of a chained game now returns two values. The first value is passed to the next method, while the second value is passed to the composed state transition functions we create within those methods.
This requires some changes. First, we change run so it returns only
the first of the tuple returned, because that’s the actual value. Then
we define a _run internal method that returns the tuple for internal
use (in bind).
def run(self, state):
return self.get().function(state)[0]
def _run(self, state):
return self.function(state)
This change has another effect, which is much more useful in languages without implicit state transitions. We can completely ignore the current state in our (bound) methods and simply pass a value to the next method. Alternatively, we can grab the current state and modify it. The ability to grab the current state and pass it to the next method as a value, or to store a value as the state, and also the ability to modify the state using a function, are generic methods we can use in all instances of this pattern.
The get method will simply discard the value it got from the last
computation and pass the current state as the value (argument) to the
next method.
@bound
def get(self, value):
cls = type(self)
return cls(lambda state: (state, state))
The put method will take an extra argument, the new_state, and
inject this as the new state in the computation, leaving the original
value intact. (Some implementations overwrite the value with some
useless value; it doesn’t matter.)
@bound
def put(self, value, new_state):
cls = type(self)
return cls(lambda state: (value, new_state))
To modify a state, we just take the last state and pass it through a function. This is very much like put.
@bound
def modify(self, value, fun):
cls = type(self)
return cls(lambda state: (value, fun(state)))
For ultimate abstraction, we can implement modify using get and
put. Using existing functionality is conceptually cleaner, albeit
possibly not more readable. Note that we define a helper function.
get passes the state as a value to the next function, where we then
modify it, and pass it to put to store it back as the state.
@bound
def modify(self, value, fun):
cls = type(self)
return cls().get()._modify(fun)
@bound
def _modify(self, value, fun):
"Modify the current state."
cls = type(self)
return cls().put(fun(value))
This leaves us with a new definition of the StateMonad.
class StateMonad(Monad):
def __init__(self, function=lambda x: (None, x)):
self.function = function
def run(self, state):
return self.get().function(state)[0]
def _run(self, state):
return self.function(state)
def bind(self, method, args, kwargs):
def transformer(old_state):
value, current_state = self._run(old_state)
computation = method(self, value, *args, **kwargs)
new_value, new_state = computation._run(current_state)
return new_value, new_state
cls = type(self)
return cls(transformer)
@bound
def get(self, value):
"Pass the current state to the next method."
cls = type(self)
return cls(lambda state: (state, state))
@bound
def put(self, value, new_state):
"Set new_state as the current state."
cls = type(self)
return cls(lambda state: (value, new_state))
@bound
def modify(self, value, fun):
cls = type(self)
return cls().get()._modify(fun)
@bound
def _modify(self, value, fun):
"Modify the current state."
cls = type(self)
return cls().put(fun(value))
The move definition in Game needs to be changed so it returns a
chain of state changes instead of simply the next state.
class Game(StateMonad):
@bound
def move(self, char):
if char == 'a':
return Game().modify(
lambda (on, score): ((on, score + 1)
if on else (on, score)))
elif char == 'b':
return Game().modify(
lambda (on, score): ((on, score - 1)
if on else (on, score)))
elif char == 'c':
return Game().modify(
lambda (on, score): (not on, score))
else:
return Game().modify(
lambda (on, score): (on, score))
But wait a moment. Now that we can return state transitions, the no-op
action at the end could be a simple empty game. And actually, the
values move returns do not depend at all on the arguments to move
anymore. That means we can abstract them out of the method and into
global or class variables.
class Game(StateMonad):
@bound
def move(self, value, char):
if char == 'a':
return ADD
elif char == 'b':
return SUB
elif char == 'c':
return SWITCH
else:
return NOOP
ADD = Game().modify(
lambda (on, score): ((on, score + 1)
if on else (on, score)))
SUB = Game().modify(
lambda (on, score): ((on, score - 1)
if on else (on, score)))
SWITCH = Game().modify(
lambda (on, score): (not on, score))
NOOP = Game()
This works.
>>> Game().move('a').move('a').move('a').get().result((False, 0))
(False, 0)
>>> Game().move('c').move('a').move('a').get().result((False, 0))
(True, 2)
What we have done in the last step is to create the state change transitions for the computation separately from creating the computation itself.
And this is the very abstract idea of the state monad.
This final implementation is so abstract that it’s unlikely to be used as is for any actual programs (in Python), but the idea of the pattern is very useful. And seeing the common operations used for this pattern is helpful in identifying when and how to use it for your programs to solve problems.