16 ms·
What Monoids teach us about software
- mazelife 9y agoThere's a good blog post as a kind of follow-up to this one that talks about how thinking in terms of monoids helps enable flat architectures and composability in Haskell: http://www.haskellforall.com/2014/04/scalable-program-architectures.html http://www.haskellforall.com/2014/04/scalable-program-archit...
- ShaneWilton 9y agoThis 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. [0] "haskell vs. ada vs. c++ vs awk vs ... an experiment in software prototyping productivity" - http://www.cs.yale.edu/publications/techreports/tr1049.pdf http://www.cs.yale.edu/publications/techreports/tr1049.pdf
- pavlov 9y agoThe 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.
- baybal2 9y agoI still didn't get it. I need a simpler explanation and examples
- dualogy 9y agoI summarized a decent Reddit thread on the topic a while back here: http://metaleap.net/blog.hasplained-monoids.html http://metaleap.net/blog.hasplained-monoids.html
- KirinDave 9y agoA 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.
- smcl 9y agoPeople 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"
- tw1010 9y agoThis article is about Monoids, not Monads. Monoids are simple. Just imagine a bunch of things, and imagine you can "combine" any arbitrary thing to another thing. The combination has the property of being associative (whatever) and you're only allowed to called it a monoid (otherwise convention says you need to call it a semigroup) if there is also an item (the "identity" or "neutral" element) which when you combine it with any arbitrary item, produces that same item as a result. Common examples are: strings which you're allowed to combine with concatenation (with the empty string being the "neutral" element). Integers with addition as the combiner is also a monoid that also has a few additional named properties (like commutativity and existence of inverses) but they're still monoids.
- umanwizard 9y agoBy "monad-related concepts" do you just mean abstract algebra? Otherwise, how are monoids and monads related, other than that they are both algebraic structures?
- smcl 9y agoMy comment was pretty poorly written, and is probably better understood in terms of just "explanations of things starting with mon-" :-D The concepts aren't tough, people are just pretty bad at putting themselves in the shoes of a learner, and throw bizarre over-complicated descriptions and examples into the mix when explaining them. The description I gave is someone's tongue-in-cheek stab at these which has stuck with me (unless I'm horrendously off and that is actually someone's legit attempt to describe monads)
- zephyz 9y agoYou have a value of a certain type. 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)
- jerf 9y agoYou left off the associativity; you need (a + (b + c)) == ((a + b) + c), where + is the combining operation.
- zephyz 9y agoI did. I left it out for two reasons: - the comment asked for a "simpler" explanation and associativity isn't a specially simple concept if you are not familiar with it and does not really help understand the core idea of a monoid. - in practice, monoid associativity isn't checked. Most type system aren't able to express it. Therefore, whenever you encounter a monoid you have no guarantee that it is indeed associative.
- feanaro 9y agoThere may be no guarantee, but that doesn't make a structure without associativity any more of a monoid, nor is having an identity element without associativity the core of idea of a monoid. If anything, associativity is the more important part of the concept since without an identity element, you are still left with a semigroup.
- jbob2000 9y agoIt'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.
- yexponential 9y ago> Given a value, we do not have to care how it was built, and whether it is a composite or not. We might not be even to tell (*). missed a word: Able to tell.
- deque-blog 9y agoThank you and good catch :) I corrected it.
- fulafel 9y agoFor Clojurists: https://clojuredocs.org/clojure.core.reducers/monoid https://clojuredocs.org/clojure.core.reducers/monoid & https://github.com/clojure/clojure/blob/f572a60262852af68cdb561784a517143a5847cf/src/clj/clojure/core/reducers.clj#L320 https://github.com/clojure/clojure/blob/f572a60262852af68cdb... For the idea, I think https://en.wikibooks.org/wiki/Haskell/Monoids https://en.wikibooks.org/wiki/Haskell/Monoids is better than this post.
- abritinthebay 9y agoMonoids (& 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.
- umanwizard 9y agoWhy monoids? Why not groups? Why not vector spaces? I can't tell why monoids are supposed to be more directly applicable to programming than any other concept from algebra.
- Koshkin 9y agoThey are all applicable, it's just that the notion of monoid is more general and thus its area of applicability is bigger. [Edit] On the other hand, it is important to realize that even though these structures look (and indeed are) related, each focuses on a completely different aspect of reality. Monoids are useful in describing composability (where associativity is essential); groups are instrumental in analyzing all kinds of symmetries; vector spaces form a scene on which one deals with linear independence, subspaces, and linear transformations. (All this finds its application in computational algorithms, but it would be interesting to see if the program structure also could be understood using the notion of symmetry and/or linearity.)
- tome 9y agoI'll assume this a genuine question and give a genuine answer. > Why not groups? Because many things you would want to combine don't have inverses. Does the list [1,2,3] have an inverse? No. That's why lists form a monoid and not a group. > Why not vector spaces? Because all finite dimensional real vector spaces are isomorphic to R^n so we tend just to use the concrete instances of tuples of floating point numbers.
- chas 9y agoAssociative operators with an identity are extremely common in programming, inverses are much less common. Most ways to turn a lot of data into a little data have a monoid hidden in them with the identity serving as a default value in the case of missing data. There is nothing you can comcatenate to a list to get the empty list, nothing you can OR with True to get False, and nothing you can union with a set to get the empty set.
- davexunit 9y agoFor 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. http://sarabander.github.io/sicp/html/2_002e2.xhtml#g_t2_002e2_002e4 http://sarabander.github.io/sicp/html/2_002e2.xhtml#g_t2_002...
- umanwizard 9y agoThe 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.
- davexunit 9y agoIt wasn't a term used in computer science then. Gerald Sussman himself said this about the term "monad" in one of his talks.
- kazinator 9y agoA monoid is just an algebraic group which is missing the concept of the inverse element. This has been gutted out of the group so that the category theorists can then see monoids in situations where they would otherwise have to rack their brains to come up with the inverse operation. https://en.wikipedia.org/wiki/Group_(mathematics)#Definition https://en.wikipedia.org/wiki/Group_(mathematics)#Definition For instance, the set of character strings and the catenate operation are almost a group. The identity element is the empty string. Closure holds: if a and b are strings, (cat a b) is a string. Associativity holds : (cat a (cat b c)) is (cat (cat a b) c). (Which is then just (cat a b c) to a Lisp programmer, (cat a) is a, and (cat) produces the empty string.) Identity element: empty string. (cat a "") -> a Inverse element: oops! We would have to postulate some sort of "negative string" so that (cat "abc" -"abc") produces "". Then we have the problem of what is (cat "abc" -"xyz"): the combination of a string and the inverse element of a different string. Let's not bother; just drop this axiom and call it a "monoid".
- kstrauser 9y agoThis 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!
- dkarl 9y agoThis 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.
- tw1010 9y agoI 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.
- dkarl 9y agoSetting aside relevance to common problem domains, I'd say monoids (as monads) are the most used mathematical abstraction in programming after sets, functions, induction, total orders, and various forms of graphs. That's pretty outstanding, especially given their B-list status in mathematics. There are dozens of explanations of monads on programming blogs and not nearly as many explanations of, say, rings or models or vector spaces.
- vertex-four 9y agoOK... 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?
- bstamour 9y agoAt 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.
- tw1010 9y agoSometimes 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.
- vertex-four 9y agoOK, so when was the last time knowing something is a monoid helped you solve a problem that you were having difficulty with?
- 9y ago
- dkural 9y agoIt'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.
- tw1010 9y agoYou don't need to give names to things, but often it's useful. It can reduce cognitive load (if you're comfortable with the terminology) and it can be useful when communicating to other engineers. Mathematicians did their thing without symbols (only words) a few hundred years ago, but once everyone agrees to use them you can start worrying about higher-order problems.
- rbehrends 9y agoThe problem with this argument is that a monoid is one of the most basic constructs you can find in abstract algebra. Using monoids as a shorthand for a couple of simple axioms doesn't buy you much; heck, the shape example didn't even have a use case for the neutral element, so all it basically said was: "intersection is associative". Just using a whole lot more words. Had the shapes example be modified to describe (say) a topological space via open sets, you may have a point.
- mbrock 9y agoThe cool thing about algebra is that it lets you reuse concepts and computations between elementary arithmetic and a wide range of abstract or complex structures. It's probably true that most programs use only very simple monoids, but look at e.g. this article to see how composition of monoids can be a very powerful design pattern in functional programming. http://repository.upenn.edu/cgi/viewcontent.cgi?article=1773&context=cis_papers http://repository.upenn.edu/cgi/viewcontent.cgi?article=1773...
- rbehrends 9y agoAnd the article introduces a whole lot more concepts, such as homomorphisms in order to be sufficiently interesting. I don't say that you can't build interesting stuff on top of monoids (I have several colleagues that are doing just that), just that the concept of a monoid by itself isn't very interesting or deep.
- kens 9y agoI'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.)
- rbehrends 9y agoYeah. I mean, I work in computer algebra, and these things strike me as trivialities.
- tome 9y ago"Early on, Peter Freyd wrote > 'Perhaps the purpose of categorical algebra is to show that which is trivial is trivially trivial.' "This can be taken to mean that one thing category theory does is help make the softer bits seem utterly natural and obvious, so as to quickly get to the heart of the matter, isolating the hard nuggets, which one may then attack with abandon. This is an invaluable service category theory performs for mathematics; therefore, category theory is plain good pragmatics." https://ncatlab.org/nlab/show/nPOV https://ncatlab.org/nlab/show/nPOV I would say equally "This is an invaluable service category theory performs for programming; therefore, category theory is plain good pragmatics."
- rbehrends 9y agoSure. Especially in abstract algebra we have a whole, complex edifice that builds upon semigroups and monoids. But computer science doesn't have the same edifice (or anything resembling it), so you're mostly confined to "look, this is a monoid, isn't this neat?" and then things sort of end there. Actual use cases for monoids as building blocks for more complex concepts are pretty rare in computer science. And even in mathematics, the fact that (say) a ring is also a multiplicative monoid becomes mostly irrelevant soon enough.
- wyc 9y agoHere'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.
- ksenzee 9y ago> f is associative: for all a, b and c, we have f(f(a, b), c) == f(a, f(b, c)) > Relative paths in a file system form a Monoid under appending How can appending be associative?
- jpfed 9y agoBecause ABC could be built by appending C to AB, or appending BC to A.
- Koshkin 9y agoWell, I guess, it's useful to remember that String type is a monoid after all! :)
- deleted 9y ago[deleted]
- jhomedall 9y agoYou might be confusing the associative property with the commutative property (I do this all the time): 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.
- ksenzee 9y agoI was! Thank you.
- deleted 9y ago[deleted]
- graphememes 9y agomonoids taught me that you can use overly complex statements to solve trivial ideas
- Vunovati 9y agoComing 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: http://blog.plasmaconduit.com/the-composite-pattern-and-monoids/ http://blog.plasmaconduit.com/the-composite-pattern-and-mono...
- imtringued 9y agoWhen I tried haskell I wanted to use wreq library to do some simple post and get requests. 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/Network-Wreq.html#v:post https://hackage.haskell.org/package/wreq-0.5.1.0/docs/Networ... post :: Postable a => String -> a -> IO (Response ByteString) 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 >>> r <- post "http://httpbin.org/post" (toJSON [1,2,3]) By looking at the definition of toJSON definition we know that toJSON returns a value https://hackage.haskell.org/package/aeson-1.2.1.0/docs/Data-Aeson-Types.html#v:toJSON https://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/Network-Wreq-Types.html#t:Postable 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 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/Network-Wreq-Types.html https://hackage.haskell.org/package/wreq-0.5.1.0/docs/src/Ne... 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.
- goostavos 9y agoCould 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.
- r41nbowdash 9y agofun 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 http://www.morganclaypool.com/doi/abs/10.2200/S00245ED1V01Y201001CNT003 http://www.morganclaypool.com/doi/abs/10.2200/S00245ED1V01Y2...