Sucker for generality
Lately, for reasons which slip my mind right now, I had to review some old library code I wrote. And as always when you review code you wrote a while ago, you think “How could I have ever thought this was good code?” Usually this is because the code contains more hacks than clean code or because you can’t even understand what that piece of code does. In this case I was quite ok with that, but could have hit myself hard for not recognising a general pattern of all distinct cases I programmed back then. This prompted me to go to:
- Rewrite the code in the more general way, reducing the code size by 30% and increasing the speed on two cases and
- Go into research mode for finding even better patterns of generalisation.
I can’t really show you the difference in 1. because I wrote the code for a project I was hired for and it’s not really open source but I decided to make a series of blog post about 2. I hope you like it.
Since I am a theoretical computer scientist and really like Haskell, probably much of these will take the form of “Applied Abstract Algebra” or “Applied Category Theory” in Haskell. Therefore I decided to do the following: Every part in this series will be divided into (at least) blog posts, the first explaining the theoretical foundations, like which algebraic/categorical structure or concept we will use, introducing some examples and some code in Haskell to use these. Subsequent blog posts will make use of the implementation and give general algorithms to solve different problems.
As this is the first blog post in the series we will start with theory. In this case Sets, Magmas, Semigroups, Monoids and Semirings.
Actually a Set in the mathematical sense is not that easy to define, there are several alternatives to do so, because the naive definition “A collection containing everything satisfying a given property” is flawed. I won’t go into that (right now). For the moment let us say a Set is a collection of things which we can consider as an object of it’s own. We dodge the question of how to form a Set and only say someone made one for us and we can work with that.
I think everybody knows some examples of Sets, let me give some anyways
- The set of natural numbers is a set.
- The set of integers is a set.
- All vertices in a Graph form set, as do all edges
In the code we will present later, we can usually assume that collection of every member of a type forms a Set, so I don’t give code for Sets here. If we really need to use Sets we can use Data.Set from the Standard Haskell Library.
A Magma or a Groupoid is probably one of the algebraic structures, almost nobody knows. A Magma is a Set equipped with on binary operation which is closed in that Set, with no further restrictions. This is so simple that everybody who has ever written a program must have seen a Magma without noticing it and probably has written something which is a Magma themself. Let’s go over this with an example:
Take the natural numbers and the operation as the usual addition we all know from school. This forms a Magma because:
- We have a Set in this case the natural numbers .
- We have a binary operation , that is a operation that takes two inputs and returns one output, in this case , and
- This operation is closed in the Set, which means, whichever two elements we select as inputs we get a element of the same Set as output.
Let’s do another example: We take the natural numbers as our Set again and as the operation we take the minimum this time . This also forms a Magma.
- We have a Set , again the natural numbers .
- We have a binary operation .
- Independent of our choice of and will always return a natural number.
And a third example: We take the integers as our Set , as binary operation we take the usual subtraction. This also forms a Magma.
- Again we have a Set this time the Integers .
- We have a binary operation .
- Independent of our choice of elements from returns an element of the Integers.
In Haskell we can make a type class for Magma by the following snippet and define the examples above as instances.
class Magma a where (<+>) :: a -> a -> a data AddMagma = AddMagma Integer data MinMagma = MinMagma Integer data SubMagma = SubMagma Integer instance Magma AddMagma where AddMagma a (<+>) AddMagma b = AddMagma $ a + b instance Magma MinMagma where MinMagma a (<+>) MinMagma b = MinMagma $ a min b instance Magma MinMagma where SubMagma a (<+>) SubMagma b = SubMagma $ a - b
Now a little more than a Magma is a Semigroup it’s again a Set with a binary operation closed in the set. But we now require a little more of the binary operation, it needs to be associative, that means whenever we take three (not necessarily distinct) elements of the Set the following must hold .
Let’s check our three examples from above if this holds.
For the Magama we have already checked that we have a Set and a binary operation closed in the set what remains is to check for associativity. I won’t formally proof that and hope you see that holds for natural numbers. So is also a Semigroup.
For the Magama we have also already checked that we have a Set and a binary operation closed in the set and have to check for associativity. Again no formal proof but a more detailed look at . On the left side we first take the smaller number of and and than compare that with c to find the smaller number among those on the right side we first find the smaller of b and c and than compare that to a to find the smallest of those two. Let’s assume the numbers are related in the following way than and therefore which is the same as . You can go through the result with other relations to finally come to the conclusion that is also associative. Which is to say is also a Semigroup.
Now for our third example from above, . This doesn’t form a Semigroup which we can see by taking and put it in $(7-6)-5=1-5=-4 \not= 7-(6-5)=7-1=-6$ so obviously this is not associative. As a result is a Magma, but not a Semigroup.
In Haskell we can’t state the property of associativity, so we can’t really give a formulation for that. In a case where we need it we would have to proof it by hand. But what we can state is the property that every Semigroup is already a Magma. This is easy to see from what we required of a Magma and a Semigroup above.
class Magma a => Semigroup a where
We come to a third structure the Monoid, which is, again, a little more than a Semigroup in this case we don’t add further restrictions to the binary operation but, require to have one distinct element from the Set which is called a neutral element or (which can be quite confusing, see below). The neutral element has the property that it does nothing if the operation is applied to it an any other element. That is to say a Monoid is a structure where is a Semigroup and for every holds.
Let’s see if we can find such an element for our remaining two examples of semigroups.
We already established that is a semigroup, so now we need to find an element which doesn’t change anything if it is added to any other number. It shouldn’t be too hard to see that satisfies exactly that. If you take any natural number and add to it you get exactly the same number back. So we have found our element of and have that forms a Monoid.
As I already said above often times the neutral element is called , this is because most of the time natural numbers with multiplication so is used as an example for a Monoid. In this case where it is not that irritating. But this throws you off as soon as you take any other combination like in which case .
Now for our second example again we already established this to be a semigroup, but now we are stuck we can’t find any element which won’t interfere with our operation, because if we select any element of to be our neutral element we can find one element which is larger then , in which case applying won’t yield as it would have to, but . So can’t be made into a Monoid.
Actually we often want something with to be a Monoid. For that we use a little trick, we add an element that by definition satisfies the property of the neutral element. We call it and than say is a Monoid. Before you ask: Yes that is cheating ;-).
Like before we can’t state the property that one or e is a neutral element in Haskell, we will have to proof that by hand, but we can at least give the structure.
class Semigroup a => Monoid a where one :: a instance Monoid AddMagma where one = 0
Disclaimer: We won’t use this code as there is already a Monoid class in the standard Haskell library in Data.Monoid.
So now for the last structure I need to introduce for the next blog post, the Semiring this time we don’t only add another restriction but we combine things we have found above. A Semiring is structure, consisting of set with two binary operations and two neutral elements such that and are Monoids and the following hold:
Ok, I see that looks complicated at first let’s try to see what it means. We already know what these Monoid thingys are, now we just have two of them that work on the same Set. That should not be to complicated. But what about these properties. You actually have encountered one example of a Semiring in school, without explicitly stated as such. The Semiring ).
Where is a Monoid, we already know that, I think you can check that is also a Monoid on your own. Now for the remaining properties:
- this simply states that I can switch the operands of the first operation which is called commutativity, you can check that this is the case with is always the same as
- in this case and is simply , so this property holds too, just check
- and you can check these with basic arithmetic, if you add two numbers and multiply them with a third number it is the same as if you first multiply the individual numbers both with third number and add the results of these multiplications.
But why are these two properties you might ask. This is simple, up to this point I never required that is the same as , so I can’t simply switch the operands around. This allows me to use more operations for the operation above. Just as an example of an operation where I can’t switch around the operands think of subtraction is obviously not the same as .
So what we just did is give a generalisation of this ) thingy and allow to use other operations than and and other Sets than . Let’s for example start by the following example
now this seems completely ridiculous, but will be very helpful in the next instalment of this series. Ok now let’s have a closer look. As already established above is a Monoid, as is ) (you just have to say adding to anything is , as you might have expected). Now we need to check the other properties
- check above again , so we need to check that but that is easy to see, I hope.
- , again attention and so we have to check , I think this you will agree this is correct, especially since I stated this to be the case above.
- and this is to say and I think we agree on that too. So also forms a Semring. Actually Semirings using and as operations have a name they are called Tropical Semirings and as I already said we will put this one to good use in the next instalment.
Again we can’t state the properties but we can write out what we basically need
class Semiring a where zero :: a one :: a (<+>) :: a -> a -> a (<.>) :: a -> a -> a data SchoolArithmatic = SchoolArithmatic Integer data Tropical = Tropical Integer | Ininity instance Semiring SchoolArithmatic where zero = 0 one = 1 (SchoolArithmatic a) <+> (SchoolArithmatic b) = SchoolArithmatic $ a + b (SchoolArithmatic a) <.> (SchoolArithmatic b) = SchoolArithmatic $ a * b instance Semiring Tropical where zero = Infinity one = 0 Infinity <+> x = x x <+> Infinity = x (Tropical a) <+> (Tropical b) = Tropical $ min a b Infinity <.> _ = Infinity _ <.> Infinity = Infinity (Tropical a) <+> (Tropical b) = Tropical $ a + b
So now I hope I haven’t confused you to much, if I have, try reading it again. If it is still unclear and you want to understand it or if you think I might have made a mistake, which is very well in the realm of possible, the comment section is your friend. If necessary I’ll update this post accordingly. Next time (not necessarily next blog post) I’ll try to put the above to good use, especially the Semiring stuff.
I have to make small addition to this post, I forgot to explain one algebraic structure the *-semiring. It is actually a just a small addition to a Semring. We add another operation which we call asteration or star () this operation has to satisfy the following property for any It is whats called a fix point operator. Depending on the setting it might e.g. work as repetition or simple be instantiated to a specific value. From this star operation we can derive another which is called plus. Plus simply omits the base case and can be defined by:
One detail we will need for the next blog post is that these operators can be defined in terms of each other. We defined in terms of . The reverse direction works as follows.
In our remaining two examples of a semiring we could define the following asteration operations:
In the semiring could be defined of the infinite sum this is not very helpful and we wont use it later on.
In the semiring on the other hand satisfies our property perfectly. Just by the simple fact that and that the minimum of and any other number in will always be . This is actually more useful and find it’s way into the next blog post.
In Haskell we can write a semiring as follows, obviously for any instance we would have to override one of the both to not fall into the trap of an infinite recursion. For the same reason I will omit a definition of the school arithmetic semiring, it simply wont finish computing anyway. However you will find the definition for the Tropical Semiring below.
class Semiring a => StarSemiring a where star :: a -> a star x = one <+> (plus x) plus :: a -> a plus x = x <.> (star x) class Starsemiring Tropical where star _ = one