Magma

Magma is a big deal in functional programming.

I know this, because I have attended two study groups on functional programming, and each time someone has pulled up the Wikipedia page on Magma.

The day after the last such meeting, I spent the morning wondering whether I had made a huge mistake trying to learn a programming paradigm that required a Ph.D. in an obscure branch of mathematics in order to get started.  But then it dawned on me (I think) what it's all about:

Groups are the higher order types that higher order functions operate on.

So, a magma is a set of things (M), together with a function (.) that takes two of those things as a parameter and returns a third one.  We could start with the basic magma and build up to groups, but I would rather go backwards from abelian groups.

Abelian Groups

• The function is commutative,  so a.b = b.a
• There is an identity element, so a.I = a
• The set contains inverse elements, so for any a, there is a b such that a.b = I
• The function is associative, so a.(b.c) = (a.b).c

An example of an abelian group would be the set of integers and the addition operation.  So,

• The function is commutative,  so a + b = b + a
• There is an identity element 0, so a + 0 = a
• The set contains inverse elements, so for any a, there is a b (in this case, -a) such that a + b = 0
• The function is associative, so a + (b + c) = (a + b) + c

These are handy for higher order functions like fold.  If you wanted to fold the addition operation across a tree of integers, you just need to start with the identity (0) and add in all of the integers in any order.

But the higher order fold function cannot be used to apply any old binary operation to any old tree of values from the set that the operation applies to.  If there is no identity element in the set, then the fold function needs an additional parameter to start with.  If the function is not associative, then you will need more memory to fold over a tree, because you have to fully process each branch.

And on it goes.