5 ms·

A monoid is a set of objects each having a port on the left and on the right, and given two such objects you can join the left port of one object to the right p

by kmill 7y ago

A monoid is a set of objects each having a port on the left and on the right, and given two such objects you can join the left port of one object to the right port of the other, constructing a new object. There is also an "empty" object that, when joined to any given object, results in that object unchanged. For example, stacks of paper can be thought of as a monoid. Given two stacks, you can stack one on top of the other (the top and bottom of the stack standing in for the ports). The vacuous concept of a stack of zero sheets of paper is the "empty" object. Another example is the set of PNG files. There are a number of monoids you could define, like horizontal concatenation of images, or the vertical concatenation of images. A non-example is blending two images with 50% opacity each, since depending on the order you blend the images, like (AB)C versus A(BC), image A might contribute 25% or 50% to the final image. For some monoids, the left/right port distinction doesn't matter. Consider buckets of marbles. The way you join two buckets of marbles is to dump them into a single bucket. The empty bucket is the empty object. It doesn't matter in which order you dump the marbles into a bucket --- you'll get the same number of marbles in the end.

navaati 7y ago
Love the non-usual, physical-world examples :)
RangerScience 7y ago
This was very helpful. So an important aspect of a set of monodial operations is that the order doesn't effect the outcome...? This mostly makes sense, although... not for arrays where order matters...?
- uryga 7y ago
  it's not exactly order independence, it's associativity: (a • b) • c == a • (b • c) i.e. "no matter where you put the parentheses, it'll give the same result". this DOESN'T mean that a • b == b • a though it may be true for some monoids like addition/multiplication over numbers¹. you'll notice that associativity indeed holds for strings (or arrays of some T), where concatenation is the monoidal operation: ("he" ++ "ll") ++ "o!" == "he ++ ("ll" ++ "o!") == "hello!" though at first blush associativity may not seem very useful, it is! it means folding/"summing" a sequence of monoidal values is trivially parallelizable. i.e. if you've got a sequence as = [a0, a1, a2, ..., an-1, an] and you want to "sum"/fold it using a's monoidal operation "•": r = (a0 • a1 • a2 • ... • an) you can split it into chunks across multiple workers and then "sum" the results of summing each chunk: r0 = (a0•a1•a2) // worker 0 r1 = (a3•a4•a5) // worker 1 ... rm = (an-2,an-1,an) // worker m r = r0•r1•...•rm // sum up what the workers produced the nice thing is, as long as we don't reorder the elements, we'll always get the same result no matter how we chunk up `as`! and this will hold for any monoid `(a, •)`. btw, an example of a less trivial monoid is `sorted lists of T `: - `•`, the monoidal operation, is `merge(a, b)`, which combines two sorted lists into a new sorted list: `merge([1,2,3,5], [2,4]) == [1,2,2,3,4,5]` - `e`, the "neutral element", is just the empty list `[]` this is a (commutative) monoid, and you could say that mergesort relies on its monoidal properties to work! --- ¹ if you can swap values around and still get the same result, you've got a "commutative monoid".
  - uryga 7y ago
    whoops, that last code block was supposed to have rm = (an-2•an-1•an) instead of the commas.
- kmill 7y ago
  The word "order" is unfortunately overloaded. The first kind, like what you're talking about, is whether you use the left port or the right port of the first object when joining it to the second object. That certainly can matter, like with the stack of paper example. The second kind is joining things through time, where it is not supposed to matter when you join things. If you have three stacks of paper, you can stack the first onto the second and put that on the third, or you can stack the second on the third and put the first on top of that, and you get essentially the same pile in either case. Piles are supposed to be an analogue of arrays, where the first kind of order matters. Lots of times, the second kind of order (associativity) actually does matter, too, where you get literally different objects, but it's ok since there are "equal" in a useful sense. For example, when you make a text editor, you might use the rope data structure to represent strings. If so, when you concatenate a list of strings, the literal tree structures you get in the representation of the rope might vary depending how you did it, but they'll all be equal in the sense that the strings they represent are equal --- the same characters in the same order.
kmill 7y ago
I thought I'd add: what's the "mono" in "monoid"? It's that the ports come in only one compatibility type. For example, devices that have exactly two ports, one male and one female, for some type of connector, maybe USB-A. If you plug one into another, then you have a new device with the same properties, at least as far as ports are concerned.

by kmill 7y ago

navaati 7y ago

Love the non-usual, physical-world examples :)

RangerScience 7y ago

This was very helpful. So an important aspect of a set of monodial operations is that the order doesn't effect the outcome...? This mostly makes sense, although... not for arrays where order matters...?

uryga 7y ago
it's not exactly order independence, it's associativity: (a • b) • c == a • (b • c) i.e. "no matter where you put the parentheses, it'll give the same result". this DOESN'T mean that a • b == b • a though it may be true for some monoids like addition/multiplication over numbers¹. you'll notice that associativity indeed holds for strings (or arrays of some T), where concatenation is the monoidal operation: ("he" ++ "ll") ++ "o!" == "he ++ ("ll" ++ "o!") == "hello!" though at first blush associativity may not seem very useful, it is! it means folding/"summing" a sequence of monoidal values is trivially parallelizable. i.e. if you've got a sequence as = [a0, a1, a2, ..., an-1, an] and you want to "sum"/fold it using a's monoidal operation "•": r = (a0 • a1 • a2 • ... • an) you can split it into chunks across multiple workers and then "sum" the results of summing each chunk: r0 = (a0•a1•a2) // worker 0 r1 = (a3•a4•a5) // worker 1 ... rm = (an-2,an-1,an) // worker m r = r0•r1•...•rm // sum up what the workers produced the nice thing is, as long as we don't reorder the elements, we'll always get the same result no matter how we chunk up `as`! and this will hold for any monoid `(a, •)`. btw, an example of a less trivial monoid is `sorted lists of T `: - `•`, the monoidal operation, is `merge(a, b)`, which combines two sorted lists into a new sorted list: `merge([1,2,3,5], [2,4]) == [1,2,2,3,4,5]` - `e`, the "neutral element", is just the empty list `[]` this is a (commutative) monoid, and you could say that mergesort relies on its monoidal properties to work! --- ¹ if you can swap values around and still get the same result, you've got a "commutative monoid".
- uryga 7y ago
  whoops, that last code block was supposed to have rm = (an-2•an-1•an) instead of the commas.
kmill 7y ago
The word "order" is unfortunately overloaded. The first kind, like what you're talking about, is whether you use the left port or the right port of the first object when joining it to the second object. That certainly can matter, like with the stack of paper example. The second kind is joining things through time, where it is not supposed to matter when you join things. If you have three stacks of paper, you can stack the first onto the second and put that on the third, or you can stack the second on the third and put the first on top of that, and you get essentially the same pile in either case. Piles are supposed to be an analogue of arrays, where the first kind of order matters. Lots of times, the second kind of order (associativity) actually does matter, too, where you get literally different objects, but it's ok since there are "equal" in a useful sense. For example, when you make a text editor, you might use the rope data structure to represent strings. If so, when you concatenate a list of strings, the literal tree structures you get in the representation of the rope might vary depending how you did it, but they'll all be equal in the sense that the strings they represent are equal --- the same characters in the same order.

kmill 7y ago

I thought I'd add: what's the "mono" in "monoid"? It's that the ports come in only one compatibility type. For example, devices that have exactly two ports, one male and one female, for some type of connector, maybe USB-A. If you plug one into another, then you have a new device with the same properties, at least as far as ports are concerned.