## Monads, part 2: impure computations

July 9, 2012

### Refresher

In the last post, we learned about monads and how to use them to implement exception handling, vector operations, and debug output. To refresh your memory, a monad is defined by:

- A type constructor that defines a
*monadic type*(usually parameterized by some other type). - A
`unit`

function that takes a value and returns a value in the corresponding monadic type. - A
`bind`

operation that takes a monadic value and a function from the non-monadic type to the monadic type. It returns a value in the monadic type.

### The `IO`

monad

Today we’ll talk about how one can use monads to describe impure computations in a pure language. Let’s define a monad which represents an impure computation:

class Computation: UNIT = 0 BIND = 1 INPUT = 2 OUTPUT = 3 def __init__(self, type, data): self.type = type self.data = data def __repr__(self): if self.type == Computation.UNIT: type_str = 'Computation.UNIT' elif self.type == Computation.BIND: type_str = 'Computation.BIND' elif self.type == Computation.INPUT: type_str = 'Computation.INPUT' elif self.type == Computation.OUTPUT: type_str = 'Computation.OUTPUT' return 'Computation(' + type_str + ', ' + self.data.__repr__() + ')'

Note that we’ve defined

`__repr__`

so that we can print a computation and examine its structure. Now, let’s define `unit`

and `bind`

for this monad:def unit(x): return Computation(Computation.UNIT, [x]) def bind(x, f): return Computation(Computation.BIND, [x, f])

Okay, that’s the whole monad! Let’s rewrite some helpers:

input = Computation(Computation.INPUT, []) def output(text): return Computation(Computation.OUTPUT, [text])

We now have a way of describing computations! It’s almost like we have a programming language within a programming language. In order for this monad to be useful, though, we need a way of executing a computation. As you know by now, this is not possible in our functional subset of Python. Let’s break the rules and write just one function in imperative Python, and we’ll consider this to be part of the runtime:

def execute(computation): if computation.type == Computation.UNIT: return computation.data[0] elif computation.type == Computation.BIND: return execute(computation.data[1](execute(computation.data[0]))) elif computation.type == Computation.INPUT: return raw_input() elif computation.type == Computation.OUTPUT: print computation.data[0] return None

Sweet, let’s try it out! We’ll start with

*Hello, World*:main = output('Hello, World!')

What is

`main`

? Let’s find out:>>> main Computation(Computation.OUTPUT, ['Hello, World!'])

It’s a computation of type

`Computation.OUTPUT`

, just as we would expect. Now let’s run this computation:>>> execute(main) Hello, World!

**Sweet victory!**You can now see how monads can be used to do I/O in a pure functional language. Let me emphasize that the

`execute`

procedure isn’t written in our pure language, and it’s not referentially transparent. Rather, it is implemented as part of the runtime. The interpreter uses it to execute our program (when we call `execute(main)`

, we are basically playing the role of the runtime).### More advanced examples

Now that we understand the idea, let’s try to write some more useful programs than

*Hello, World*. First, we can try out the program from the previous example which reads a line of text and prints it back:main = bind(input, output)

This time, we get:

>>> main Computation(Computation.BIND, [Computation(Computation.INPUT, []), <function output at 0x00000000027E1198>])

And running the program:

>>> execute(main) This will get printed back! This will get printed back!

Note that I entered the first

`This will get printed back!`

, and the second one was printed by the program as we would expect.Now let’s write a program that responds to user input:

def respond(input): if input == 'yes': return output('You said YES!') else: return output('You said NO!') main = bind(input, respond)

Let’s test it out:

>>> execute(main) yes You said YES! >>> execute(main) no You said NO!

It works! Let’s modify the example so that it keeps asking the user for input until he/she says

`yes`

:def main_wrapper(dummy): return main def respond(input): if input == 'yes': return output('You said YES!') else: return bind(output('Try saying \'yes\' once in a while.'), main_wrapper) main = bind(input, respond)

Does it work?

>>> execute(main) no Try saying 'yes' once in a while. no Try saying 'yes' once in a while. no Try saying 'yes' once in a while. yes You said YES!

Sweet—recursion doesn’t seem to be a problem either. Notice how we defined

`main_wrapper`

simply because `bind`

expects a function of one argument. It turns out that this is a common monadic pattern, so let’s abstract it:def sequence(u, v): return bind(u, lambda x: v)

`sequence`

performs the computation `u`

, ignores its return value, and then performs `v`

and returns the result. Note that `execute`

must be eager when evaluating its argument. If it was lazy, the first computation (`u`

) might never get executed because the lambda expression doesn’t use it. Let’s rewrite our example using `sequence`

:def respond(input): if input == 'yes': return output('You said YES!') else: return sequence(output('Try saying \'yes\' once in a while.'), main) main = bind(input, respond)

Does it still work?

>>> execute(main) no Try saying 'yes' once in a while. no Try saying 'yes' once in a while. no Try saying 'yes' once in a while. yes You said YES!

Excellent. To conclude, let’s write a program that asks the user for two lines of input, concatenates them, and prints the result:

def respond2(input1): return lambda input2: output('You said "' + input1 + '" and "' + input2 + '".') def respond1(input1): return bind(input, respond2(input1)) main = bind(input, respond1)

And finally:

>>> execute(main) hello world You said "hello" and "world".

It works! Hopefully by now you have an idea of how to compose impure computations with monads. Let me know in the comments if anything wasn’t clear!

## Monads, part 1: a design pattern

July 9, 2012

Monad is a design pattern that allows us to redefine how function composition works. Before I define what a monad is, let’s develop some intuition with motivational examples.

### Example 1: exception handling (a.k.a. “Maybe”)

Let’s use Python to describe a function which computes the quotient of

`100`

and some divisor. In the special case where the divisor is zero, we’ll return `None`

:def divide100(divisor): if divisor == 0: return None else: return 100 / divisor

Let’s also write a function to compute the square root of a number. If the input is negative, we’ll return

`None`

: def sqrt(x): if x < 0: return None else: return x ** 0.5

Can we compose these functions? What if we wanted to compute something like

`sqrt(divide100(sqrt(x)))`

? That would work as long as `x`

is positive. If we explicitly handle the case when any of those functions returns `None`

, the code becomes much longer:a = sqrt(x) if a is not None: b = divide100(a) if b is not None: c = sqrt(b)

You can imagine how tedious it would be if we had to do manual error checking like this for all of our function calls. Perhaps a better solution is to rewrite

`divide100`

and `sqrt`

such that they each do the error handling themselves. For example, we might modify them as follows: def composable_divide100(divisor): if divisor is None or divisor == 0: return None else: return 100 / divisor def composable_sqrt(x): if x is None or x < 0: return None else: return x**0.5

Now we can evaluate expressions like

`composable_sqrt(composable_divide100(composable_sqrt(x)))`

. When `x <= 0`

, the entire expression evaluates to `None`

just as we would expect.Rather than modifying all of our functions to check for

`None`

, let’s write a wrapper function (let’s call it `bind`

) to do the error handling for us. It takes a value (either a number or `None`

) and a function (such as `divide100`

or `sqrt`

) and applies the function to that value. If the input is `None`

, we skip the function application and just return `None`

:def bind(x, f): if x is None: return None else: return f(x)

Now we can compose these functions like:

`bind(bind(bind(x, sqrt), divide100), sqrt)`

. Sweet! We have a way to compose numerical functions that might fail. You’ve essentially just implemented Haskell’s `Maybe`

monad, which is a simple form of exception handling. Let’s try some more complex examples. ### Example 2: vector operations (a.k.a. “List”)

We know that, mathematically, positive numbers have two square roots. Let’s modify

`sqrt`

to return a list of values: def sqrt(x): if x < 0: return [] elif x == 0: return [0] else: return [x**0.5, -x**0.5]

So there are three cases we have to consider. If

`x`

is positive, we return its two square roots. If `x`

is `0`

, we return `[0]`

. If `x`

is negative, we return the empty list.Great! Our sqrt function now makes more mathematical sense, at least for real numbers. But we have the same problem as in

*Example 1*—it is no longer composable with itself. We can’t just compute`sqrt(sqrt(x))`

, because the inner call to `sqrt`

returns a list, and the outer call expects a number. As before, we need to define a `bind`

function to help us with composition: def bind(x, f): return [j for i in x for j in f(i)]

Here,

`bind`

takes a list of numbers `x`

and a function `f`

. The doubly-iterated list comprehension might look cryptic—you can think of it like this: We apply `f`

to each value in `x`

, which gives us a list of lists. Then we flatten the result into one list and return it. Now we can compute the square roots of a list of numbers, and then compute all the square roots of the results: >>> bind(bind([5, 0, 3], sqrt), sqrt) [1.4953487812212205, -1.4953487812212205, 0, 1.3160740129524924, -1.3160740129524924]

It works! But our original goal was to find the square roots of

*one*number. We could always write`bind([x], sqrt)`

where `x`

is a number, maybe it would be better to use a function to abstract the representation of our input. Let’s call this function `unit`

: def unit(x): return [x]

Yep, it just puts a value into a list. It may seem unmotivated now, but we’ll write a more helpful

`unit`

function in the next example. Now we don’t have to put our input into a list—instead, we run it through `unit`

, which puts it in the necessary representation: >>> bind(bind(unit(4), sqrt), sqrt) [1.4142135623730951, -1.4142135623730951]

Cool, we can now intelligently compose functions that might return several values! That’s basically Haskell’s

`List`

monad.### Example 3: debug output (a.k.a. “Writer”)

Suppose we have some functions

`u`

and `v`

, and each function takes a number and returns a number. It doesn’t really matter what these functions are, so let’s define them as follows: def u(x): return x + 4 def v(x): return x * 2

No problem there. We can even compose them, as in

`u(v(x))`

. What if we wanted these functions to output some extra information along with their normal return value? For example, suppose we want each function to also return a string indicating that the function had been called. We might modify `u`

and `v`

like this: def verbose_u(x): return (x + 4, '[verbose_u was called on ' + str(x) + ']') def verbose_v(x): return (x * 2, '[verbose_v was called on ' + str(x) + ']')

Now we have the same problem as before, we broke composability:

`verbose_u(verbose_v(x))`

doesn’t work. By now, we know the solution to this problem is `bind`

:def bind(x, f): result, output = f(x[0]) return (result, x[1] + output)

Here,

`x`

is a tuple containing the result from another operation (such as `verbose_u`

or `verbose_v`

) and the output from that operation. We apply `f`

to `x`

to produce a new result-output tuple. The final result is the result from applying `f`

and the concatenation of the previous output and the output from `f`

. This means we can once again compose `verbose_u`

and `verbose_v`

, using `bind`

:>>> bind(bind((4, ''), verbose_v), verbose_u) (12, '[verbose_v was called on 4][verbose_u was called on 8]')

Awesome! Not only do we get a numerical result, but we also get a complete execution trace. Notice how we passed

`(4, '')`

, when all we cared about was the `4`

. The empty string means that no functions had been called at that point, but that’s an implementation detail. It would be better to write a unit function to construct this tuple for us, so we don’t have to worry about what goes in the string, the ordering of the elements of the tuple, etc. def unit(x): return (x, '')

Our example becomes:

>>> bind(bind(unit(4), verbose_v), verbose_u) (12, '[verbose_v was called on 4][verbose_u was called on 8]')

Still works! We’ve just implemented Haskell’s

`Writer`

monad! ### The pattern

In each example, we had some functions which we wanted to compose, but their type signatures were incompatible. Our functions took a value of some type and returned a value in the corresponding

*monadic*type. All we did was write a wrapper function`bind(x, f)`

, which defines the logic for how such functions can be chained together. We also defined `unit(x)`

(which is often called `return`

because of the way it is used) to convert a value into a monadic type, so it can be used with our bound functions. A monad is a type constructor, a

`bind`

operation, and a `unit`

function. In *Example 1*, the monadic type was the union of`float`

and `NoneType`

(we didn’t need a `unit`

function because the monadic type was a superset of the input type). In *Example 2*, the monadic type was`list`

(of `float`

s), and `unit`

simply put values into a `list`

. Finally, the monadic type for *Example 3*was the product (i.e., tuple) of`int`

and `str`

, so unit constructed that tuple from a value and the empty string. So the use of monads is basically a design pattern, and it’s been used to implement several concepts that are normally associated with imperative programming, such as exception handling (much like in

*Example 2*), parsers, state, collections, and I/O (as we will see shortly).### Monad axioms

Proper monads must obey three axioms so they behave the way we expect.

- Left Identity:
`bind(unit(x), f) == f(x)`

- Right Identity:
`bind(x, unit) == x`

- Associativity:
`bind(bind(x, f), g) == bind(x, lambda a: bind(f(a), g))`

(Here, equality should be taken to mean the two expressions represent the same computation.)

The first two axioms mean that

`unit`

and `bind`

roughly do inverse things: unit puts a value into a monadic container for binding and bind takes it out to apply a function. The last axiom means we can compose functions together without worrying about how composition precedence works. I’ll leave it as an exercise for the reader to prove that the versions of `unit`

and `bind`

that we wrote obey the three monad laws. ### But what about side effects?

It’s probably not obvious how we can use monads to do side effects in a pure way. But by now you understand what a monad is and how to use it to do some useful things, like exception handling, error propagation, and stack traces. We’ll talk about I/O in the next post, but keep in mind that I/O is just one of many uses of monads.

### Appendix: *do* notation

When using monads, expressions like these can become tedious to write:

bind(bind(unit(4), verbose_v), verbose_u)

Haskell uses the infix operator

`x >>= f`

to mean `bind(x, f)`

(also, `unit`

is called `return`

in Haskell). So in Haskell, it might look more like this: return 4 >>= verbose_v >>= verbose_u

Not bad. But even with this convenient syntax, it can get a little ugly (example taken from Learn You a Haskell):

Just "Hello, " >>= (\x -> Just "World!" >>= (\y -> Just (x ++ y)))

A special syntax for monads was invented for Haskell called

*do*-notation. It makes common monadic operations easier on the eyes. For example, the above expression could be written in*do*-notation like this:do x <- Just "Hello, " y <- Just "World!" Just (x ++ y)

It’s a clever syntax that makes function composition look more like an imperative program. Because it is Haskell-specific, I won’t go into details, but more information can be found here.