5 ms·

For those who don’t know what a monoid is, like me three months ago, I believe a monoid is something that implements monoidal operations, which are binary assoc

For those who don’t know what a monoid is, like me three months ago, I believe a monoid is something that implements monoidal operations, which are binary associative operations with an identity. Integers have monoidal operations like addition and multiplication. You have two arguments, which don’t matter in ordering, and where an identity like the additive or multiplicative identity exists.

kragen 7y ago
This is all correct! Except for order not mattering, which is true of your examples but not true in general. But integer addition and multiplication also have a variety of other interesting algebraic properties: they are invertible (except multiplication by 0) and commutative, one distributes over the other, and integer addition has inverse elements. Some other monoids may give the flavor more clearly: - string concatenation is a monoid, with the empty string as the identity element. In fact, string concatenation is the most general monoid on a set, called the "free monoid"; all other monoids can be made from it by defining a canonicalization operation. For integer addition, for example, you can collapse a string of integers such as [4, -1, 2] down to their sum, such as [5]. Note that the free monoid is not commutative, and although it is invertible (in "hairy" || " and a half" = "hairy and a half", you can take " and a half" off and get the original "hairy"), it doesn't have inverse elements. - max and min on a closed set, and more generally all semilattices. Let's write 4 \/ 5 = 5 \/ 4 = 5. This \/ is associative and has an identity (whatever the maximum of the closed set is; we can augment the integers with -∞ and +∞ and use -∞ as the identity element), so it forms a monoid. Any theorem about monoids will work equally well for string concatenation and for this pairwise max operator. Isn't that wild? - & and | for bitstrings of some length. This is also a lattice. - Matrix multiplication (for matrices of a particular square shape). - The morphological dilation operation.
- techbio 7y ago
  Fascinating. Curious about matrix multiplication and a “particular square shape”. I’m interested if you would care to elaborate on the matrix relationship.
  - kragen 7y ago
    Oh, well, I mean that if you have a 3×3 matrix and a 4×4 matrix, you can't even multiply them. So 4×4 matrices form a monoid under multiplication, as do 3×3 matrices, but matrices in general do not. It turns out that they actually form a much richer structure called a ring when you add in their addition operator as well: https://en.m.wikipedia.org/wiki/Matrix_ring https://en.m.wikipedia.org/wiki/Matrix_ring
RangerScience 7y ago
ELI5? I appreciate the attempted explanation, but I'm not finding the the new one any more helpful.
- curryhoward 7y ago
  Consider these equations for integers: x * 1 = x 1 * x = 1 x * (y * z) = (x * y) * z These should be familiar if you know about integers. Now consider the following equations for strings: concat(x, "") = x concat("", x) = x concat(x, concat(y, z)) = concat(concat(x, y), z) These should be familiar if you know about strings. Now consider the following equations for booleans: x or false = x false or x = x x or (y or z) = (x or y) or z These should be familiar if you know about booleans. If you can see the pattern, you understand monoids. Monoids are everywhere in programming.
  - deleted 7y ago
    [deleted]
  - RangerScience 7y ago
    This is fantastic, thank you! Alright, first thing I noticed was the presence of identity operators. But then you're replacing the identity "operator" with an expression. Combining this with some of what other people are saying, and one aspect of monoids is that they're... chainable? The value of a monoid expression is the same type as the parameters of the monoid expression; `bar someMonoidFunction(bar x, bar y)`...? This then has some interesting ramifications for chaining/composing, as you demonstrate in the third example of each group. There's... something further than this, I can tell, but it's not yet clear to me. Can you do one these wonderful - heh, koans, basically - for something like `sin(cos(x))`?
    - BoiledCabbage 7y ago
      You've pretty much got it. A monoid is a two argunent operation and a data type with 3 properties: It's 'chainable', or the more precise mathematical term is "closed". It has a value that can be used as an identity. And it's associative. Where associative means that when 'chaining' multiple operations (as you termed it) it doesn't matter how you group with parentheses; it'll produce the same result.

kragen 7y ago

This is all correct! Except for order not mattering, which is true of your examples but not true in general. But integer addition and multiplication also have a variety of other interesting algebraic properties: they are invertible (except multiplication by 0) and commutative, one distributes over the other, and integer addition has inverse elements. Some other monoids may give the flavor more clearly: - string concatenation is a monoid, with the empty string as the identity element. In fact, string concatenation is the most general monoid on a set, called the "free monoid"; all other monoids can be made from it by defining a canonicalization operation. For integer addition, for example, you can collapse a string of integers such as [4, -1, 2] down to their sum, such as [5]. Note that the free monoid is not commutative, and although it is invertible (in "hairy" || " and a half" = "hairy and a half", you can take " and a half" off and get the original "hairy"), it doesn't have inverse elements. - max and min on a closed set, and more generally all semilattices. Let's write 4 \/ 5 = 5 \/ 4 = 5. This \/ is associative and has an identity (whatever the maximum of the closed set is; we can augment the integers with -∞ and +∞ and use -∞ as the identity element), so it forms a monoid. Any theorem about monoids will work equally well for string concatenation and for this pairwise max operator. Isn't that wild? - & and | for bitstrings of some length. This is also a lattice. - Matrix multiplication (for matrices of a particular square shape). - The morphological dilation operation.

techbio 7y ago
Fascinating. Curious about matrix multiplication and a “particular square shape”. I’m interested if you would care to elaborate on the matrix relationship.
- kragen 7y ago
  Oh, well, I mean that if you have a 3×3 matrix and a 4×4 matrix, you can't even multiply them. So 4×4 matrices form a monoid under multiplication, as do 3×3 matrices, but matrices in general do not. It turns out that they actually form a much richer structure called a ring when you add in their addition operator as well: https://en.m.wikipedia.org/wiki/Matrix_ring https://en.m.wikipedia.org/wiki/Matrix_ring

RangerScience 7y ago

ELI5? I appreciate the attempted explanation, but I'm not finding the the new one any more helpful.

curryhoward 7y ago
Consider these equations for integers: x * 1 = x 1 * x = 1 x * (y * z) = (x * y) * z These should be familiar if you know about integers. Now consider the following equations for strings: concat(x, "") = x concat("", x) = x concat(x, concat(y, z)) = concat(concat(x, y), z) These should be familiar if you know about strings. Now consider the following equations for booleans: x or false = x false or x = x x or (y or z) = (x or y) or z These should be familiar if you know about booleans. If you can see the pattern, you understand monoids. Monoids are everywhere in programming.
- deleted 7y ago
  [deleted]
- RangerScience 7y ago
  This is fantastic, thank you! Alright, first thing I noticed was the presence of identity operators. But then you're replacing the identity "operator" with an expression. Combining this with some of what other people are saying, and one aspect of monoids is that they're... chainable? The value of a monoid expression is the same type as the parameters of the monoid expression; `bar someMonoidFunction(bar x, bar y)`...? This then has some interesting ramifications for chaining/composing, as you demonstrate in the third example of each group. There's... something further than this, I can tell, but it's not yet clear to me. Can you do one these wonderful - heh, koans, basically - for something like `sin(cos(x))`?
  - BoiledCabbage 7y ago
    You've pretty much got it. A monoid is a two argunent operation and a data type with 3 properties: It's 'chainable', or the more precise mathematical term is "closed". It has a value that can be used as an identity. And it's associative. Where associative means that when 'chaining' multiple operations (as you termed it) it doesn't matter how you group with parentheses; it'll produce the same result.