Why Monoids?

I sincerely plan to explain in simple terms what's all this fuss about monoids, why we suddenly need these primitive structures, and how to make them available in Java.

A monoid is one of the simplest notions of algebra. Slightly oversimplifying, it consists of elements that have a multiplication operation a*b defined on them, and a neutral element e, such that e*a == a*e. Multiplication should be associative (a*b)*c == a*(b*c), but not necessarily commutative (a*b != b*a). If you can't imagine non-commutative multiplication, think of matrices... or of spatial rotations. The order counts.

A simpler example would consist of integer numbers and addition playing the role of multiplication. 0 is the neutral element with respect to addition, so there.

Now why would we need this structure? It turned out that if you have to add up a billion, or a quadrillion of integers, you may be interested in doing it by distributing the operation over several (or ~700 000, in the case of Google) machines. Adding up a quadrillion of integers may be not that interesting; but multiplying a billion of matrices is a different, and more challenging, story.

And why can we distribute it among the thousands of computers? We can do it all thanks to the associativity. (m₁*m₂*...*m_k1*m_k1+1*m_k1+2..*m_k2*...*m_n) is the same as

(m₁*m₂*...*m_k1)*(m_k1+1*m_k1+2..*m_k2)*(...*m_n), and we can calculate intermediate results (shown in parentheses here) on different machines, then aggregating them together; we can do it in cascade, whatever we choose. The strategy does not influence the result.

The following Java class defines, or rather declares the necessary functionality:

public abstract class Monoid<X>
{
abstract X unit();
abstract X m(X x, X y);

public X fold(Iterable<X> source) {
   X result = unit();
   for (X x : source) {
       result = m(result, x);
   }
   return result;
}

public X fold(X[] source) {
   X result = unit();
   for (X x : source) {
       result = m(result, x);
   }
   return result;
}
}

We can use it to add numbers, strings, matrices; to multiply numbers or matrices; to concatenate lists and join sets.

Monoid<Set<T>> setMonoid = new Monoid<Set<T>> {
   public Set<T> unit() {
       return Set<T>.EMPTY;
   }

   public Set<T> m(Set<T> a, Set<T> b) {
       Set<T> c = a.clone();
       c.addAll(b);
       return c;
   }

Of course using all this for the data that we have in memory of one single machine. But, as I said before, we can actually delegate the monoid's fold operation to the computing cloud, and have the list deployed somewhere in the big file system, and let the cloud partition it. The result will be the same; and all this due to the monoidal properties of our concrete classes and operations.

on Variance

I'll try to explain to practicing programmers what this variance means, and how it is related to the famous and frequently misunderstood "Liskov principle".

Say we have the following types: A, B, A1 and B1, where A1 is a subtype of A, and B1 is a subtype of B. In Java it would look like this:

class A {
  ...
}

class A1 extends A {
  ...
}

class B {
  ...
}

class B1 extends B {
  ...
}

Now let's build a class of pairs:

class Pair<X, Y> {
  X first;
  Y second;
}

If we compare Pair<A, B> ab; and Pair<A1, B1> a1b1; we see that it is natural to expect that a1b1 should be assignable to ab, but not vice versa: the components can be cast in one direction only. A1 is a specialization of A; B1 is specialization of B, and so the Pair<A1,B1> is a specialization of Pair<A,B>. This is what is called covariance: specialization transforms into specialization.

And if you are a fan of "Liskov's substitution principle", you can see that a Pair<A1, B1> can always be used ("substitute") where a Pair<A, B> is required.

Now the opposite case, contravariance. Suppose we have two functions declared like this:

  B f(A a);
  B f1(A1 a1);

(I use Java syntax; the two lines above mean that both functions return B).

Which one can replace which? See, f1 cannot be used instead of f: what if we pass something that is not A1? f1 does not know what to do with it. But the opposite is okay: we can always use f where f1 is required: any A1 can be viewed as an A.

When we deal with object methods, not just plain functions, one hidden parameter is always present: the object itself. So that a method declared as

  class A {
    ...
    C f(B b);
    ...
  }

actually is a function defined on pairs (A, B), and takes values in C. This function is contravariant in both parameters. Contravariance in the first (hidden) parameter is an essential part of OOP. Take a look at the following code snippet:

  class A1 extends A {
    ...
    C f(B b) {
      println(getClass().getName() + " called with " + b.getClass().getName());
    }
  }
  ...
  A instanceOfA = new A1();
  ...
  instanceOfA.f(b);
  ...
}

This is Java, and Java uses dynamic dispatch (that is, all methods are virtual), and so the method of A1 is called in place of method f of A. Method f of A is substituted with a method of A1; contravariance made it possible.

Note that, since a method is always contravariant on its owner object, all getters, for instance, are contravariant: a superclass can call them, and the owner object, which is an instance of a subclass, can substitute the superclass in any context.

(Many thanks to M.Abadi and L.Cardelli's "A Theory of Objects" for explaining the OOP part to me.)