# Fantas, Eel, and Specification 4: Semigroup

Today, 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('Sum', ['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 monoids in 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('Tuple', ['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(
'Tuple3', ['a', 'b', 'c']
)

const Tuple4 = daggy.tagged(
'Tuple4', ['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('Customer', [
'name',             // String
'favouriteThings',  // [String]
'registrationDate', // Int -- since epoch
])
``````

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
),

)
}
``````

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),

// We could use Set, though.
customer.favouriteThings,

Min(customer.registrationDate),

),

// 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!