Examples

I think everybody knows some examples of Sets, let me give some anyways

• $\mathbb{N}=\{0,1,2,3, \ldots\}$ The set of natural numbers is a set.
• $\mathbb{Z}=\{0, -1, 1, -2, 2, \ldots\}$ The set of integers is a set.
• All vertices in a Graph form set, as do all edges
• $\ldots$

Haskell

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.

Examples

Take the natural numbers $X=\mathbb{N}$ and the operation $\oplus=+$ as the usual addition we all know from school. This forms a Magma because:

1. We have a Set $X$ in this case the natural numbers $\mathbb{N}$.
2. We have a binary operation $\oplus$, that is a operation that takes two inputs and returns one output, in this case $+$, and
3. 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 $X=\mathbb{N}$ again and as the operation $\oplus$ we take the minimum this time $min(x,y)$. This also forms a Magma.

1. We have a Set $X$, again the natural numbers $\mathbb{N}$.
2. We have a binary operation $min(x,y)$.
3. Independent of our choice of $x$ and $y$ $min(x,y)$ will always return a natural number.

And a third example: We take the integers as our Set $X=\mathbb{Z}$, as binary operation we take $\oplus=-$ the usual subtraction. This also forms a Magma.

1. Again we have a Set $X$ this time the Integers $\mathbb{Z}$.
2. We have a binary operation $-$.
3. Independent of our choice of elements from $\mathbb{Z}$ $-$ returns an element of the Integers.

Haskell

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 

Examples

Let’s check our three examples from above if this holds.

For the Magama $(\mathbb{N}, +)$ 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 $$(a + b) + c = a + (b + c)$$ holds for natural numbers. So $(\mathbb{N}, +)$ is also a Semigroup.

For the Magama $(\mathbb{N}, min(x,y))$ 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 $$min(min(a, b), c) = min (a, min (b + c))$$. On the left side we first take the smaller number of $a$ and $b$ 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 $a<b<c$ than $min(a,b) = a$ and therefore $min( min (a, b), c) = min (a, c) = a$ which is the same as $min(a, min (b, c))=min(a, b)=a$. You can go through the result with other relations to finally come to the conclusion that $min(x,y)$ is also associative. Which is to say $(\mathbb{N}, min(x,y))$ is also a Semigroup.

Now for our third example from above, $(\mathbb{Z},-)$. This doesn’t form a Semigroup which we can see by taking $a=7,b=6,c=5$ 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 $\mathbb{Z},-)$ is a Magma, but not a Semigroup.

Haskell

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 

Examples

Let’s see if we can find such an element for our remaining two examples of semigroups.

We already established that $(\mathbb{N},+)$ 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 $0$ satisfies exactly that. If you take any natural number and add $0$ to it you get exactly the same number back. So we have found our element $e=0$ of $\mathbb{N}$ and have that $(\mathbb{N},+,0)$ forms a Monoid.

As I already said above often times the neutral element is called $\mathbf{1}$, this is because most of the time natural numbers with multiplication so $(\mathbb{N}, \cdot, 1)$ is used as an example for a Monoid. In this case $e=\mathbf{1}=1$ where it is not that irritating. But this throws you off as soon as you take any other combination like $(\mathbb{N},+,0)$ in which case $e=\mathbf{1}=0$.

Now for our second example $(\mathbb{N}, min(x,y))$ 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 $min(x,y)$ operation, because if we select any element of $\mathbb{N}$ to be our neutral element $e$ we can find one element $x$ which is larger then $e$, in which case applying $min$ won’t yield $x$ as it would have to, but $e$. So $\mathbb{N}, min(x,y))$ can’t be made into a Monoid.

Actually we often want something with $min$ 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 $\infty$ and than say $(\mathbb{N}\cup \{\infty\}, min(x,y), \infty)$ is a Monoid. Before you ask: Yes that is cheating ;-).

Haskell

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.

Example

$(\mathbb{N}\cup \{\infty\}, min(x,y), +, \infty, 0)$ 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 $(\mathbb{N}\cup \{\infty\}, min(x,y), \infty)$ is a Monoid, as is $(\mathbb{N}\cup\{\infty\}, +, 0$) (you just have to say adding $\infty$ to anything is $\infty$, as you might have expected). Now we need to check the other properties

1. $a \oplus b=b\oplus a$ check above again $\oplus=min(x,y)$, so we need to check that $min(x,y)=min(y,x)$ but that is easy to see, I hope.
2. $a \otimes \mathbf{0}= \mathbf{0}\otimes a=\mathbf{0}$, again attention $\otimes=+$ and $\mathbf{0}=\infty$ so we have to check $a+\infty=\infty+a=\infty$, I think this you will agree this is correct, especially since I stated this to be the case above.
3. $a \otimes (b \oplus c) = (a\otimes b) \oplus (a\otimes c)$ and $(a \oplus b) \otimes c = (a\otimes c) \oplus (b \otimes c)$ this is to say $a + min(b,c) = min(a+b, a+c)$ and $min(a,b)+c = min(a+c, b+c)$ I think we agree on that too. So $(\mathbb{N}\cup \{\infty\}, min(x,y), +, \infty, 0)$ also forms a Semring. Actually Semirings using $min(x,y)$ 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.

Haskell

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

Example

In our remaining two examples of a semiring we could define the following asteration operations:

In the $(N, +, \cdot, 0, 1)$ semiring $*$ could be defined of the infinite sum $x*=1+\sum_{i}^{\infty}x$ this is not very helpful and we wont use it later on.

In the $(N\cup \{\infty\}, min, +, \infty, 0)$ semiring on the other hand $x* = 0$ satisfies our property perfectly. Just by the simple fact that $\oplus=min(x,y)$ and that the minimum of $0$ and any other number in $N\cup \{\infty\}$ will always be $0$. This is actually more useful and find it’s way into the next blog post.

Haskell

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