# Fantas, Eel, and Specification 4: Semigroup

13 Mar 2017Today, after a moment of thanks to all those following this series (seriously, *thank you* ♥), we can move onto a question that has occupied human thought for aeons: how do we generalise the process of combining (or mooshmashing) things together? With **semigroups**, of course!

Now, just as with `Setoid`

, we’ll get methods and laws out the way now so that we can move on to fun things. Luckily, there’s only one of each! A valid `Semigroup`

must have a `concat`

method with the following signature:

```
concat :: Semigroup a => a ~> a -> a
```

*A Semigroup’s concat method must take another value of the same type, and return a third value of the same type.* The only law we have to worry about here is

**associativity**:

```
a.concat(b).concat(c)
=== a.concat(b.concat(c))
```

In other words, as long as the left-to-right order is maintained, we can put the brackets wherever we like. Just take a moment to think about how much **freedom** we have with this structure! As stated earlier, `Semigroup`

types are designed to be mooshmashed together. How the mooshmashing works is *entirely* up to you.

Let’s start with a look at **strings**. By chance, JavaScript’s `String`

type is *already* a Fantasy Land-compliant semigroup!

```
// 'hello, world!'
'hello'.concat(', world!')
// This operation is associative, too!
'hello'.concat(', ').concat('world!')
'hello'.concat(', '.concat('world!'))
```

We take two strings, and `concat`

them to make another string. Along those lines, you might also notice that **arrays are already valid semigroups**, too!

```
[1, 2].concat([3, 4]) // [1, 2, 3, 4]
// Aaand it's associative!
[1].concat([2, 3]).concat([4])
[1].concat([2, 3].concat([4]))
```

Notice, as well, that we don’t put any **constraints** on the array’s inner type - we don’t need to care *what* is in the array!

For `String`

and `Array`

, it’s pretty obvious what the `concat`

implementation would be, probably because it’s `concat`

enation. How, though, do we `concat`

numbers? `+`

? `*`

? `max`

?

The answer is that **it’s up to you** - we can pick any of these as they would all satisfy the laws. This is the **freedom of semigroups**. In actual fact, it would even be a valid `concat`

implementation for strings if they were concatenated with `x + " MITTENS " + y`

- there really is a *lot* we can do with semigroups (but **always check the laws**).

For the sake of clarity, we tend to create **separate semigroup types** to encapsulate these ideas. We’ll start with a nice, easy one: `Sum`

.

```
const Sum = daggy.tagged('val')
Sum.prototype.concat = function (that) {
return Sum(this.val + that.val)
}
Sum(2).concat(Sum(3)).val // 5
```

**That’s it**. No hidden magic, no nothing. It’s so wonderfully simple; why not write `Product`

(multiplication), `Max`

, and `Min`

types as an exercise? I can promise you that it won’t take long!

We’re not only restricted to numbers, either. There are two intuitive `Semigroup`

instances for booleans:

```
Any.prototype.concat = function (that) {
return Any(this.val || that.val)
}
All.prototype.concat = function (that) {
return All(this.val && that.val)
}
```

`Any`

will hold `true`

if *any* concatenated values be `true`

, and `All`

will hold `true`

if *all* concatenated values be `true`

.

There are also a few others that don’t care what the inner type is, such as `First`

and `Last`

. Super simple, and we’ll see a use for these later:

```
// Return the a value in a.concat(b)
First.prototype.concat = function (that) {
return this
}
// Return the b value in a.concat(b)
Last.prototype.concat = function (that) {
return that
}
```

We’ll also see loads more use cases for these types defined so far when we get on to

monoidsin the next article*.

We could even define a `Set`

semigroup, where concatenation is **set union** (or **intersection**!), and the elements of its inner list are unique. If you want to have a go at building such a type, notice that `Set a`

could only be a `Semigroup`

if `a`

were a `Setoid`

(because you need to check for duplicates) - *all these algebraic structures are connected*! **Spooky**.

More generally, this is one of many examples of a `Semigroup`

instance with **constraints**. It’s much more common, however, for the constraints to be that inner types *also be semigroups*.

Let’s imagine we have a pair structure, which just holds two values of type `a`

and `b`

respectively. How do we make the *pair* a semigroup? Well, if we wanted to `concat`

it with another pair of types `a`

and `b`

, the obvious solution would be to `concat`

the two `a`

values and the two `b`

, and return a pair of the results. To do that, `a`

and `b`

need to be semigroups:

```
const Tuple = daggy.tagged('a', 'b')
// concat :: (Semigroup a, Semigroup b) =>
// Tuple a b ~> Tuple a b -> Tuple a b
Tuple.prototype.concat = function (that) {
return Tuple(this.a.concat(that.a),
this.b.concat(that.b))
}
// Returns Tuple(Sum(3), Any(true))
Tuple(Sum(1), Any(false))
.concat(Tuple(Sum(2), Any(true)))
```

We can see here that the `Tuple`

type is only a semigroup when its component parts are semigroups. This is a clever pattern: one (or both) of those component semigroups could be *another* pair of other semigroups, and they could **nest** as deep as we need! You can also extend this idea to any fixed groups of elements:

```
const Tuple3 = daggy.tagged(
'a', 'b', 'c'
)
const Tuple4 = daggy.tagged(
'a', 'b', 'c', 'd'
)
// Tuple5, Tuple6, etc...
// Is `concat` obvious for these?
```

I’m pretty sure you can work out how the `Tuple`

’s `concat`

method can be rewritten for *any number of fields*! Anyway, let’s not waste time writing `concat`

for `Tuple20`

. Instead, let’s talk about a *practical* application of this idea: **customer record merging**.

I’m sure they’re the three words you wanted to hear! Let’s imagine you’re building some system in which you store customer records that look like this:

```
const Customer = daggy.tagged(
'name', // String
'favouriteThings', // [String]
'registrationDate', // Int -- since epoch
'hasMadePurchase' // Bool
)
```

For whatever reason - I worked with the NHS, and reasons were *bountiful*) - you might end up with duplicate records for the same person. In this instance, you’d want to write a `concat`

function to make use of our shiny new `Semigroup`

machinery:

```
Customer.prototype.concat =
function (that) {
return Customer(
this.name,
// A `Set` type would be good here.
this.favouriteThings
.concat(that.favouriteThings),
Math.min(
this.registrationDate,
that.registrationDate
),
this.hasMadePurchase
|| that.hasMadePurchase
)
}
```

Well, it *is* a semigroup, but… it’s pretty **ugly**, right? Firstly, we’re tied to **one** particular merge strategy. Secondly, all these properties’ strategies look… *familiar*…

What we’d *really* like to do is define independent merge strategies, probably using semigroups, to which we can delegate the work. *That way*, we could even have several **different strategies** for merging, depending on the situation!

To do that, we’ll need to translate `Customer`

into some structure that can hold the same information (or, in fancy terms, *something isomorphic to our Customer structure*).

We’ve actually already defined one such structure: the `Tuple4`

! We’re holding exactly four values, so we can translate to and from this structure without trouble. Our “merge strategy” is therefore just a way of converting our `Customer`

object to and from a `Tuple4`

of `Semigroup`

types:

```
const myStrategy = {
// to :: Customer
// -> Tuple4 (First String)
// [String]
// (Min Int)
// (Any Bool)
to: customer => Tuple4(
First(customer.name),
// Arrays are semigroups already!
// We could use Set, though.
customer.favouriteThings,
Min(customer.registrationDate),
Any(customer.hasMadePurchase)
),
// from :: Tuple4 (First String)
// [String]
// (Min Int)
// (Any Bool)
// -> Customer
from: ({ a, b, c, d }) =>
Customer(a.val, b, c.val, d.val)
}
```

Our `to`

field converts a `Customer`

into a `Tuple4`

(with the properties wrapped in `Semigroup`

types), and our `from`

field converts back. The **type** of the intermediate structure might look a bit frightening, but…

*Who cares*? The important thing is that **it’s a semigroup**, and, if we have a semigroup, we can write a *gorgeous* function for merging values:

```
// merge :: Semigroup m
// => { to :: a -> m
// , from :: m -> a }
// -> a -> a -> a
const merge = strategy => x => y =>
strategy.from(
strategy.to(x)
.concat(strategy.to(y))
)
```

Look at that signature. Given any two values of a type (not necessarily a `Semigroup`

type!), if we can give a strategy (isomorphism!) for converting them to and from a given Semigroup, we can merge them!

What if we want to merge **more than two** customers? Well, instead of writing hundreds of functions, let’s just do a `reduce`

on a list to merge them into a given *starter customer*:

```
const mergeMany = strategy => initial =>
customers => customers.reduce(
merge(strategy), initial
)
```

Gets me all flustered, it does. We can actually make this *even prettier* with a little more structure that we’ll discuss in the next article on **monoids**, but I think this is a good enough example for now.

After all, we’ve taken our problem, separated our concerns, and produced some abstract functions that we could apply to *other* types - not just `Customer`

! - regardless of how complex they might be. **It’s semigroups all the way down**.

We’ve seen that semigroups have our back any time we want to *merge*, *mooshmash*, or *combine* (whatever word gives you the best **intuition**!) several data into one. We’ve also seen how flexible they can be - everything from `First`

to `Pair`

was a law-obiding `Semigroup`

type.

Yet, just as we’ll see with all the other Fantasy Land magic, the interface is *exactly* what we needed to create some really powerful functions. If you’re not convinced, here’s a Gist of the above example to play with.

Next time, we’ll look at a very common extension to the idea of semigroups. If you can’t wait until then, I actually wrote a blog post on monoids a while back that should help you get a feel before next week.

Finally, another **thank you** to everyone following along. The feedback has been *great*, and I’ve had plenty of questions. Please please *please* send any my way, via my Twitter or my GitHub, and I’ll do what I can to help out.

Keep mooshmashing, and take care ♥

** I’ve given a lightning talk on monoids in the past, but it’s a PHP talk by a younger Tom, so it’s all a bit painful to watch, I’m afraid!*