> My go-to example of a monoid is (the set of strings, string concatenation, the empty string)

My favorite is the monoid of endomorphisms! "Endomorphism" is a fancy word, but it just means "if you give me a `T`, I'll return a `T` like it but with some changes."

Programs that operate on a stack usually look something like this (if we ignore everything that isn't touching the stack):

    stack.push('a');
    stack.push('b');
    stack.pop();

It's assumed that `stack` refers to some mutable cell, here. We can push mutation to the boundary if we change `push` and `pop` to return the new stack, and change `stack` itself to reference a get/set register containing a stack:

    stack.set(stack.get().push('a').push('b').pop());

Now, what is the type signature of `push`? In Haskell-ish, it's `Char -> (Stack -> Stack)`. With `pop`, it's `Stack -> Stack`. (I'm assuming that `this` is passed last, which is amusingly the opposite of what we're used to.) In other words, each operation takes zero or more arguments and produces a transformation that turns one Stack into another.

The thing about operations like `Stack -> Stack` is that you can combine them together without even having a `Stack` handy. You just produce a function that does one, passes its result to the other, and returns the final result. And of course, I could write an identity function that returns the given stack unchanged. That makes `Stack -> Stack` (and really any `T -> T`) a monoid!

In other words, instead of `(stack.push('a')).pop()`, where we morally associate the parentheses to the left, we have something like `stack.(push('a').pop())`, except obviously OOP dot notation doesn't work that way. But that's the intuition -- we're combining the operations before we feed them a stack to operate on.

Ultimately, that's what Raph's stack monoid is based on, except instead of functions `T -> T` they describe `push` and `pop` with data. This is called "defunctionalization", and it basically works because we can write a single function (an interpreter) that performs the cumulative actions described by that data.

As a sibling comment explains, lists are the free monoid for a set of actions (where "free" means "assuming the least necessary"), so we could get by with `[Push 'a', Push 'b', Pop]` as a representation. But this contains more information than we actually need. We know that if a push is followed by a pop, the contents of the push don't matter to us. We can therefore remove any push-then-pop pair of actions. When we simplify in this way, we find that the only sequences of actions we have are N pops followed by M pushes. So Raph's representation coalesces the adjacent pushes and pops into `(Int, [Char])`