Demystifying Monads using Python – Part 2

A sequencing operator

In this part, I want to show that the same formalism we developed for progamming with SMFs can be used to express programs that perform I/O. But I want to do another couple of things before leaving the world of SMFs.

The first thing is to define an infix operator for sequ. To do this, we will need to create a wrapper for our SMFs. In Haskell, we can define an operator stand-alone like a function, but in Python we need a class to hang it off.

class SMF:

    def __init__(self, f):
        self.f = f
    
    def __call__(self, *args):
        return self.f(*args)
    
    def __rshift__(self, g):
        return SMF(lambda h: self.f(lambda s: g(h)(s)))

Our primitive operations now become:

add = lambda x: SMF(lambda f: lambda s: f(s | {x}))

listify = SMF(lambda f: lambda s: f(list(s))(s))

(There's an incidental benefit to introducing this wrapper. It makes explicit something that wasn't quite so obvious before: each of the functions we're sequencing is either an SMF itself or a function that returns an SMF. In Haskell, you would be able to see this from the types of the functions.)

We can now write dedup as

dedup = lambda l: (
        add(l[0]) >> dedup(l[1:])
    if l else
        listify)

Dealing with "return" values

The other thing concerns SMFs that produce a result for use by later steps in the computation. So far, the only one we've seen that does this is listify, and we only used it right at the very end. If we had tried to use it in the middle of a computation, we would have noticed a slight problem: as currently defined, our sequencing operation can't cope with that!

To see the issue more clearly, let's tackle another task. We'll write a program decadup that does the same thing as dedup, except that if it encounters a number it's already seen, it adds 10 times that number to the output list.

To do this we're going to need another primitive that tests whether a value is a member of the set. This primitive will produce a boolean result, and in accordance with the conventions we established, it will pass the result as an extra argument to its continuation.

member = lambda x: SMF(lambda f: lambda s: f(x in s)(s))

Now let's have a go at implementing decadup. We want to write something like this:

# Warning: This doesn't work!
decadup = lambda l: (
        member(l[0]) / (lambda b:
            add(10 * l[0]) if b else add(l[0]))
        >> decadup(l[1:])
    if l else
        listify)

The red part here is meant to be the continuation seen by the call to member. It receives the result from member in b and uses it to decide whether to add l[0] or 10 * l[0] to the set.

The reason it doesn't work can be seen by examining the definition of / above.

    def __truediv__(self, g):
        return SMF(lambda h: self.f(lambda s: g(h)(s)))

The red part here is the actual continuation that gets passed to member, and it doesn't expect to receive a result argument, only the state s.

The easiest way to fix this is to define a second sequencing operator that takes a result and passes it on. This operation is usually called "bind", because it binds the result to a variable for use by subsequent steps of the computation.

In Haskell the binding operator is usually spelled >>=, but that's not available to us in Python, so I'm going to use **. We add a method to the SMF class:

    def __pow__(self, g):
        return SMF(lambda h: self.f(lambda x: lambda s: g(x)(h)(s)))

The red part shows how ** differs from >>. The result is picked up in x and passed on to g.

Now we can write a working version of decadup:

decadup = lambda l: (
        member(l[0]) ** (lambda b:
            add(10 * l[0]) if b else add(l[0]))
        >> decadup(l[1:])
    if l else
        listify)

The result of run_smf(decadup, [5,4,3,6,8,2,8,4,5]) is [2, 3, 4, 5, 6, 8, 40, 80, 50].

Handling I/O

So far, the state object we've been dealing with has been an in-memory data structure. However, it's not too hard to imagine passing around an object w with methods such as print() and input() that affect the state of the world. Just as we could get away with mutating our set object in-place, we can get away with mutating the outside world in-place. We will never be in the embarrassing position of needing access to the state of the world at an earlier time, which (unless you're Guido and therefore have a time machine) is not easy to come by.

The world object might look something like this:

class World:

    def print(self, x, f):
        print(x)
        f(self)

    def input(self, f):
        x = input()
        f(x)(self)

Then we could define primitives

io_print = lambda x: IO(lambda f: lambda w: w.print(x, f))

io_input = IO(lambda f: lambda w: w.input(f))

Here, IO is assumed to be a wrapper class like SMF that provides suitable definitions of the sequencing operators.

But if you think about it a bit, we don't really need to pass the world object around, because it doesn't contain any state of its own. There could be a single global instance, or – more Pythonically – we could just turn its methods into top-level functions. Let's do that:

def world_print(x, f):
    print(x)
    f()

def world_input(f):
    x = input()
    f(x)

Now we can drop the w parameter from our primitives:

io_print = lambda x: IO(lambda f: world_print(x, f))

io_input = IO(lambda f: world_input(f))

To complete the picture, we need to supply a wrapper class. This is essentially identical to the SMF wrapper, except that there is no state parameter.

class IO:

    def __init__(self, f):
        self.f = f
    
    def __call__(self, *args):
        return self.f(*args)
    
    def __rshift__(self, g):
        return IO(lambda h: self.f(lambda: g(h)))
    
    def __pow__(self, g):
        return IO(lambda h: self.f(lambda x: g(x)(h)))

We'll also need a top-level function to run our IO programs. We can get by with something a lot simpler than run_smf, because we don't need to provide for passing in input or getting back output – our IO program will be perfectly capable of doing those things for itself. We can just fire it straight off with a final continuation that does nothing.

def run_io(f):
    return f(lambda: None)

Now we can write a test program.

greet = (
    io_print("Hi, what's your name?") >>
    io_input ** (lambda name:
    io_print("Aren't monads great, " + name + "?")))

To show that it works, here's a sample session:

>>> run_io(greet)
Hi, what's your name?
Greg
Aren't monads great, Greg?
>>>

I/O in Haskell

In Haskell, the things corresponding to our Python io_print and io_input functions are called actions. The type of an I/O action is called IO. (Technically it's IO t where t is the type of the result produced by the action.)

The Haskell equivalent of tbe greet program above would be

main = putStrLn "Hi, what's your name?" >>
    getLine >>= \name ->
    putStrLn ("Aren't monads great, " ++ name ++ "?")

This is a bit neater, because we're able to use more suggestive operator symbols, and also the grammar doesn't require putting extra parentheses around the lambda expression.

However, Haskell goes further and provides a special syntax for dealing with monads:

main = do
  putStrLn "Hi, what's your name?"
  name <- getLine
  putStrLn ("Aren't monads great, " ++ name ++ "?")

The do construct is syntactic sugar that gets macro-expanded into an equivalent expression involving >>, >>= and lambdas.

Note that Haskell doesn't provide any equivalent of our Python run_io function, nor is there any way you could write one yourself. Instead, you just define the name main to be something of type IO, and the Haskell system knows what to do with it.

A consequence of this is that all the I/O done by a Haskell program is, in a sense, at the top level. I/O actions can appear as parts of other I/O actions, but you can't embed I/O in the middle of an "ordinary" function.

What has happened here?

At this point, you might be thinking that there is some sleight of hand going on here somewhere. We started with something that was evidently purely functional, and seemingly without any abrupt transition, ended up doing I/O, which is evidently not functional!

What we have done is construct an algebra of actions. The I/O actions themselves are not functions in the mathematical sense – they don't take input as arguments and produce a result as a return value. But there's nothing wrong with that – lots of other things that functional programs manipulate are not functions, integers and strings for example.

On the other hand, the operations such as >> that we have defined on actions are functions -- they take actions as arguments and produce other actions as results. When we write something like greet we're writing a function whose return value is an action.

So we have a closed system – a set of actions, and a collection of operations that take actions and produce other actions. There is an algebraic structure to this system, so we can apply algebraic reasoning to it.

And that's one reason why Haskell programmers like monads so much – they let you perform algebra on programs that do I/O.