4 ms·

From Wikipedia: > In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. So M

From Wikipedia: > In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. So M = (S, op, id) My go-to example of a monoid is (the set of strings, string concatenation, the empty string). It's my go-to because there's e.g. no `x` such that `concat("blah", x) == ""`. Another example is (integers, +, 0), but it is not my go-to example because it also more than a monoid. I did not find a clear explanation of what the stack monoid is here. Can someone state it, please?

tomstuart 5y ago
An earlier post (https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html) explains it. The elements of the monoid are stack operations represented by pairs `(n, vs)`, where `n` is a number of values to pop off the stack and `vs` is a list of values to push on afterwards. So e.g. `(3, [])` is “pop 3 values”, `(1, ['foo', 'bar'])` is “pop 1 value then push 'foo' and 'bar'”, etc. Two elements are composed by combining their pop counts and push lists to reflect what happens to the stack if you apply the operations sequentially, e.g. the previous two examples compose to `(4, ['foo', 'bar'])`. The identity is `(0, [])`.
- lmm 5y ago
  So this isn't really the stack monoid, this is mutations as a monoid (which is a construction that exists for anything mutable), or the command monoid. The insight is that these mutations have a nice representation as first-class values and you can combine two "stack mutation commands" efficiently.
  - Twisol 5y ago
    > So this isn't really the stack monoid, this is mutations as a monoid (which is a construction that exists for anything mutable) I can see why you'd balk at the name "stack monoid", but the specific commands / actions being modeled (push/pop) are exactly the ones modeling a stack. It's not a purely syntactic construction because a push followed by a pop is evaluated away. The representation as `(pops, pushes)` is the natural conclusion of this line of semantic analysis. > this is mutations as a monoid In general though, yeah, this is the secret sauce. The history of commands on a mutable cell is sufficient to recover the value of the cell at any point in time, and the history of values held by the cell is sufficient to derive a (not necessarily unique) history of commands going between each snapshot. Typically, though, we only remember the "latest" value of the cell, so we lose a lot of information. In a parallel algorithm, multiple "points in time" need to be accessible simultaneously, so you get a lot by moving to a representation where you're not already missing information.
TheMatten 5y ago
> My go-to example of a monoid is (the set of strings, string concatenation, the empty string). There's an interesting reason why strings are a good example - when you think of `string` as `List<char>`, that `List` in it actually turns out to be a "free monoid". That is, minimal amount of structure needed to encode monoid operations in such a way that you can interpret them later as needed into something else. And one possible interpretation function is something commonly called `reduce` - you can basically think of `[1,2,3].reduce((x, y) => x + y, 0)` as interpretation of this monoidal structure into monoid of integers with addition.
dan-robertson 5y ago
Consider first the bicyclic monoid, which may be presented as < a,b | ba >. That is, the elements are lists of the symbols a, b, such that you never see a b followed by an a, so elements have the form a^n b^m, and indeed the numbers n,m are sufficient to describe an element of the monoid. One way to look at it is as parenthesis balancing: replace a,b with (,) respectively and then the monoid is strings of (,) except any matched pairs () are removed. Now change ( for lots of different elements you might want, say integers for their place in the string maybe. You get a presentation like < p, x \in X | \forall x \in X xp = e >, that is if you see an element of your data set immediately followed by a p (for pop) you can delete both. This is the stack monoid and elements may be described as p^n s, where s is a list of elements of X and may be read as “the stack operations of popping n times and pushing a,” or “the tree traversal of going up n nodes and then going down the path s.”
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
skavi 5y ago
Is a reduce method a monoid then?
- Twisol 5y ago
  It's definitely related, yes! You can reduce any list given a monoid on the type of elements of the list. That is, if you have a type `T` with combining operator `combine: (T, T) -> T` and unit `e: T`, you can reduce a list of `[T]` starting with `e` and combining each element into it. If I have a list of numbers `xs`, there are two nice monoids available: (+, 0) and (*, 1). In a JS-like notation, I can reduce using either monoid with `xs.reduce(0, (acc, x) => acc + x)` or `xs.reduce(1, (acc, x) => acc * x)`, respectively. The existence of `reduce` is actually exactly what makes lists the "free monoid"!

tomstuart 5y ago

An earlier post (https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html) explains it. The elements of the monoid are stack operations represented by pairs `(n, vs)`, where `n` is a number of values to pop off the stack and `vs` is a list of values to push on afterwards. So e.g. `(3, [])` is “pop 3 values”, `(1, ['foo', 'bar'])` is “pop 1 value then push 'foo' and 'bar'”, etc. Two elements are composed by combining their pop counts and push lists to reflect what happens to the stack if you apply the operations sequentially, e.g. the previous two examples compose to `(4, ['foo', 'bar'])`. The identity is `(0, [])`.

lmm 5y ago
So this isn't really the stack monoid, this is mutations as a monoid (which is a construction that exists for anything mutable), or the command monoid. The insight is that these mutations have a nice representation as first-class values and you can combine two "stack mutation commands" efficiently.
- Twisol 5y ago
  > So this isn't really the stack monoid, this is mutations as a monoid (which is a construction that exists for anything mutable) I can see why you'd balk at the name "stack monoid", but the specific commands / actions being modeled (push/pop) are exactly the ones modeling a stack. It's not a purely syntactic construction because a push followed by a pop is evaluated away. The representation as `(pops, pushes)` is the natural conclusion of this line of semantic analysis. > this is mutations as a monoid In general though, yeah, this is the secret sauce. The history of commands on a mutable cell is sufficient to recover the value of the cell at any point in time, and the history of values held by the cell is sufficient to derive a (not necessarily unique) history of commands going between each snapshot. Typically, though, we only remember the "latest" value of the cell, so we lose a lot of information. In a parallel algorithm, multiple "points in time" need to be accessible simultaneously, so you get a lot by moving to a representation where you're not already missing information.

TheMatten 5y ago

> My go-to example of a monoid is (the set of strings, string concatenation, the empty string). There's an interesting reason why strings are a good example - when you think of `string` as `List<char>`, that `List` in it actually turns out to be a "free monoid". That is, minimal amount of structure needed to encode monoid operations in such a way that you can interpret them later as needed into something else. And one possible interpretation function is something commonly called `reduce` - you can basically think of `[1,2,3].reduce((x, y) => x + y, 0)` as interpretation of this monoidal structure into monoid of integers with addition.

dan-robertson 5y ago

Consider first the bicyclic monoid, which may be presented as < a,b | ba >. That is, the elements are lists of the symbols a, b, such that you never see a b followed by an a, so elements have the form a^n b^m, and indeed the numbers n,m are sufficient to describe an element of the monoid. One way to look at it is as parenthesis balancing: replace a,b with (,) respectively and then the monoid is strings of (,) except any matched pairs () are removed. Now change ( for lots of different elements you might want, say integers for their place in the string maybe. You get a presentation like < p, x \in X | \forall x \in X xp = e >, that is if you see an element of your data set immediately followed by a p (for pop) you can delete both. This is the stack monoid and elements may be described as p^n s, where s is a list of elements of X and may be read as “the stack operations of popping n times and pushing a,” or “the tree traversal of going up n nodes and then going down the path s.”

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

skavi 5y ago

Is a reduce method a monoid then?

Twisol 5y ago
It's definitely related, yes! You can reduce any list given a monoid on the type of elements of the list. That is, if you have a type `T` with combining operator `combine: (T, T) -> T` and unit `e: T`, you can reduce a list of `[T]` starting with `e` and combining each element into it. If I have a list of numbers `xs`, there are two nice monoids available: (+, 0) and (*, 1). In a JS-like notation, I can reduce using either monoid with `xs.reduce(0, (acc, x) => acc + x)` or `xs.reduce(1, (acc, x) => acc * x)`, respectively. The existence of `reduce` is actually exactly what makes lists the "free monoid"!