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:

**Associativity:**For each x,y,z elements of M, (xoy)oz = xo(yoz).**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:

- You can read this very beautiful article of Bartosz Milewski: Free Monoids.
- You can read Graham Hutton’s: Programming in Haskell.
- You can read Richard Bird’s: Thinking Functionally with Haskell.

## Leave a Reply