DEV Community

Pragmatic Maciej
Pragmatic Maciej

Posted on • Updated on

Algebraic Structures Explained - Part 2 - Magma

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 S.

Definition of the binary operation:

* : (S,S) -> S // pair of S to S
Enter fullscreen mode Exit fullscreen mode

In Haskell

(*) :: S -> S -> S
Enter fullscreen mode Exit fullscreen mode

In Elm

m : S -> S -> S
Enter fullscreen mode Exit fullscreen mode

In TypeScript

type M = (a: S, b: S) => S
Enter fullscreen mode Exit fullscreen mode

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.

Magma example

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.

Discussion (0)