Consider reading first part of the series before diving into the article - Algebraic Structures Explained - Part 1 - Base Definitions
Definition of Magma
Magma is algebraic structure in a form of a pair
(S, *) where
S is a set, and
* is a binary operation over the set
S. Such binary operation that for given two members of set
S will return a third member of
Definition of the binary operation:
* : (S,S) -> S // pair of S to S
(*) :: S -> S -> S
m : S -> S -> S
type M = (a: S, b: S) => S
So for given pair will make another member of the same set.
Note Remember that we said that we will use word set and type as equivalents in this series. If you don't recall the relation go back to the first article of the series
Such operations in programming terms is of course a closed function with two arguments. So any type with such closed binary operation creates Magma algebraic structure.
Note Closed function means function which arguments and return types are the same
Magma is the loosest algebraic structure we will describe, is most general.
Every algebraic operation we know from school forms Magma, say addition or multiplication and both. But these operations have also more strict algebraic properties. One of these properties is associativity. I will be honest with you I had a lot of problem to find operation which has a lack of associativity property.
But successfully I have found one which is really nice to understand. And such Magma is known by everybody game - Rock, Paper, Scissors . Big thanks for for Mark Seemann who made that example.
[Elm] type Shape = Rock | Paper | Scissors -- sum type forms a set play: Shape -> Shape -> Shape play a b = case a of Rock -> case b of Rock -> Rock Paper -> Paper Scissors -> Rock Paper -> case b of Paper -> Paper Rock -> Paper Scissors -> Scissors Scissors -> case b of Scissors -> Scissors Rock -> Rock Paper -> Scissors
Our Magma is created by pair
(Shape, play). It fulfills all we need from Magma - we have a set, and we have binary closed function.
The last is to show that Shape Magma is not associative. Associativity is a property which is saying that grouping do not change the result. For example of such grouping we can think of parentheses in addition:
a + b + c == (a + b) + c == a + (b + c)
We know from school that addition is associative. Shape Magma is not, below the proof:
play (play Rock Scissors) Paper == play Rock (play Scissors Paper) --- evaluates to false
Changing order of execution does change the result.
What next in the series
Great. We know what is Magma in next article we will go one step further into Semigroup.
If you are interested in notifications about next articles please follow me on dev.to and twitter.
Top comments (0)