Here's the ELI5 of monoids used in programming that might help get the idea across:
Conceptually, a monoid is anything that:
- Has a "zero-value" (mempty, e.g., 0)
- Can be "appended" together (mappend, e.g., +)
- Has an identity with the zero-value: x + 0 == x, 0 + x == x
- Is associative: x + y + z == (x + y) + z == x + (y + z)
This isn't limited to just arithmetic with operators like +. You can define whole new types as monoids if they have these characteristics. For example, we can merge together configuration files by using monoid operators (in pseudo-code):
There's no need to break out the really formal definitions if you're just trying to get some nice working code.
Borrowing from mathematics is beneficial because we can work with structures that have simple but useful guarantees. In Haskell, you can expect all the above to be true for correct type instances of Monoid, without the implementation details at hand. It's a core tenet of functional programming to disarm complexity with simplicity.
Thanks. This is a lot more helpful for non-math geeks than the two initial definitions in the article:
> A Monoid can be defined a tuple (M, op, e)
This definition lost me completely because I'm not even sure what "defining it as a tuple" is meant to imply. Based on your explanation it sounds like that is fancy talk for saying it is defined by having three properties.
> In a statically typed language, we can translate the notion of set into the notion of type.
The second definition again completely lost me because I'm not even sure what "set" and "type" mean in this context and being able to "translate the notion of set" is unhelpful when the definition using a set is the one I didn't understand in the first place.
I'm a programmer with over a decade of professional experience. I don't understand the article because I have no formal education in higher math nor in anything beyond basic computer science. Your explanation proves it's possible to explain these concepts with practical examples rather than academic jargon.
This is a great summary. I think it's valuable to say that learning how to map your problem domain onto instances of categories like Monoid is useful because it immediately makes your problem embarassingly parallel, because you can parallelize the addition process (just making sure to preserve overall ordering of operations). I.e., map/reduce. And if it's a commutative monoid, you don't even have to sweat the ordering.
Yep, when I was trying to understand the fuss about monoids (I blame Gabriel Gonzales excelent talk [1]), I made myself a little toy EDSL for configuration in Python, that was made mostly by implementing mappend for dictionaries [3] :)
Can I use a composite object or dict for the type?
So all you need to do is to create the null object and the add and sub function on the type? And I can use an implementation of that type as the state for something?
How can I guarantee the order? Would I need to use something like a blockchain or is a distributed database enough, as long as only I need the data and trust myself? In a cluster would it make sense to use etcd
I think, even better would be a commutative monoid, that doesn't depend on the order. It should be possible to scale the global state in a distributed system very concurrent, because of the commutativity.
I would have to store a log (easiest part) and the current state. To sync state between the nodes in a distributed system, they would have to send update messages to each other. They're able to batch process multiple messages to improve throughput.
It's always amusing to watch programmers learn a tiny piece of mathematics and turn into a totem. All those data structures would work just as fine without a monoid formalization, and one can use all their power with no attention given to algebraic axioms that define a monoid.
I'm not sure why it's interesting to label all these things as monoids. It seems kind of the tail wagging the dog.
More concretely, "monoid" seems both too general and too specific to be useful. Things that commute and things that don't commute are lumped together as monoids, and that seems to be a much more useful distinction.
Consider the monoids described in the article. For concatenation and file paths, order is important. On the other hand, multiplication, addition, maps, sets, and the shape examples all commute, so the ordering a monoid gives you is irrelevant. How does it help to consider both concatenation and addition as monoids?
(I'm honestly trying to see the relevance of monoids.)
For me it gets interesting when you compose monoids, and that article has several elegant examples.
Otherwise I think the monoid structure is not super interesting in itself, but it's a really useful building block when thinking of software "algebraically", which to me is the most interesting aspect of Haskell as a programming tradition.
As for commutativity, I'm not sure how to answer. The monoid notion is useful in both commutative and noncommutative settings. When composing monoids one might be commutative and others noncommutative (like, say, a tuple of int and list of strings, the int being a total size and the strings being file names).
It's useful when you write functions that take generic monoids as arguments, such as many aggregation functions on data structures. For instance, finding the largest element in a tree, or the first successful result in a list of actions. Structuring the code like this separates the concerns of traversing the data structure and performing the particular type of aggregation. Haskell has the function foldMap which implements this idea.
I can't speak to the relevance of monoids (I don't have much experience with FP) but to me those examples are helpful in illustrating the definition. It's easy to assume associativity <=> commutativity until presented with counterexamples.
OK... So exactly why is it useful to me, as someone writing programs in the real world rather than theorising about how computation works, that a list type under concatenation and a money type under summation are monoids? Can I actually write useful code with this knowledge?
At least in C++, knowing your type forms a monoid with your operation informs you when you are safe to use various parallel algorithms. e.g. `std::accumulate` with an associative operator is safe to run in parallel.
Sometimes learning things like this actually changes the way you think. You might not notice it the first month you study these things, but little by little you'll grow comfortable with it and eventually it becomes second nature. Eventually this can help you reason about things in ways you weren't able to before, which is useful for certain especially challenging scenarios.
If you code Haskell then you'll run into monoids all the time, and if you understand what that word means then you can write more concise and idiomatic code that makes use of the wide range of monoid instances available under the common monoid API.
You can then make sure to expose the monoid interface for users of your Haskell libraries and they'll be happier because your values will cleanly fit with the rest of the ecosystem.
If you don't code Haskell then it's not like monoids are crucial learning for a successful career. Maybe you could approach them with some curiosity and find something interesting and useful about basic algebraic structures.
But probably all these monoid nerds are just puttin' you on...
If you don't work in a language with a type system sufficiently powerful enough to express monoids, or weak enough to express monoids dynamically, there's not much practical value. But note that while cleanly expressing the monad interface is challenging for a type system, monoid is not so hard, and most things that have interfaces or concepts or traits or something like that can do it. At that point you can write generic code that uses them, and you'd be surprised how much value you can get out of that. You write a lot of code manually doing things to monoids that you could have done once.
(It is unfortunate that monoids sound like monad's more complicated brother, when in fact it is exactly the opposite way around. Monoids are so simple that a common reaction once you actually get it is to go "Seriously? That's it?")
The other useful thing about monoids is that because of the associativity, they provide a useful, yet easy, way of breaking up a task for multiprocessing. If you can prove that your data type and the operations you desire to use on it are monoidal (and by "prove" I mean the informal sort of things programmers do all the time, not grabbing a proof system and going at it), then you have some really easy options, and it's really easy to write a system that very cleanly breaks up "the strategy of how I'm going to multiprocess this" from "what it is I want to multiprocess".
Because of this, it is likely that you're going to continue hearing more about these things over time, rather than less. Monoids are just about the simplest non-trivial example of such things, and the more sophisticated steps up (lattices, CRDTs [1]) are probably also things you're going to hear more about in the future.
Personally, I think in a lot of ways we are still have collectively done next to nothing as a community to address the multicore world we live in. Right now we're taking advantage of some things like Go's green threads or "asynchronous" programming to deal with the common case where we have some problem where a single core is adequate to solve it, but we need some complicated scheduling or we have huge numbers of these relatively small problems coming at us at once, but we still have made very little progress in doing complex tasks truly in parallel. It is very likely that those solutions are going to involve coming to understand these mathematical abstractions and why they are important. Monoid is going to be the first of them you'll encounter, because it is, as I said, probably the simplest non-trivial one. But on its own it won't get you all that far in general.
This post does a great job of linking the elements of the mathematical definition of a monoid with their usefulness in code, helping explain why monoids are so outstandingly useful in programming. If you've ever wondered why it's monoids that come up over and over again in programming instead of another mathematical abstraction, this article will help.
I think "outstandingly useful" is a bit strong and I think it polarizes people who are on the fence on whether the concept is practically useful or just formalistic jargon.
This is a great introduction to monoids. The shape example actually appeared in a study performed in the early 90s [0]. I'm not convinced that you can draw too many valuable conclusions from the study, but it's a fun, quick paper to read.
The shape example reminds me of how traditional raytracing renderers work: the entire scene is a function whose input is [x,y] view space coordinates and output is [r,g,b] color. To produce an image, you call the function for each pixel and store the results.
Could be an interesting tutorial to see a raytracer explained in terms of monoids.
This is awesome. That's the first explanation of the subject that actually made sense to me, and made me understand why I should care. Thanks for sharing!
fun fact: you can run shortest path algorithms on pretty much everything as long as it fulfills the monoid constraints (taking min and combining paths, operating on distances is a monoid)
so basically, for the cost of implementing two operations you can reuse dijkstra or bellman-ford to do crazy stuff like belief propagation etc
Could anyone provide a "real world," or generic business coding (database, input validation, etc, etc..) example that demos rates their usefulness outside of a pure "mathy" domain.
I find that most of these fp examples tend to focus on simple things like shapes which tend to already have monoid properties built in. I'd be interested in seeing examples of how they help your kind of run of the mill business coding.
Coming from an OOP background what made me connect some dots about what the monoids are and what are they good for after reading the article is that they can also be viewed as the GOF composite pattern.
I've just stumbled upon an article that describes this:
Monoids (& monads) are one of those tools that I think help shape your thinking (like FP) and, even if you don’t use them daily or regularly... still help make you a better programmer to understand.
The concepts are actually very simple but their effects are complex. This is great introduction though I think a little high level for beginners.
For those that like SICP, the picture language in section 2.2.4 describes a monoid, though they don't call it that because the term hadn't yet been adopted. Even so, I found it very helpful in understanding what all the monoid literature was going on about because I'm much more familiar with Lisp than I am statically typed ML-family languages.
The word "monoid" has been used with its current meaning since the 50s, maybe before.
I think the authors of SICP didn't describe the picture language as such because it just isn't a very useful concept, not because they didn't know the word.
A bit of advice about understanding concepts like these:
You don't understand every single instance. You understand the concept, and then you begin to learn individual instances.
The shape and the use of monoids is really easy to grasp. Sometimes understanding how a thing is specifically is a monoid or how it's implemented can be obscure. They are similar to monads in this respect, although often less complicated.
In summary, understand that there is a beach and that the beach is made of many grains of sand. Each grain of sand may not be obvious from just staring at the beach.
People are awful at explaining Monad-related concepts. I think everyone starts with a reasonable explanation and then tweak it to be more succinct until they end up "a monad is just a monoid in the category of endofunctors"
It's a stupid over-complication of stuff you do every day while programming. It's these annoying science-y, elitist words that keep people away from programming.
A monoid is just an operation you perform on things that are similar. The concat() function in JS is a monoid.
import Data.Aeson (Value, encode)
instance Postable Value where
postPayload = putPayload
Why is it so difficult to do a simple task like finding all instances of a typeclass? In a Java IDE finding the implementations of an interface is just a single button away and fully automated. Of course I'm assuming that you've already imported the library that contains the typeclass instance. In this case the instances are part of the wreq library themselves and not of aeson or some plugin that you use to connect wreq and aeson. If hoogle worked as I think it should it could even be superior to a local search that only considers libraries that are part of your project. I'm a big fan of self documentation and like the type-aware documentation but this is a case where although it took a short time I've wasted more time than I'm comfortable with for a simple program that could be written in python or whatever instead.
I don't care about category theory at all and you can have all the practical benefits of category theory without putting it on a pedestial. It's neat to write more generic functions and stuff but there is no need to glorify it.
From a practical standpoint monoid, monad and functor you can think of them as an interface. When your code accepts a specific implementation like ArrayList you can in some cases instead use the java interface List to make your code more generic. When your code accepts a specific implementation like Maybe or List then sometimes you can use the Monad typeclass to make your code more generic.
[+] [-] wyc|8 years ago|reply
Conceptually, a monoid is anything that:
- Has a "zero-value" (mempty, e.g., 0)
- Can be "appended" together (mappend, e.g., +)
- Has an identity with the zero-value: x + 0 == x, 0 + x == x
- Is associative: x + y + z == (x + y) + z == x + (y + z)
This isn't limited to just arithmetic with operators like +. You can define whole new types as monoids if they have these characteristics. For example, we can merge together configuration files by using monoid operators (in pseudo-code):
There's no need to break out the really formal definitions if you're just trying to get some nice working code.Borrowing from mathematics is beneficial because we can work with structures that have simple but useful guarantees. In Haskell, you can expect all the above to be true for correct type instances of Monoid, without the implementation details at hand. It's a core tenet of functional programming to disarm complexity with simplicity.
[+] [-] pluma|8 years ago|reply
> A Monoid can be defined a tuple (M, op, e)
This definition lost me completely because I'm not even sure what "defining it as a tuple" is meant to imply. Based on your explanation it sounds like that is fancy talk for saying it is defined by having three properties.
> In a statically typed language, we can translate the notion of set into the notion of type.
The second definition again completely lost me because I'm not even sure what "set" and "type" mean in this context and being able to "translate the notion of set" is unhelpful when the definition using a set is the one I didn't understand in the first place.
I'm a programmer with over a decade of professional experience. I don't understand the article because I have no formal education in higher math nor in anything beyond basic computer science. Your explanation proves it's possible to explain these concepts with practical examples rather than academic jargon.
[+] [-] yanowitz|8 years ago|reply
[+] [-] dllthomas|8 years ago|reply
In the case of configurations, "right bias" (aka Last) is probably a good choice. I don't like that Haskell chose it for the general Map instance.
[+] [-] a-saleh|8 years ago|reply
[1] https://www.youtube.com/watch?v=WsA7GtUQeB8 [2] http://notes.asaleh.net/posts/monoid-pattern-in-python/ [3] http://notes.asaleh.net/posts/monoid-for-specifying-configur...
[+] [-] rmetzler|8 years ago|reply
So all you need to do is to create the null object and the add and sub function on the type? And I can use an implementation of that type as the state for something?
How can I guarantee the order? Would I need to use something like a blockchain or is a distributed database enough, as long as only I need the data and trust myself? In a cluster would it make sense to use etcd
I think, even better would be a commutative monoid, that doesn't depend on the order. It should be possible to scale the global state in a distributed system very concurrent, because of the commutativity.
I would have to store a log (easiest part) and the current state. To sync state between the nodes in a distributed system, they would have to send update messages to each other. They're able to batch process multiple messages to improve throughput.
[+] [-] gbacon|8 years ago|reply
https://www.google.com/search?q=define%3Atenet
[+] [-] reese_john|8 years ago|reply
[+] [-] dkural|8 years ago|reply
[+] [-] kens|8 years ago|reply
More concretely, "monoid" seems both too general and too specific to be useful. Things that commute and things that don't commute are lumped together as monoids, and that seems to be a much more useful distinction.
Consider the monoids described in the article. For concatenation and file paths, order is important. On the other hand, multiplication, addition, maps, sets, and the shape examples all commute, so the ordering a monoid gives you is irrelevant. How does it help to consider both concatenation and addition as monoids?
(I'm honestly trying to see the relevance of monoids.)
[+] [-] mbrock|8 years ago|reply
http://repository.upenn.edu/cgi/viewcontent.cgi?article=1773...
For me it gets interesting when you compose monoids, and that article has several elegant examples.
Otherwise I think the monoid structure is not super interesting in itself, but it's a really useful building block when thinking of software "algebraically", which to me is the most interesting aspect of Haskell as a programming tradition.
As for commutativity, I'm not sure how to answer. The monoid notion is useful in both commutative and noncommutative settings. When composing monoids one might be commutative and others noncommutative (like, say, a tuple of int and list of strings, the int being a total size and the strings being file names).
[+] [-] chas|8 years ago|reply
If this is interesting to you Dan Piponi goes into significantly more detail (http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-use...).
[+] [-] tome|8 years ago|reply
https://news.ycombinator.com/item?id=15242204
[+] [-] smelterdemon|8 years ago|reply
[+] [-] rbehrends|8 years ago|reply
[+] [-] vertex-four|8 years ago|reply
[+] [-] bstamour|8 years ago|reply
[+] [-] tw1010|8 years ago|reply
[+] [-] mbrock|8 years ago|reply
You can then make sure to expose the monoid interface for users of your Haskell libraries and they'll be happier because your values will cleanly fit with the rest of the ecosystem.
If you don't code Haskell then it's not like monoids are crucial learning for a successful career. Maybe you could approach them with some curiosity and find something interesting and useful about basic algebraic structures.
But probably all these monoid nerds are just puttin' you on...
[+] [-] Dolores12|8 years ago|reply
[+] [-] jerf|8 years ago|reply
(It is unfortunate that monoids sound like monad's more complicated brother, when in fact it is exactly the opposite way around. Monoids are so simple that a common reaction once you actually get it is to go "Seriously? That's it?")
The other useful thing about monoids is that because of the associativity, they provide a useful, yet easy, way of breaking up a task for multiprocessing. If you can prove that your data type and the operations you desire to use on it are monoidal (and by "prove" I mean the informal sort of things programmers do all the time, not grabbing a proof system and going at it), then you have some really easy options, and it's really easy to write a system that very cleanly breaks up "the strategy of how I'm going to multiprocess this" from "what it is I want to multiprocess".
Because of this, it is likely that you're going to continue hearing more about these things over time, rather than less. Monoids are just about the simplest non-trivial example of such things, and the more sophisticated steps up (lattices, CRDTs [1]) are probably also things you're going to hear more about in the future.
Personally, I think in a lot of ways we are still have collectively done next to nothing as a community to address the multicore world we live in. Right now we're taking advantage of some things like Go's green threads or "asynchronous" programming to deal with the common case where we have some problem where a single core is adequate to solve it, but we need some complicated scheduling or we have huge numbers of these relatively small problems coming at us at once, but we still have made very little progress in doing complex tasks truly in parallel. It is very likely that those solutions are going to involve coming to understand these mathematical abstractions and why they are important. Monoid is going to be the first of them you'll encounter, because it is, as I said, probably the simplest non-trivial one. But on its own it won't get you all that far in general.
[1]: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
[+] [-] dkarl|8 years ago|reply
[+] [-] tw1010|8 years ago|reply
[+] [-] ShaneWilton|8 years ago|reply
[0] "haskell vs. ada vs. c++ vs awk vs ... an experiment in software prototyping productivity" - http://www.cs.yale.edu/publications/techreports/tr1049.pdf
[+] [-] pavlov|8 years ago|reply
Could be an interesting tutorial to see a raytracer explained in terms of monoids.
[+] [-] mazelife|8 years ago|reply
[+] [-] kstrauser|8 years ago|reply
[+] [-] fulafel|8 years ago|reply
https://clojuredocs.org/clojure.core.reducers/monoid & https://github.com/clojure/clojure/blob/f572a60262852af68cdb...
For the idea, I think https://en.wikibooks.org/wiki/Haskell/Monoids is better than this post.
[+] [-] r41nbowdash|8 years ago|reply
so basically, for the cost of implementing two operations you can reuse dijkstra or bellman-ford to do crazy stuff like belief propagation etc
http://www.morganclaypool.com/doi/abs/10.2200/S00245ED1V01Y2...
[+] [-] goostavos|8 years ago|reply
I find that most of these fp examples tend to focus on simple things like shapes which tend to already have monoid properties built in. I'd be interested in seeing examples of how they help your kind of run of the mill business coding.
[+] [-] Vunovati|8 years ago|reply
I've just stumbled upon an article that describes this:
http://blog.plasmaconduit.com/the-composite-pattern-and-mono...
[+] [-] abritinthebay|8 years ago|reply
The concepts are actually very simple but their effects are complex. This is great introduction though I think a little high level for beginners.
[+] [-] umanwizard|8 years ago|reply
I can't tell why monoids are supposed to be more directly applicable to programming than any other concept from algebra.
[+] [-] graphememes|8 years ago|reply
[+] [-] davexunit|8 years ago|reply
http://sarabander.github.io/sicp/html/2_002e2.xhtml#g_t2_002...
[+] [-] umanwizard|8 years ago|reply
I think the authors of SICP didn't describe the picture language as such because it just isn't a very useful concept, not because they didn't know the word.
[+] [-] baybal2|8 years ago|reply
[+] [-] zephyz|8 years ago|reply
You have another value of the same type.
If there exist a function (let's call it "combine") that combines those two values and emits a third value of the same type.
AND
There exists a value of this type that does nothing when used as argument to this "combine" function.
then your type is a monoid. (basically)
[+] [-] KirinDave|8 years ago|reply
You don't understand every single instance. You understand the concept, and then you begin to learn individual instances.
The shape and the use of monoids is really easy to grasp. Sometimes understanding how a thing is specifically is a monoid or how it's implemented can be obscure. They are similar to monads in this respect, although often less complicated.
In summary, understand that there is a beach and that the beach is made of many grains of sand. Each grain of sand may not be obvious from just staring at the beach.
[+] [-] smcl|8 years ago|reply
[+] [-] dualogy|8 years ago|reply
[+] [-] jbob2000|8 years ago|reply
A monoid is just an operation you perform on things that are similar. The concat() function in JS is a monoid.
[+] [-] ksenzee|8 years ago|reply
> Relative paths in a file system form a Monoid under appending
How can appending be associative?
[+] [-] jpfed|8 years ago|reply
[+] [-] jhomedall|8 years ago|reply
associative: (a + b) + c = a + (b + c)
commutative: a + b = b + a
For example, appending strings is associative, but not commutative. Appending items to an unordered set is both associative and commutative.
[+] [-] Koshkin|8 years ago|reply
[+] [-] unknown|8 years ago|reply
[deleted]
[+] [-] yexponential|8 years ago|reply
missed a word: Able to tell.
[+] [-] deque-blog|8 years ago|reply
[+] [-] imtringued|8 years ago|reply
I took a look at docs and found the function definition for a post request.
https://hackage.haskell.org/package/wreq-0.5.1.0/docs/Networ...
We can see that the second parameter should be an instance of the Postable typeclass.The examples mention using a JSON value as a parameter
By looking at the definition of toJSON definition we know that toJSON returns a valuehttps://hackage.haskell.org/package/aeson-1.2.1.0/docs/Data-...
Just seeing a single example isn't enough for me to generalise though.
I proceed to go to the definition of the Postable typeclass.
https://hackage.haskell.org/package/wreq-0.5.1.0/docs/Networ...
Unfortunately it doesn't list the instances of the typeclass so I decide to use hoogle.
https://www.haskell.org/hoogle/?hoogle=Postable
No results found.
I then start looking at the source code of the library until I found this file which contains the Postable instance for json values.
https://hackage.haskell.org/package/wreq-0.5.1.0/docs/src/Ne...
Why is it so difficult to do a simple task like finding all instances of a typeclass? In a Java IDE finding the implementations of an interface is just a single button away and fully automated. Of course I'm assuming that you've already imported the library that contains the typeclass instance. In this case the instances are part of the wreq library themselves and not of aeson or some plugin that you use to connect wreq and aeson. If hoogle worked as I think it should it could even be superior to a local search that only considers libraries that are part of your project. I'm a big fan of self documentation and like the type-aware documentation but this is a case where although it took a short time I've wasted more time than I'm comfortable with for a simple program that could be written in python or whatever instead.I don't care about category theory at all and you can have all the practical benefits of category theory without putting it on a pedestial. It's neat to write more generic functions and stuff but there is no need to glorify it.
From a practical standpoint monoid, monad and functor you can think of them as an interface. When your code accepts a specific implementation like ArrayList you can in some cases instead use the java interface List to make your code more generic. When your code accepts a specific implementation like Maybe or List then sometimes you can use the Monad typeclass to make your code more generic.