As we observed in the post about equational reasoning (An exercie in equational reasoning), constructing algorithms based on laws can help us gain a lot in efficiency.

Let’s introduce a little theory first. A monoid is a pair (M,o) where M is a set and “o” (called the law of composition) is a function o: MxM -> M with the following axioms:

1. Associativity: For each x,y,z elements of M, (xoy)oz = xo(yoz).
2. Identity element: there exists in M an element e such as: e o x = x o e =x, for each x from M.

As it can be seen, associativity is a very important property and says that it doesn’t matter the order of composition for elements, because the result will remain the same. This is a very important property which leads to mathematical laws used in optimisation!

You know for sure a lot of monoids in practice, but most of the time you didn’t call them that way. Let’s see some examples:

Example 1. The set of natural numbers (N = {0,1,2,3,4,…}) is a monoid under the addition learnt in school – the identity element is 0.

Example 2. The well-known boolean set B = {False, True} forms a monoid under the laws:
AND, with the identity True (True AND x = x AND True = x, where x can be True or False);
OR, with the identity False (False OR x = x OR False = x, where x can be True or False).

Example 3. This probably is one of the most important for computing, everyone uses it when working with lists. Lists form a monoid under concatenation, and the identity is the empty list (denoted by “[]”).

Now is the moment to introduce the important notion of power.

Powers laws of monoids: In a monoid (M,o), we denote x^0 the power 0 of the element x. By convention, x^0 = e (the identity element of the monoid). We define also x^n = x o x o x … o x (the composition applied n times) and, using associativity, it’s easily seen that (x^n)^m = x^(n*m), for each n,m natural numbers. Also, it’s easisly seen that x^(n+m) = x^n * x^m.

These are two of the most important properties of monoids. We’ll employ them in finding an efficient solution for computing the exponent n of a given number x (denoted by x^n).

Let’s denote our function exp1 :: (Integer,Integer) -> Integer. The scope is to compute exp1(x,n) = x^n.

The first idea would be to use the simple law: x^n = x*x^(n-1), which becomes exp1(x,n) = x*exp1(x,n-1).
That leads us to the first program, which is very ineficient (because we have to recurse through almost all the powers of n):
> exp1 :: (Integer,Integer) -> Integer
> exp1(x,n)
>      | n == 0 = 1
>      | n == 1 = x
>      | otherwise = x*exp1(x,(n-1))

The second idea is based on the powers laws of monoids:
– if the exponent is even (n = 2m), we’ll have exp1(x,2m) = x^(2m) = (x^2)^m = exp1(x^2,m) = exp1(x*x,m)
– if the exponent is odd (n = 2m+1), we’ll have exp1(x,2m+1) = x^(2m+1) = (x^2m) * x = x * x^(2m) = x*((x^2)^m) =   x*exp1(x^2,m) = x*exp1(x*x,m)

Thus, we arrive at the program:

> exp1 :: (Integer,Integer) -> Integer
> exp1(x,n)
>         | n == 0 = 1
>         | n == 1 = x
>         | even n = exp1(x*x,m)
>         | odd n = x*exp1(x*x,m)
>             where m = div n 2;

The power of this solution is that, when the recursion step takes place, n is halved, which leads to much less steps taken for the computation of the exponential function. The halving of n was made possible by applying systematically the laws of powers in monoids, which are based on the associativity property of the composition law and the existence of the identity element. 