6 ms·
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
by wyc 9y ago
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):
-- Zero Value
mempty == {}
-- Append
{"color": "Blue"} `mappend` {"fontSize": 12} == {"color": "Blue", "fontSize": 12}
-- Identity
{"color": "Blue"} `mappend` {} == {"color": "Blue"}
{} `mappend` {"fontSize": 12} == {"fontSize": 12}
-- Associativity
{} `mappend` {"a": "b"} `mappend` {"c": "d"}
== ({} `mappend` {"a": "b"}) `mappend` {"c": "d"}
== {} `mappend` ({"a": "b"} `mappend` {"c": "d"})
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.
- gbacon 9y ago*tenet https://www.google.com/search?q=define%3Atenet https://www.google.com/search?q=define%3Atenet
- wyc 9y agooops thanks
- yanowitz 9y agoThis 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.
- pluma 9y agoThanks. 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.
- equalunique 9y agoLeading up to monads, monoids are covered in this excellent presentation: https://www.youtube.com/watch?v=ZhuHCtR3xq8 https://www.youtube.com/watch?v=ZhuHCtR3xq8
- lou1306 9y agoA tuple is just an ordered bag of elements. E.G. a graph is a tuple (V, E) where V (vertices) is a set and E (edges) is a binary relation between vertices. Defining stuff as tuples makes sense, because then you can define the set of all such tuples (e.g. the set of all monoids for a given set M or the set of all graphs for the given vertices V) and formally reason about it :)
- ebola1717 9y ago> I'm not even sure what "defining it as a tuple" is meant to imply Yeah, in a computer science situation it's needlessly obfuscatory. It's literally just an interface with a "plus" method and an identity value.
- feanaro 9y ago"interface", "method"... One man's obfuscatory is another man's revelatory. It heavily depends on the "axiom set" you first learned about computer science concepts on. I would contend that "interface" and "method" are objectively more obvious concepts.
- reese_john 9y agoThat reminds me of Vector Spaces. Is there any relation? Are Vector Spaces monoids?
- tome 9y agoYes, a vector space is a monoid under its addition.
- Jtsummers 9y agotome speaks the truth. More generally, in mathematics there are hierarchies of structures [0]. In this case monoids are both groupoids/magmas (a set with a binary operation returning elements of that set), and semigroups (a set with an associative binary operation returning elements of that set). Monoids add in an identity element. Vector spaces have addition over vectors and multiplication of vectors by scalars. Considering vector spaces and addition only, that is a monoid. It also happens to be further along this hierarchy as you have commutativity, inverses, and other properties. A bit like the statement: all squares are rectangles, not all rectangles are squares. We can say that all vector spaces are monoids (under addition), but not all monoids are vector spaces. [0] https://en.wikipedia.org/wiki/Algebraic_structure https://en.wikipedia.org/wiki/Algebraic_structure
- dllthomas 9y agoIt's maybe worth noting that we have a choice of how values are merged on collision. I think it's a monoid only when that choice forms a semigroup. 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.
- whateveracct 9y agoYeah the Map monoid instance is very unfortunate :( When I came from Scala I really missed the one in scalaz (which is as you describe) reducers has a UnionWith newtype which gives you the better Map monoid. But I think it uses a lazy unionWith, which will cause your Map to leak space when used in a foldMap over many elements :(
- a-saleh 9y agoYep, 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] :) [1] https://www.youtube.com/watch?v=WsA7GtUQeB8 https://www.youtube.com/watch?v=WsA7GtUQeB8 [2] http://notes.asaleh.net/posts/monoid-pattern-in-python/ http://notes.asaleh.net/posts/monoid-pattern-in-python/ [3] http://notes.asaleh.net/posts/monoid-for-specifying-configuration/ http://notes.asaleh.net/posts/monoid-for-specifying-configur...
- rmetzler 9y agoCan 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.