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.

For more informations about monoids and algebraic structures, and also about functional programming:

Constantin Liculescu


Share Button