4 ms·
> 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
by Twisol 5y ago
> 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])`
- tremon 5y ago> With `pop`, it's `Stack -> Stack`. A signature like that would simply discard the value of the element on the stack, which makes the data structure write-only and superfluous. The signature should be `Stack -> (Char, Stack)`.
- Twisol 5y ago`Stack -> (Char, Stack)` is equivalent to `(Stack -> Char, Stack -> Stack)`, which amounts to adding a `peek` method to the scheme above. The inclusion of `peek` changes nothing about the description of stack mutations above, and its clear separation better maps to what Raph is modeling in the first place. To be more explicit: Raph is modeling a scene graph, and a traversal of the scene graph consists of a series of pushes and pops on a stack, together with operations on nodes that act on a particular state of the stack. To parallelize these operations we need to be able to access the state of the stack at multiple points along the traversal. Each operation will use `peek` (and likely `pop`, too, but notice that it doesn't affect other operations here; it's more like moving a cursor down the stack) to drive its own behavior, but those read operations are independent of the traversal itself. It is the traversal we are modeling.