Currying, Composition, and a Monad in Python

To cite Wikipedia:

In functional programming, a monad is a programming structure that represents computations. Monads are a kind of abstract data type constructor that encapsulate program logic instead of data in the domain model. A defined monad allows the programmer to chain actions together and build different pipelines that process data in various steps, in which each action is decorated with additional processing rules provided by the monad; for example a sequence of arithmetic operations can be controlled to avoid division by zero in intermediate results.

While Python is no functional programming language, it supports a functional programming style in that it among others offers use of

• list comprehensions
• first class functions
• limited anonymous functions (lambda’s in Python)

Missing is

• currying, and
• function composition
• tail call optimization
• full support of anonymous functions

However, we can do quite a few things with what is there.

Below, we will take a look at how we can simulate currying and function compositions so that we can use them to write monads. The main tool we will use is that of a “callable” class that is used to simulate true functions:

import inspect
class mycallable:
    def __init__(self, fun, nargs=None):
        '''make a callable out of fun, record number of args'''
        if nargs == None:
            if isinstance(fun, mycallable): self.nargs = fun.nargs
            else: self.nargs = len(inspect.getargspec(fun).args)
        else: self.nargs = nargs
        self.fun = fun
    def __add__(self, fun):
        '''compose self and fun'''
        f = (mycallable(fun) if not isinstance(fun, mycallable) else fun)
        return mycallable(lambda *args: self(f(*args)), f.nargs)
    def __call__(self, *args):
        '''do the currying'''
        if len(args) == self.nargs: # straight call
            return self.fun(*args)
        if len(args) == 0: # f() == f when arity of f is not 0
            return self
        if len(args) < self.nargs: # too few args
            return mycallable(lambda *ars: self.fun(*(args + ars)),
                              self.nargs-len(args))
        if len(args) > self.nargs: # if l x,y:x+y defined as l x:(l y:x+y)
            rargs = args[self.nargs:]
            res = self.fun(*(args[:self.nargs]))
            return (res(*rargs) if isinstance(res, mycallable) else res)

This allows us to write things like:

f = mycallable(lambda x,y : x + y)
h = mycallable(lambda x: x**2)
(h + f)(1)(2)  # h(f(1)(2)) == 9
(h + f)(1,2)   # h(f(1,2))  == 9

Note that the above does not work with keyword arguments, I’ll leave that as an exercise to the reader ;)

As an example of what we could use currying and composition for, we define some standard functional programming tools:

fold = mycallable(lambda f,i,s: (f(s[0],fold(f,i,s[1:])) if s else i))
cons = mycallable(lambda a,l : [a] + l)
map  = mycallable(lambda f: fold(cons + f, []))

In particular, the last definition is interesting in that it is a partial application of a fold.

Now assume we have two functions f and g such that both, in addition to the result, return a string explaining what they did. For example

f = lambda x : (x + 2, 'f added 2 to %d' % x)
g = lambda x : (x**2,  'g raised %d to the power of 2' % x)

each return a string together with the result. What we would like to do is to compose the functions as

(f + g)(2)

and get something like (6, ‘g raised 2 to the power of 2. f added 2 to 4.’). The problem is that f expects an integer as argument and not a (integer, string) tuple. What we want as result is (fgx, gs + fs) where

(gx, gs) = g(x)
(fgx, fs) = f(gx)

This can be achieved by

fadapted = lambda f, (gx, gs) : ((lambda (fgx, fs): (fgx, gs + fs))(f(gy)))
(fgx, fgs) = fadapted(f, g(x))

where fadapted(f) is the “adaptation” of f to accept a (gx, gs) tuple, and return (f(gx), fs + gs).

How can we automate this pattern so that we can chain together multiple functions? One answer is to define a writer callable:

class writer(mycallable):
    '''the writer plumber'''
    def __add__(self, fun):
        return writer(writer.bind(self) + fun)
    def __call__(self, *args):
        res = mycallable.__call__(self, *args)
        return res if not isinstance(res, mycallable) else writer(res)

where

writer.bind = mycallable(lambda fp,(gx, gs):(
    lambda(fgx,fs):(fgx,gs+' => ' +fs))(fp(gx)))

does the adaptation. Note that writer.bind as defined above can be called with only the first argument fp returning curried function expecting a (vaue, string) tuple as input. This function can then be composed with any function that returns such a tuple.

We can now chain together functions (writer sub-type callables) that are of the right kind, i.e., they return a (value, string) tuple. We would however like to avoid having to re-implement all library functions in order to implement this type of “logging.” We can do this by wrapping any function that returns a value only in such a way that it returns a (value, string) tuple instead. This way we “lift” the function into the class of writer type functions. We can do this by:

writer.unit = mycallable(lambda x : (x, 'lifted returns ' + str(x)))
writer.lift = writer(lambda f : writer(writer.unit + f))

Then,

h = writer.lift(lambda x : x*x)

is the ‘lifted’ version of lambda x : x*x, and can be composed with f and g as

(h + f + g)(5)

which returns

(729, 'raised 5 to the power of 2 => added 2 to 25 => lifted returns 729')

Note that we did not choose the names bind, unit (also called return), and lift arbitrarily, as they are standard names of what makes up a monad. In fact the writer callable is a monad, and it is usually known as the writer monad. To learn more about monads, check out any of the monad tutorials linked to here.