5 ms·

>> algebraic structure I talk about the most passionately is the monoid Can you ELI5 monoid? what problem does it solve which isn't easy in other languages wi

>> algebraic structure I talk about the most passionately is the monoid Can you ELI5 monoid? what problem does it solve which isn't easy in other languages without it? edit: thx everyone.

PieSquared 9y ago
"Monoid" is an adjective that describes a data type. Anything you describe as a monoid has to have three properties: you can add them together, there's an "empty" or "zero" value, and (a + b) + c = a + (b + c). For example, strings with concatenation are a monoid, because you can use an empty string and the string + operator. For example, integers with addition are a monoid, because you can use 0 and the integer + operator. For example, sets are a monoid, because you can use the empty set and the union operator. For example, a "Picture" data type could be a monoid, because you could have a fully-transparent picture and use an "overlay" operator to put one picture on top of another. Why do you care? Well, for one thing, it just makes it easy to find the function or operator you want to use: as the OP said, if I feel like my data type should have a concat or append operator but I don't know what it's called, I just use mappend / mempty / mconcat. But, as another practical example: "sum" in Python works for numbers, but I've seen folks assume that it works for anything that you can use + on, and so try and use strings with it. But, because "sum" isn't a general purpose tool, that doesn't work! In Haskell, on the other hand, the equivalent -- mconcat -- will work on anything that is a monoid. (And can be specialized to work faster for specific data structures.) Other languages also have monoids. If someone tells you Haskell has monoids and other languages don't, what they really mean is, Haskell makes explicit the monoid pattern / interface, where other languages have it implicitly for different data types. Talking about the pattern explicitly isn't revolutionary, but it can be pretty useful for discoverability and writing "general" algorithms. Instead of calling data structures monoids, you'd get the same effect if, as a programming language community, you decided that as many types as possible should support "+", and that every data type that can should have a makeEmptyThing() method, and that it would be weird and not ok if x + makeEmptyThing() didn't equal x and if (x + y) + z didn't equal x + (y + z), and then subtly shamed any libraries that defined makeEmptyThing() and + in ways that didn't follow that pattern. But if your programming language community did this (for consistency) you'd probably want to come up with a name for it -- "Addable", "Concatable", etc -- and the Haskell community chose "Monoid" (because of relationships to theory etc etc).
- dllthomas 9y ago
  I agree with much of what you say here. Some refinements and small disagreements follow: A monoid isn't just a data type. Mathematically, it's a set ("data type" is plenty close enough, in this context) and an operation. Integers with addition are a monoid. But so are integers with multiplication. And these are two different monoids. Haskell confuses this issue a bit - they way the Haskell libraries are set up you can only name one Monoid instance per type, and so types that form monoids in several interesting ways get wrapped in "new types" so you can name each of the several. This mostly works fine, but is a bit hacky from a math POV, and I think doesn't lead as well as it might to a more general understanding. It's worth noting, too, that some of the Haskell libraries - particularly those from the early days - make some unfortunate decisions about what instances to bless. I often complain about the Monoid instance for Map. Map forms a monoid under union so long as we combine values (on collision) associatively. Unfortunately, the library doesn't let us pick how they are combined, it just takes the left one. That's usually not what I want, and it's particularly painful when I've been combining Sets with monoid operations and now realize they need to carry some extra info. ... and then of course there's floating point, which probably shouldn't even be Num. > But if your programming language community did this (for consistency) you'd probably want to come up with a name for it -- "Addable", "Concatable", etc -- and the Haskell community chose "Monoid" (because of relationships to theory etc etc). There are two things I really like about using the name Monoid, compared to the others. First, it's much clearer what the rules are. We aren't stuck wondering whether strings or products are "really" "Addable", whether functions of the form (a -> a) are "really" "Concatable" (... and what about nonempty strings? you can concatenate them, but they have no identity object...). Clarity in an interface means I know what properties I can rely on. You can define those properties precisely with "more intuitive" names, but then the actual interface doesn't match the intuition and people won't realize it, which is worse. You could get precise and intuitive by adding verbosity - "AssociativeOperationWithIdentity". My principle objection there is readability and aesthetics, but if that's what a community wants to go with okay... "Monoid" is short and unambiguous and well established in related fields. That last point touches on the other thing I like. There are mathematical results that can be useful to programmers. Reducing the translation needed helps make those more accessible. And everyone could do with knowing just a bit more algebra :-P
- 9y ago
danidiaz 9y ago
A monoid is an interface with two operations: one that produces an element out of thin air, and one that combines two elements. It also comes with a contract, like the contracts of "equals", "hashCode" or Comparable in Java. The contract says that the operation must be associative, and that the element you produce out of thin air must be neutral: when you combine it with another element it leaves the other element unchanged. One benefit of having such general interfaces is that you can reuse code across a wide range of domains. For example: the Comparator interface in Java can be seen as a monoid, with the "thenComparing" function as the combination operation: https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html#thenComparing-java.util.Comparator- https://docs.oracle.com/javase/8/docs/api/java/util/Comparat... You could build a list of comparators and concatenate it, map a function that produces a comparator over a list and concatenate it, and so on. Another benefit is that you can be quite general when specifying requirements for your functions. In Haskell, the Writer monad only requires the type of the accumulator to be an instance of Monoid. So you can user regular lists, difference lists, or the integers under addition. Also in Haskell some composite types automatically satisfy an interface if their components do, saving you work. For example, a tuple of monoids is automatically a monoid. Any function that returns a monoid is itself a monoid as well. (Functions that begin and end in the same type can be monoids in a different way: the neutral element is the identity function and the combination operation is composition.)
kreetx 9y ago
Monoid is a type class, similar to interfaces in Java, and this is what it makes easy: if your code uses the monoid interface of some type then you can swap the underlying concrete type without changing your code, and it still works. Obviously, you can do that in any untyped language, too, but explicitly defining these contracts makes code easy to manage and understand. And the compiler will tell you if/how you're doing something wrong.
mightybyte 9y ago
A monoid is something that allows you to take two of the same kind of thing and smash them together to be one of that same kind of thing. It also requires you to have an "empty" thing that can be smashed together with any other thing without changing the result. In code: smash :: Monoid a => a -> a -> a empty :: Monoid a => a A monoid is a property of things, not languages, so the idea of "a language without a monoid" doesn't really make sense.
- deleted 9y ago
  [deleted]
- catnaroek 9y ago
  Ah, so this is a monoid: instance Monoid Int where smash 25 x = x smash x 25 = x smash x y = 2*x^2 - 3*x*y empty = 25 Thanks for explaining!
  - amelius 9y ago
    I think combining 25 and x should yield x.
    - catnaroek 9y ago
      Oops, yes, my bad.
  - deleted 9y ago
    [deleted]
  - mjhoy 9y ago
    There are also the monoid "laws" (not checked in Haskell): empty `smash` x = x -- left identity x `smash` empty = x -- right identity (x `smash` y) `smash` z = x `smash` (y `smash` z) -- associativity Your definition doesn't fit any of these. (Edit: you've rewritten to meet the first two; but it is not associative.)
    - conistonwater 9y ago
dmitriid 9y ago
The irony is that there are now 4 monoid tutorials in the replies, and they are all different, and differently confusing :) And there I was, thinking that this only applied to monads :)
- throwanem 9y ago
  Perhaps someone should come up with a generalizable method for combining monoid tutorials. I wonder what we could call it...
- kahnpro 9y ago
  Is it really so confusing? I mean, if you understand + for integers and for strings and for lists, and you can understand why this is basically the same operation for all of them, congratulations! you know what a monoid is.
  - dmitriid 9y ago
    It's not confusing to me :) I'm just saying that at the time I wrote my comment there where four different comments with four different ways of explaining monoids with four different sets of terminology :)
sillysaurus3 9y ago
A monoid is a method of converting coffee into internet comments about monoids. It's quite ingenious, really.
ostochast 9y ago
For some people it is easier to understand a concept, especialy an abstract one, if they are given a few examples. For those people: A monoid is a set and an binary operation on the elements of that set with the following properties: 1.The operation acts on two elements of the set to produce another elemenent of that set(closure). Examples: You have a set od natural numbers {0,1,2,3..} with standard addition. Whichever two natural numbers you choose to add you will get a natural number back. A set of MxN matrices and matrix addition. If A and B are two MxN matrices A+B is a MxN matrix. 2.The order in which the operations are performed does not matter(associativity). So for all elements of our set a,b and c and the operation +: a+(b+c)=(a+b)+c must be valid. Examples: Let L be a set of strings and + concatenation. "Just"+(" an "+ "example")=("Just"+" an ")+"example" Vector addition over vectors of same dimension. 3.There is an element(unique!) in the set which when applied to any element of the set returns that element(identity, neutral element). e+a=a+e=a e is identity Examples: 0 is identity for standard addition: 0+1=1, 4+0=4 1 is identity for standard multplication: 1*7=7 ""(empty string) is identity for string concatenation
egl2019 9y ago
"Yet another monoid tutorial." This time in Hacker News comments. And lots of them. :-)

>> algebraic structure I talk about the most passionately is the monoid Can you ELI5 monoid? what problem does it solve which isn't easy in other languages without it? edit: thx everyone.

PieSquared 9y ago

"Monoid" is an adjective that describes a data type. Anything you describe as a monoid has to have three properties: you can add them together, there's an "empty" or "zero" value, and (a + b) + c = a + (b + c). For example, strings with concatenation are a monoid, because you can use an empty string and the string + operator. For example, integers with addition are a monoid, because you can use 0 and the integer + operator. For example, sets are a monoid, because you can use the empty set and the union operator. For example, a "Picture" data type could be a monoid, because you could have a fully-transparent picture and use an "overlay" operator to put one picture on top of another. Why do you care? Well, for one thing, it just makes it easy to find the function or operator you want to use: as the OP said, if I feel like my data type should have a concat or append operator but I don't know what it's called, I just use mappend / mempty / mconcat. But, as another practical example: "sum" in Python works for numbers, but I've seen folks assume that it works for anything that you can use + on, and so try and use strings with it. But, because "sum" isn't a general purpose tool, that doesn't work! In Haskell, on the other hand, the equivalent -- mconcat -- will work on anything that is a monoid. (And can be specialized to work faster for specific data structures.) Other languages also have monoids. If someone tells you Haskell has monoids and other languages don't, what they really mean is, Haskell makes explicit the monoid pattern / interface, where other languages have it implicitly for different data types. Talking about the pattern explicitly isn't revolutionary, but it can be pretty useful for discoverability and writing "general" algorithms. Instead of calling data structures monoids, you'd get the same effect if, as a programming language community, you decided that as many types as possible should support "+", and that every data type that can should have a makeEmptyThing() method, and that it would be weird and not ok if x + makeEmptyThing() didn't equal x and if (x + y) + z didn't equal x + (y + z), and then subtly shamed any libraries that defined makeEmptyThing() and + in ways that didn't follow that pattern. But if your programming language community did this (for consistency) you'd probably want to come up with a name for it -- "Addable", "Concatable", etc -- and the Haskell community chose "Monoid" (because of relationships to theory etc etc).

dllthomas 9y ago
I agree with much of what you say here. Some refinements and small disagreements follow: A monoid isn't just a data type. Mathematically, it's a set ("data type" is plenty close enough, in this context) and an operation. Integers with addition are a monoid. But so are integers with multiplication. And these are two different monoids. Haskell confuses this issue a bit - they way the Haskell libraries are set up you can only name one Monoid instance per type, and so types that form monoids in several interesting ways get wrapped in "new types" so you can name each of the several. This mostly works fine, but is a bit hacky from a math POV, and I think doesn't lead as well as it might to a more general understanding. It's worth noting, too, that some of the Haskell libraries - particularly those from the early days - make some unfortunate decisions about what instances to bless. I often complain about the Monoid instance for Map. Map forms a monoid under union so long as we combine values (on collision) associatively. Unfortunately, the library doesn't let us pick how they are combined, it just takes the left one. That's usually not what I want, and it's particularly painful when I've been combining Sets with monoid operations and now realize they need to carry some extra info. ... and then of course there's floating point, which probably shouldn't even be Num. > But if your programming language community did this (for consistency) you'd probably want to come up with a name for it -- "Addable", "Concatable", etc -- and the Haskell community chose "Monoid" (because of relationships to theory etc etc). There are two things I really like about using the name Monoid, compared to the others. First, it's much clearer what the rules are. We aren't stuck wondering whether strings or products are "really" "Addable", whether functions of the form (a -> a) are "really" "Concatable" (... and what about nonempty strings? you can concatenate them, but they have no identity object...). Clarity in an interface means I know what properties I can rely on. You can define those properties precisely with "more intuitive" names, but then the actual interface doesn't match the intuition and people won't realize it, which is worse. You could get precise and intuitive by adding verbosity - "AssociativeOperationWithIdentity". My principle objection there is readability and aesthetics, but if that's what a community wants to go with okay... "Monoid" is short and unambiguous and well established in related fields. That last point touches on the other thing I like. There are mathematical results that can be useful to programmers. Reducing the translation needed helps make those more accessible. And everyone could do with knowing just a bit more algebra :-P
9y ago

danidiaz 9y ago

A monoid is an interface with two operations: one that produces an element out of thin air, and one that combines two elements. It also comes with a contract, like the contracts of "equals", "hashCode" or Comparable in Java. The contract says that the operation must be associative, and that the element you produce out of thin air must be neutral: when you combine it with another element it leaves the other element unchanged. One benefit of having such general interfaces is that you can reuse code across a wide range of domains. For example: the Comparator interface in Java can be seen as a monoid, with the "thenComparing" function as the combination operation: https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html#thenComparing-java.util.Comparator- https://docs.oracle.com/javase/8/docs/api/java/util/Comparat... You could build a list of comparators and concatenate it, map a function that produces a comparator over a list and concatenate it, and so on. Another benefit is that you can be quite general when specifying requirements for your functions. In Haskell, the Writer monad only requires the type of the accumulator to be an instance of Monoid. So you can user regular lists, difference lists, or the integers under addition. Also in Haskell some composite types automatically satisfy an interface if their components do, saving you work. For example, a tuple of monoids is automatically a monoid. Any function that returns a monoid is itself a monoid as well. (Functions that begin and end in the same type can be monoids in a different way: the neutral element is the identity function and the combination operation is composition.)

kreetx 9y ago

Monoid is a type class, similar to interfaces in Java, and this is what it makes easy: if your code uses the monoid interface of some type then you can swap the underlying concrete type without changing your code, and it still works. Obviously, you can do that in any untyped language, too, but explicitly defining these contracts makes code easy to manage and understand. And the compiler will tell you if/how you're doing something wrong.

mightybyte 9y ago

A monoid is something that allows you to take two of the same kind of thing and smash them together to be one of that same kind of thing. It also requires you to have an "empty" thing that can be smashed together with any other thing without changing the result. In code: smash :: Monoid a => a -> a -> a empty :: Monoid a => a A monoid is a property of things, not languages, so the idea of "a language without a monoid" doesn't really make sense.

deleted 9y ago
[deleted]
catnaroek 9y ago
Ah, so this is a monoid: instance Monoid Int where smash 25 x = x smash x 25 = x smash x y = 2*x^2 - 3*x*y empty = 25 Thanks for explaining!
- amelius 9y ago
  I think combining 25 and x should yield x.
  - catnaroek 9y ago
    Oops, yes, my bad.
- deleted 9y ago
  [deleted]
- mjhoy 9y ago
  There are also the monoid "laws" (not checked in Haskell): empty `smash` x = x -- left identity x `smash` empty = x -- right identity (x `smash` y) `smash` z = x `smash` (y `smash` z) -- associativity Your definition doesn't fit any of these. (Edit: you've rewritten to meet the first two; but it is not associative.)
  - conistonwater 9y ago

dmitriid 9y ago

The irony is that there are now 4 monoid tutorials in the replies, and they are all different, and differently confusing :) And there I was, thinking that this only applied to monads :)

throwanem 9y ago
Perhaps someone should come up with a generalizable method for combining monoid tutorials. I wonder what we could call it...
kahnpro 9y ago
Is it really so confusing? I mean, if you understand + for integers and for strings and for lists, and you can understand why this is basically the same operation for all of them, congratulations! you know what a monoid is.
- dmitriid 9y ago
  It's not confusing to me :) I'm just saying that at the time I wrote my comment there where four different comments with four different ways of explaining monoids with four different sets of terminology :)

sillysaurus3 9y ago

A monoid is a method of converting coffee into internet comments about monoids. It's quite ingenious, really.

ostochast 9y ago

For some people it is easier to understand a concept, especialy an abstract one, if they are given a few examples. For those people: A monoid is a set and an binary operation on the elements of that set with the following properties: 1.The operation acts on two elements of the set to produce another elemenent of that set(closure). Examples: You have a set od natural numbers {0,1,2,3..} with standard addition. Whichever two natural numbers you choose to add you will get a natural number back. A set of MxN matrices and matrix addition. If A and B are two MxN matrices A+B is a MxN matrix. 2.The order in which the operations are performed does not matter(associativity). So for all elements of our set a,b and c and the operation +: a+(b+c)=(a+b)+c must be valid. Examples: Let L be a set of strings and + concatenation. "Just"+(" an "+ "example")=("Just"+" an ")+"example" Vector addition over vectors of same dimension. 3.There is an element(unique!) in the set which when applied to any element of the set returns that element(identity, neutral element). e+a=a+e=a e is identity Examples: 0 is identity for standard addition: 0+1=1, 4+0=4 1 is identity for standard multplication: 1*7=7 ""(empty string) is identity for string concatenation

egl2019 9y ago

"Yet another monoid tutorial." This time in Hacker News comments. And lots of them. :-)