Monoids in Python

Francisco Mota, 09 Oct 2011

Monoids are a mathematical abstraction with plenty of applications in computer science, especially in functional programming. In the post, I will (re)introduce the concept, and then we’ll implement the concept in Python.

In math, a monoid is a set $A$ with a neutral element $\epsilon$ and an operation $(\cdot) : A \times A \rightarrow A$. We will use the triple $\langle A, \epsilon, \cdot \rangle$ to denote such a monoid.

A monoid must satisfy two properties. First, the neutral element $\epsilon$ must disappear when applied to $(\cdot)$: $$ \epsilon \cdot x = x \cdot \epsilon = x $$ Secondly, $(\cdot)$ must be associative: $$ a \cdot (b \cdot c) = (a \cdot b) \cdot c $$

Any triple $\langle A, \epsilon, \cdot \rangle$ that satisfies these properties is a monoid. Let’s look at some examples.

The natural numbers form a monoid, with addition: $\langle \mathbb{N}, 0, + \rangle$. The identity property holds: $a + 0 = 0 + a = a$. Associativity also holds: $a + (b + c) = (a + b) + c$.
The natural numbers form yet another monoid, with multiplication: $\langle \mathbb{N}, 1, \times \rangle$.
Informally, Python lists form the monoid $\langle \mbox{list}, [\ ], + \rangle$. Python tuples form the monoid $\langle \mbox{tuple}, (), + \rangle$. Python sets form the monoid $\langle \mbox{set}, \mbox{set}(), | \rangle$.

In our move to Python, we’re going to modify our definition of monoid ever so slightly. This will prove to be very useful, but keep in mind that these will no longer be monoids in the mathematical sense.

Rather than define monoids $\langle A, \epsilon, \cdot \rangle$ in terms of $A$, we’ll define them in terms of a function lift that lifts a value into the monoid. That is, if a is some value in Python, then lift(a) is a value inside the monoid. We will notate these monoids Monoid(null, lift, op), where null corresponds to $\epsilon$ and op corresponds to $(\cdot)$.

This adaptation makes sense if you consider Python’s dynamic type system. In Python, an integer might be an int, or it might just look like an int. In the spirit of duck typing, we want our monoids to work with values that look like the values we were expecting. Restricting our monoids to the set $A$ would break the spirit of duck typing.

Okay, enough talking. Let’s look at some code.

class Monoid:
    def __init__(self, null, lift, op):
        self.null = null
        self.lift = lift
        self.op   = op

    def __call__(self, *args):
        result = self.null
        for arg in args:
            arg = self.lift(arg)
            result = self.op(result, arg)
        return result

What __call__ does is it combines values inside the monoid. Let’s say we have a monoid,

monoid = Monoid(null, lift, op)

Then we have

monoid()      == null
monoid(a)     == lift(a)
monoid(a,b)   == op(lift(a), lift(b))
monoid(a,b,c) == op(op(lift(a), lift(b)), lift(c))

For example, with

intsum = Monoid(0, int, lambda a,b: a+b)

We have

intsum()           == 0
intsum(10)         == int(10)                     == 10
intsum(10, 20)     == int(10) + int(20)           == 30
intsum(10, 20, 30) == int(10) + int(20) + int(30) == 60

These kinds of monoid capture one of the essential computations in functional programming – map and reduce. The lift function corresponds to the map, and the op function corresponds to the reduce. We could define __call__ in this way:

    def __call__(self, *args):
        args = map(self.lift, args)
        return reduce(self.op, args, self.null)

This suggests that, if we have a list of integers x, we can call intsum(*x) to get their sum. But converting the list into arguments for __call__ is inefficient, so we’re going to create a method, fold, dedicated to mapping and reducing data. Then we’ll redefine __call__ by using fold.

    def fold(self, xs):
        if hasattr(xs, "__fold__"):
            return xs.__fold__(self)
        else:
            xs = map(self.lift, xs)
            return reduce(self.op, xs, self.null)

    def __call__(self, *args):
        return self.fold(args)

The only thing that should seem odd is checking for a __fold__ method in the given collection. This is just a hook that will be useful in later posts, when I define structures that can folded using monoids.

Here are a few more examples.

summ   = Monoid(0,  lambda x: x,      lambda a,b: a+b)
joinm  = Monoid('', lambda x: str(x), lambda a,b: a+b)
listm  = Monoid([], lambda x: [x],    lambda a,b: a+b)
tuplem = Monoid((), lambda x: (x,),   lambda a,b: a+b)
lenm   = Monoid(0,  lambda x: 1,      lambda a,b: a+b)
prodm  = Monoid(1,  lambda x: x,      lambda a,b: a*b)

Here, summ calculates sums, joinm concatenates strings, listm builds a list, tuplem builds a tuple, lenm calculates the length of any sequence it folds, and prodm calculates products. Actually,

summ.fold(xs)   == sum(xs)
joinm.fold(xs)  == ''.join(xs)   # almost
listm.fold(xs)  == list(xs)
tuplem.fold(xs) == tuple(xs)
lenm.fold(xs)   == len(xs)
prodm.fold(xs)  == product(xs)

Before I go, there is one more monoid I want to share. What happens when we want to apply a monoid to lists of lists of items? Use the star method to create a monoid that operates on lists of items:

    def star(self):
        return Monoid(self.null, self.fold, self.op)

We basically replace self.lift with self.fold, so when we “lift” values into the new monoid, we are actually folding these values in the old monoid.

For example,

summ.star().fold([[10, 20, 30], [40, 50]])
    == summ.fold([10, 20, 30]) + summ.fold([40, 50])
    == (10 + 20 + 30) + (40 + 50)
    == 10 + 20 + 30 + 40 + 50

I’m going to make a post on Finger Trees shortly, and the star method of Monoid will be invaluable.

The full code for this post can be found at monoid.py.

Challenges

These go from easy to hard, roughly, and are not guaranteed to have an answer.

Using only listm, how would you concatenate a list of lists. That is, how would you transform [[a, b, c], [d, e], [f], []] into [a, b, c, d, e, f]?
The reverse of a monoid is a monoid where the operator take its arguments in reverse order. Create a method, reverse, that creates a reverse monoid. What is listm.reverse()?
Are there monoids that are fixed-points of the star method? That is, is there a monoid m such that m and m.star() are indistinguishible? (Side challenge: formalize the notion of “indistinguishible”.)
Do monoids have a dual concept? Monoids, as defined here, are roughly an embodiement of “map/reduce”, which is used to process and analyze data, potentially taking a large body of data and reducing it. Is there a similar concept, a “comonoid”, that generates data, instead of reducing it?
Let lift = int, and let op return an int. Can we enumerate all possible monoids? If not, what can we enumerate?

Comments

Leave comments on the reddit submission.

« The New Fuga Model

Tiny Bloom Filter »