DEV Community

loading...

Monoids (and semigroups)

Sam A. Horvath-Hunt
https://samhh.com
・3 min read

This post contains examples written in Haskell and TypeScript (fp-ts).

Semigroups and monoids are mathematical structures that capture a very common programmatic operation, the reduction of multiple elements into one. Formalisms like this enable us to create and utilise otherwise unobtainable abstractions, and signal to other developers our intent with common language.

To understand monoids, we must first begin with semigroups.

Concatenation

Semigroups formally define how to concatenate together two items of the same type. For example, arrays are semigroups:

[1, 2] <> [3, 4] -- [1, 2, 3, 4]
Enter fullscreen mode Exit fullscreen mode
[1, 2].concat([3, 4]) // [1, 2, 3, 4]
Enter fullscreen mode Exit fullscreen mode

You could equally define a semigroup instance for numbers under addition and multiplication, or for booleans under conjunction and disjunction. If the underlying mathematics interest you, you can read more about semigroups on Wikipedia.

What’s more interesting is the ability to define semigroups for arbitrary types that we’ve defined. Let's imagine we have the type Cocktail, and we want to be able to combine any two of them together. Given a definition for the type as follows:

data Cocktail = Cocktail
    { name :: String
    , ingredients :: [String]
    }
Enter fullscreen mode Exit fullscreen mode
type Cocktail = {
    name: string;
    ingredients: string[];
};
Enter fullscreen mode Exit fullscreen mode

We can then define a formal semigroup instance which will allow us to combine any pair of cocktails together:

instance Semigroup Cocktail where
    a <> b = Cocktail (name a <> " " <> name b) (ingredients a <> ingredients b)

mojito = Cocktail "Mojito" ["rum", "mint"]
robroy = Cocktail "Rob Roy" ["scotch", "bitters"]

combined = mojito <> robroy
-- Cocktail { name = "Mojito Rob Roy", ingredients = ["rum", "mint", "scotch", "bitters"] }
Enter fullscreen mode Exit fullscreen mode
const semigroupCocktail: Semigroup<Cocktail> = {
    concat: (a, b) => ({
        name: a.name + ' ' + b.name,
        ingredients: a.ingredients.concat(b.ingredients),
    }),
};

const mojito: Cocktail = { name: 'Mojito', ingredients: ['rum', 'mint'] };
const robroy: Cocktail = { name: 'Rob Roy', ingredients: ['scotch', 'bitters'] };

// { name: 'Mojito Rob Roy', ingredients: ['rum', 'mint', 'scotch', 'bitters'] }
const combined = semigroupCocktail.concat(mojito, robroy);
Enter fullscreen mode Exit fullscreen mode

And just llike that we can combine our types together! Of course, we could just define a function for concatenating these two particular types together without the semigroup formalism, but that’d be both less obvious at a glance to developers familiar with this mathematical terminology, and less likely to be reusable in common abstractions; you’d have to rely upon duck typing and couldn’t rely upon adherence to any laws. Speaking of which, utilising the semigroup type class implies adhering to the law of associativity, something common in mathematical and functional abstractions that allows the consumer to make useful assumptions.

Fun fact: If your (attempted) semigroup instance isn’t associative, then it is in actual fact a magma! Although it does exist in the type class hierarchy, it’s exceptionally rare to define a magma that’s not associative thus not also a semigroup.

Identity

We now know how to combine things, but what about if we mightn’t have anything? For such circumstances we can define a monoid, which is simply a semigroup with an identity element.

An identity element is a value for a type which, combined with another of its type, results in no change to said other. For example, the identity for strings is '', for numbers under addition 0, for numbers under multiplication 1, for booleans under conjunction true, and so on.

The identity element for arrays is an empty array. See how when we apply this identity element to any given array we always get said array back again unchanged:

[1, 2] <> [] -- [1, 2]
[] <> [1, 2] -- [1, 2]
Enter fullscreen mode Exit fullscreen mode
[1, 2].concat([]) // [1, 2]
[].concat([1, 2]) // [1, 2]
Enter fullscreen mode Exit fullscreen mode

What about our Cocktail type from earlier? Given the two fields are each already monoids, this will be quite simple:

instance Monoid Cocktail where
    mempty = Cocktail mempty mempty
Enter fullscreen mode Exit fullscreen mode
const monoidCocktail: Monoid<Cocktail> = getStructMonoid({
    name: monoidString,
    ingredients: A.getMonoid<string>(),
});
Enter fullscreen mode Exit fullscreen mode

And just like this we can combine any arbitrary number of cocktails:

mconcat []               -- Cocktail { name = "", ingredients = [] }
mconcat [mojito]         -- Cocktail { name = "Mojito", ingredients = ["rum", "mint"] }
mconcat [mojito, robroy] -- Cocktail { name = "Mojito Rob Roy", ingredients = ["rum", "mint", "scotch", "bitters"] }
Enter fullscreen mode Exit fullscreen mode
fold(monoidCocktail)([])               // { name: '', ingredients: [] }
fold(monoidCocktail)([mojito])         // { name: 'Mojito', ingredients: ['rum', 'mint'] }
fold(monoidCocktail)([mojito, robroy]) // { name: 'Mojito Rob Roy', ingredients: ['rum', 'mint', 'scotch', 'bitters'] }
Enter fullscreen mode Exit fullscreen mode

This is equivalent to reducing over an array of items using the semigroup concatenation operation as the function and the monoidal identity element as the starting value.


This post can also be found on my personal blog:
https://www.samhh.com/blog/monoids-semigroups

Discussion (3)

Collapse
sshine profile image
Simon Shine

This Semigroup instance breaks the semigroup laws, since

λ> mempty <> mojito
Cocktail {name = " Mojito", ingredients = ["rum","mint"]}

λ> mojito <> mempty
Cocktail {name = "Mojito ", ingredients = ["rum","mint"]}

If you want to fix this, consider making this a commutative monoid:

λ> (mojito <> robroy) == (robroy <> mojito)
...

...although I think sufficiently advanced drinks are not commutative because of chemistry.

Collapse
samhh profile image
Sam A. Horvath-Hunt Author

You're right, I cheated a little bit there!

Collapse
sshine profile image
Simon Shine • Edited

I don't think that cheating is a thing.

Also, thanks for making my new go-to example of a monoid a cocktail.

I have been using soup and tango for a while, and people don't seem to relate.

Another thought on the monoidal properties of cocktails: You may want a multiset / bag rather than a set of ingredients, since an important property of a cocktail is how many parts of each ingredient go into it.

I ended up writing a bit about it here. :-D