# Wild combination

In this chapter, we will examine monoids by way of semigroup. Monoids are the bubblegum in the hair of mathematical abstraction. They capture an idea that spans multiple disciplines, figuratively and literally bringing them all together. They are the ominous force that connects all that calculates. The oxygen in our code base, the ground on which it runs, quantum entanglement encoded.

Monoids are about combination. But what is combination? It can mean so many things from accumulation to concatenation to multiplication to choice, composition, ordering, even evaluation! We'll see many examples here, but we'll only tip-toe on the foothills of monoid mountain. The instances are plentiful and applications vast. The aim of this chapter is to provide a good intuition so you can make some monoids of your own.

Addition has some interesting qualities I'd like to discuss. Let's have a look at it through our abstraction goggles.

For starters, it's a binary operation, that is, an operation which takes two values and returns a value, all within the same set.

`# a binary operation1 + 1 = 2`

See? Two values in the domain, one value in the codomain, all the same set - numbers, as it were. Some might say numbers are "closed under addition", meaning the type won't ever change no matter which ones get tossed into the mix. That means we can chain the operation since the result is always another number:

`# we can run this on any amount of numbers1 + 7 + 5 + 4 + ...`

In addition to that (what a calculated pun...), we have associativity which buys us the ability to group operations however we please. Incidentally, an associative, binary operation is a recipe for parallel computation because we can chunk and distribute work.

`# associativity(1 + 2) + 3 = 61 + (2 + 3) = 6`

Now, don't go confusing this with commutativity which allows us to rearrange the order. While that holds for addition, we're not particularly interested in that property at the moment - too specific for our abstraction needs.

Come to think of it, what properties should be in our abstract superclass anyways? What traits are specific to addition and what ones can be generalized? Are there other abstractions amidst this hierarchy or is it all one chunk? It's this kind of thinking that our mathematical forefathers applied when conceiving the interfaces in abstract algebra.

As it happens, those old school abstractionists landed on the concept of a group when abstracting addition. A group has all the bells and whistles including the concept of negative numbers. Here, we're only interested in that associative binary operator so we'll choose the less specific interface Semigroup. A Semigroup is a type with a `concat` method which acts as our associative binary operator.

Let's implement it for addition and call it `Sum`:

`class Sum:    def __init__(self, x):        self.x = x    def concat(self, other):        return Sum(self.x + other.x)`

Note we `concat` with some other `Sum` and always return a `Sum`.

`Sum(1).concat(Sum(3)) # Sum(4)Sum(4).concat(Sum(37)) # Sum(41)`

Just like that, we can program to an interface, not an implementation. Since this interface comes from group theory it has centuries of literature backing it up. Free docs!

Now, as mentioned, `Sum` is not pointed, nor a functor. As an exercise, go back and check the laws to see why. Okay, I'll just tell you: it can only hold a number, so `map` does not make sense here as we cannot transform the underlying value to another type. That would be a very limited `map` indeed!

So why is this useful? Well, as with any interface, we can swap out our instance to achieve different results:

`class Product:    def __init__(self, x):        self.x = x    def concat(self, other):        return Product(self.x * other.x)​class Min:    def __init__(self, x):        self.x = x    def concat(self, other):        return Min(min(self.x,other.x))​class Max:    def __init__(self, x):        self.x = x    def concat(self, other):        return Max(max(self.x, other.x))`

This isn't limited to numbers, though. Let's see some other types:

`class Any:    def __init__(self, x):        self.x = x    def concat(self, other):        return Any(self.x or other.x)​class All:    def __init__(self, x):        self.x = x    def concat(self, other):        return All(self.x and other.x)​Any(False).concat(Any(True)) # Any(True)Any(False).concat(Any(False)) # Any(False)​All(False).concat(All(True)) # All(False)All(True).concat(All(True)) # All(True)​[1,2].concat([3,4]) # [1,2,3,4]​"miracle grow".concat("n") # "miracle grown"​Map({day: 'night'}).concat(Map({white: 'nikes'})) # Map({day: 'night', white: 'nikes'})`

If you stare at these long enough the pattern will pop out at you like a magic eye poster. It's everywhere. We're merging data structures, combining logic, building strings...it seems one can bludgeon almost any task into this combination based interface.

I've used `Map` a few times now. Pardon me if you two weren't properly introduced. `Map` simply wraps `dict` so we can embellish it with some extra methods without altering the fabric of the universe.

# All my favourite functors are semigroups.

The types we've seen so far which implement the functor interface all implement semigroup one as well. Let's look at `Identity` (the artist previously known as Container):

`class Identity:...def concat(self, other):  return Identity(self.value.concat(other.value))}​Identity(Sum(4)).concat(Identity(Sum(1))) # Identity(Sum(5))Identity(4).concat(Identity(1)) # AttributeError: 'int' object has no attribute 'concat'`

It is a semigroup if and only if its `value` is a semigroup. Like a butterfingered hang glider, it is one whilst it holds one.

Other types have similar behavior:

`# combine with error handlingRight(Sum(2)).concat(Right(Sum(3))) # Right(Sum(5))Right(Sum(2)).concat(Left('some error')) # Left('some error')​​# combine asyncTask([1,2]).concat(Task([3,4])) # Task([1,2,3,4])`

This gets particularly useful when we stack these semigroups into a cascading combination:

`serverA.get('/friends').concat(serverB.get('/friends')) # Task([friend1, friend2])​# load_setting :: str -> Task Error (Maybe (Map str Boolean))load_setting('email').concat(load_setting('general')) # Task(Maybe(Map({backgroundColor: true, autoSave: false})))`

In the top example, we've hit a couple of different servers and combined their results in an async way using `Task` and `Array`. Lastly, we've stacked `Task`, `Maybe`, and `Map` to load, parse, and merge multiple settings.

These can be `chain`ed or `ap`'d, but semigroups capture what we'd like to do much more concisely.

This extends beyond functors. In fact, it turns out that anything made up entirely of semigroups, is itself, a semigroup: if we can concat the kit, then we can concat the caboodle.

`class Analytics:    def __init__(self, clicks, path, idle_time):        self.clicks = clicks        self.path = path        self.idle_time = idle_time​    def concact(self, other):        return Analytics(clicks.concat(other.clicks),                         path.concat(other.path),                         idle_time.concat(other.idle_titme))​​Analytics(Sum(2), ['/home', '/about'], Right(Max(2000))).concat(Analytics(Sum(1), ['/contact'], Right(Max(1000))))# Analytics(Sum(3), ['/home', '/about', '/contact'], Right(Max(2000)))`

We can stack and combine as many of these as we'd like. It's simply a matter of adding another tree to the forest, or another flame to the forest fire depending on your codebase.

The default, intuitive behavior is to combine what a type is holding, however, there are cases where we ignore what's inside and combine the containers themselves. Consider a type like `Stream`:

# Monoids for nothing

We were abstracting addition, but like the Babylonians, we lacked the concept of zero (there were zero mentions of it).

Zero acts as identity meaning any element added to `0`, will return back that very same element. Abstraction-wise, it's helpful to think of `0` as a kind of neutral or empty element. It's important that it act the same way on the left and right side of our binary operation:

`# identity1 + 0 = 10 + 1 = 1`

Let's call this concept `empty` and create a new interface with it. Like so many startups, we'll choose a heinously uninformative, yet conveniently googleable name: Monoid. The recipe for Monoid is to take any semigroup and add a special identity element. We'll implement that with an `empty` function on the type itself:

`class Array:    def empty(self):        return []​class Sum:    def empty(self):        return Sum(0)​class Product:    def empty(self):        return Product(1)​class All():    def empty(self):        return All(True)`

When might an empty, identity value prove useful? That's like asking why zero is useful. Like not asking anything at all...

When we have nothing else, who can we count on? Zero. How many bugs do we want? Zero. It's our tolerance for unsafe code. A fresh start. The ultimate price tag. It can annihilate everything in its path or save us in a pinch. A golden life saver and a pit of despair.

Codewise, they correspond to sensible defaults:

`def settings(overrides=Array.empty(), total=Sum.empty()):    ...`

Or to return a useful value when we have nothing else:

`sum([]) # 0`

They are also the perfect initial value for an accumulator...

# Folding down the house

It just so happens that `concat` and `empty` fit perfectly in the first two slots of `reduce`. We can actually `reduce` an array of semigroup's down by ignoring the empty value, but as you can see, that leads to a precarious situation:

`# concat :: Semigroup s => s -> s -> sconcat = lambda x, y: x.concat(y)​functools.reduce(concat), [Sum(1), Sum(2)]) # Sum(3)​functools.reduce(concat), []) # TypeError: reduce() of empty sequence with no initial valu`

Boom goes the dynamite. Like a twisted ankle in a marathon, we have ourselves a runtime exception. Python is more than happy to let us strap pistols to our sneakers before running - it is a conservative sort of language, I suppose, but it stops us dead in our tracks when the array is barren. What could it return anyhow? `None`, `False`, `-1`? If we were to continue on in our program, we'd like a result of the right type. It could return a `Maybe` to indicate the possibility of failure, but we can do one better.

Let's use `reduce` function and make a safe version where the `empty` value is not optional. It shall henceforth be known as `fold`:

`# fold :: Monoid m => m -> [m] -> mfold = lambda init, xs: reduce(xs, concat, init)`

The initial `m` is our `empty` value - our neutral, starting point, then we take an array of `m`'s and crush them down to one beautiful diamond like value.

`fold(Sum.empty(), [Sum(1), Sum(2)]) # Sum(3)fold(Sum.empty(), []) # Sum(0)​fold(Any.empty(), [Any(False), Any(True)]) # Any(true)fold(Any.empty(), []) # Any(False)​​fold(Either(Max.empty()), [Right(Max(3)), Right(Max(21)), Right(Max(11))]) # Right(Max(21))fold(Either(Max.empty()), [Right(Max(3)), Left('error retrieving value'), Right(Max(11))]) # Left('error retrieving value')`

We've provided a manual `empty` value for those last two since we can't define one on the type itself. That's totally fine. Typed languages can figure that out by themselves, but we have to pass it in here.

# Not quite a monoid

There are some semigroups that cannot become monoids, that is provide an initial value. Look at `First`:

`class First:    def __init__(self, x):        self.x = x    def concat(self, other):        return First(self.x)​Map({id: First(123), is_paid: Any(True), points: Sum(13)}).concat(Map({id: First(2242), is_paid: Any(False), points: Sum(1)}))# Map({id: First(123), is_paid: Any(True), points: Sum(14)})`

We'll merge a couple of accounts and keep the `First` id. There is no way to define an `empty` value for it. Doesn't mean it's not useful.

# Group theory or Category theory?

The notion of a binary operation is everywhere in abstract algebra. It is, in fact, the primary operation for a category. We cannot, however, model our operation in category theory without an identity. This is the reason we start with a semi-group from group theory, then jump to a monoid in category theory once we have empty.

Monoids form a single object category where the morphism is `concat`, `empty` is the identity, and composition is guaranteed.

## Composition as a monoid

Functions of type `a -> a`, where the domain is in the same set as the codomain, are called endomorphisms. We can make a monoid called `Endo` which captures this idea:

`class Endo:    def __init__(self, run):        self.run = run    def concat(self, other):        return Endo(compose(run, other.run))    def empty(self):        return Endo(indetity)​# in actionthing_down_flip_and_reverse :: Endo [str] -> [str]thing_down_flip_and_reverse = fold(Endo(lambda: []), [Endo(reverse), Endo(sort), Endo(append('thing down')])thing_down_flip_and_reverse.run(['let me work it', 'is it worth it?'])# ['thing down', 'let me work it', 'is it worth it?']`

Since they are all the same type, we can `concat` via `compose` and the types always line up.

You may have noticed that `join` is an operation which takes two (nested) monads and squashes them down to one in an associative fashion. It is also a natural transformation or "functor function". As previously stated, we can make a category of functors as objects with natural transformations as morphisms. Now, if we specialize it to Endofunctors, that is functors of the same type, then `join` provides us with a monoid in the category of Endofunctors also known as a Monad. To show the exact formulation in code takes a little finagling which I encourage you to google, but that's the general idea.
Even applicative functors have a monoidal formulation known in the category theory as a lax monoidal functor. We can implement the interface as a monoid and recover `ap` from it:
`# concat :: f a -> f b -> f [a, b]# empty :: () -> f ()​# ap :: Functor f => f (a -> b) -> f a -> f bap = compose(map(([f, x]) => f(x)), concat)`