3 ms·

Thanks for the explanation. Such things continue to be impenetrable to me, I guess I will keep trying.

jerf 12y ago
Monads are legitimately a bit tricky. They do things with closures that you do not generally get exposed to in imperative languages, even ones with very solid closure support. There is an "aha!" moment for most people. Perhaps less so than some people's attempts to explain it would imply, but there is legitimately an "aha!" Monoids are so easy that the biggest impediment to understanding them is believing that they really are that easy, possibly due to a "halo effect" from the similarity with the word "monad". Do you have: 1. An associative operation, that is, a <+> (b <+> c) = (a <+> b) <+> c 2. A single "zero" such that 0 <+> a = a <+> 0 = a Then you have a monoid. That's it. Seriously, that's it. There's nothing more. I've represented the operation by <+> because traditionally it involves a "+" since it is most like the plus operator, and I'm too lazy to go get the traditional +-with-circle operator. If you "de-math" the linked page you'll find that's what it says, but it does make sort of heavy weather of it by comparison. Category theory tends to do that to people. I've on occasion been tempted to try to write a "practical category theory" guide myself, because I really feel like even the ones so labeled get caught up in the math and never provide any solid examples. Just a handful of trivial examples that leave a casual reader unable to figure out how to apply the idea to more complicated ones. So, in the interests of me not being a hypocrite, let me reiterate the trivial examples, then provide a non-trivial example of something a fluent Haskell programmer would not even blink at implementing. For lists, the <+> operator is "list concatenation", which is associative, and the 0-element is the empty list. Integers are an interesting case, as both conventional addition (with the 0-element being literally 0) and conventional multiplication (with the 0-element being 1 here!) form a monoid. So, how do you "use" monoids? Like any other interface, you create functions that generically take in "a monoid" and do something useful with its operation. Here's an example. Suppose you have two hash tables, and the values are known to be monoids. Now you can create a "combine" function that can losslessly combine two hash tables. If a key exists in either table alone, it will just be copied through, but if it exists in both tables, the resulting value is "left value <+> right value". Now what happens? Well, if the hash table is full of "strings", you'll get the concatenation of both. If the hash table is full of "addition-monoid numbers", the exact same function will now return the summed total of both hash tables. If the hash table is full of lists of some value of type "X", you'll now get a hash table that has all of the values in the lists. All the same function. As someone else points out, monoids are also parallelizable. You're 80% of the way to a distributed map-reduce-esque counting algorithm with just hash tables and the monoidal combining operator I just described. This is the value of "monoids"... not that you would use the interface when you have a concrete class in hand, but that you can use the interface to write generic functions where you just have to pass them some 0-value and some way of combining two values together, and they know how to do "something" based on that information, despite not understanding the type itself. The hash table implementation above does not know about "lists" or "numbers" or "strings"... it just knows that it has "things it can combine". Because monoids are so simple, you have them all over the place and don't realize it. Here's a really complicated example from the world of practical software engineering: Permissions ought to be monoids. If you have one object that gives you permissions A, B, and C, and another that gives you A, D, and E, you ought to have an operation that will combine them into an object that gives permissions for A, B, C, D, and E. If you have the ability to grant "permission X, except not X's starting with 'a'", you have a permission system that will be insanely difficult to understand once people start actually using it. How do you combine "permission X" with "permission X but not starting with 'a'"? (Either of the two obvious answers is guaranteed to be both what one user intended and not what another user intended. This is not a good characteristic to put into your security system.) And of course you have a "zero-object", a permissions object that grants no permissions at all. And... if you have this and you've explained to your system that it is a monoid, the aforementioned hash table will happily take permissions as its values and happily combine them together even though the person writing the hash table implementation certainly did not have your permissions objects in mind at the time! Anyhow, that's really all there is. 0-value, associative combiner, wrapped in an interface. You can use that in a huge variety of ways, but the concept itself is really that simple.
- codygman 12y ago
  Wow, I'm going to use this to explain monoids in the future. Great explanation!

jerf 12y ago

Monads are legitimately a bit tricky. They do things with closures that you do not generally get exposed to in imperative languages, even ones with very solid closure support. There is an "aha!" moment for most people. Perhaps less so than some people's attempts to explain it would imply, but there is legitimately an "aha!" Monoids are so easy that the biggest impediment to understanding them is believing that they really are that easy, possibly due to a "halo effect" from the similarity with the word "monad". Do you have: 1. An associative operation, that is, a <+> (b <+> c) = (a <+> b) <+> c 2. A single "zero" such that 0 <+> a = a <+> 0 = a Then you have a monoid. That's it. Seriously, that's it. There's nothing more. I've represented the operation by <+> because traditionally it involves a "+" since it is most like the plus operator, and I'm too lazy to go get the traditional +-with-circle operator. If you "de-math" the linked page you'll find that's what it says, but it does make sort of heavy weather of it by comparison. Category theory tends to do that to people. I've on occasion been tempted to try to write a "practical category theory" guide myself, because I really feel like even the ones so labeled get caught up in the math and never provide any solid examples. Just a handful of trivial examples that leave a casual reader unable to figure out how to apply the idea to more complicated ones. So, in the interests of me not being a hypocrite, let me reiterate the trivial examples, then provide a non-trivial example of something a fluent Haskell programmer would not even blink at implementing. For lists, the <+> operator is "list concatenation", which is associative, and the 0-element is the empty list. Integers are an interesting case, as both conventional addition (with the 0-element being literally 0) and conventional multiplication (with the 0-element being 1 here!) form a monoid. So, how do you "use" monoids? Like any other interface, you create functions that generically take in "a monoid" and do something useful with its operation. Here's an example. Suppose you have two hash tables, and the values are known to be monoids. Now you can create a "combine" function that can losslessly combine two hash tables. If a key exists in either table alone, it will just be copied through, but if it exists in both tables, the resulting value is "left value <+> right value". Now what happens? Well, if the hash table is full of "strings", you'll get the concatenation of both. If the hash table is full of "addition-monoid numbers", the exact same function will now return the summed total of both hash tables. If the hash table is full of lists of some value of type "X", you'll now get a hash table that has all of the values in the lists. All the same function. As someone else points out, monoids are also parallelizable. You're 80% of the way to a distributed map-reduce-esque counting algorithm with just hash tables and the monoidal combining operator I just described. This is the value of "monoids"... not that you would use the interface when you have a concrete class in hand, but that you can use the interface to write generic functions where you just have to pass them some 0-value and some way of combining two values together, and they know how to do "something" based on that information, despite not understanding the type itself. The hash table implementation above does not know about "lists" or "numbers" or "strings"... it just knows that it has "things it can combine". Because monoids are so simple, you have them all over the place and don't realize it. Here's a really complicated example from the world of practical software engineering: Permissions ought to be monoids. If you have one object that gives you permissions A, B, and C, and another that gives you A, D, and E, you ought to have an operation that will combine them into an object that gives permissions for A, B, C, D, and E. If you have the ability to grant "permission X, except not X's starting with 'a'", you have a permission system that will be insanely difficult to understand once people start actually using it. How do you combine "permission X" with "permission X but not starting with 'a'"? (Either of the two obvious answers is guaranteed to be both what one user intended and not what another user intended. This is not a good characteristic to put into your security system.) And of course you have a "zero-object", a permissions object that grants no permissions at all. And... if you have this and you've explained to your system that it is a monoid, the aforementioned hash table will happily take permissions as its values and happily combine them together even though the person writing the hash table implementation certainly did not have your permissions objects in mind at the time! Anyhow, that's really all there is. 0-value, associative combiner, wrapped in an interface. You can use that in a huge variety of ways, but the concept itself is really that simple.

codygman 12y ago
Wow, I'm going to use this to explain monoids in the future. Great explanation!