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.
It's always baffling to watch programmers learn something new and immediately reject it as useless. When did the search for knowledge and better ways to think about code become a reason to mock someone?
Any decent programming language will let you write code that uses an abstraction, limiting your interaction with some of its input values to only operations defined in the abstraction.
Then the question becomes "how interesting is this abstraction free of concrete details?" It turns out monoids allow you to write general code that gives you incredible flexibility when you later choose a concrete instance of the abstraction to work in. See http://www.soi.city.ac.uk/~ross/papers/FingerTree.html for an example of how you can specialize a general data structure to do a number of specific functions based on a choice of monoid.
The best abstractions are the ones that introduce a lot of flexibility based on choices that code doesn't depend on. A lot of the deepest abstractions in that sense come from math. This isn't an accident. Math is about searching for good abstractions. When one of them is found to be applicable to programming, that should be celebrated.
This is a much deeper debate, but through my subjective experience programming for two decades, stand-alone as PhD, and also leading a 200-person engineering team, I thing flexibility is by and large the last thing to optimize for, and almost always a sign of a novice engineer.
You don't know the future. You don't know what will work with the end users of your software, or where your research will take you. The best thing you can do is to accomplish the task in front of you in the simplest, most directly performant way possible, and put it to use - in front of customers, or in doing your research.
True flexibility is not having to wait for every iteration so engineers can program in every iteration of the future.
There is a huge cost you pay today for 'flexibility', most things advertised as such are not in fact flexible, and the trend in designing complex real world systems is in fact for each project to do exactly ONE thing and do it very well.
Btw you're assuming I've rejected algebra, and I've done so immediately. I have no objections to using abstract algebra or category theory in designing and thinking about programming languages, and none of my opinions are a jerk-reaction to anything.
i would consider self driving cars complex real world systems, and they are designed to be 'flexible'...i would hope at least associative (pedestrian + car == car + pedestrian == bad)
Well, the article certainly doesn't give one enough to chew on to celebrate.
I don't at all get what the hype is about from this article, the concept of "you can combine two things and get a thing" isn't novel or radical.
I get a feeling that the kicker is about associativity, which is to say "when combining a bunch of things in a row, you can combine them any way as long as you only combine the adjacent ones". The kicker being that if you have that, you can parallelize.
So, seeing associativity allows one to identify parallelizable problems.
it's weird how the article neglected that at all. maybe it was assumed to be obvious? I've given brownbags about monoids and they were all focused on parallelization. things like summingbird were good examples i've used.
>All those data structures would work just as fine without a monoid formalization
That was has happening in the last 50+ years.
>and one can use all their power with no attention given to algebraic axioms that define a monoid.
Not really. When you can actually identify a pattern, and treat different instances of the same phenomenon as a single concept, you get much more power over simple using those individual instances as different cases.
It's the very reason why we create and use abstractions.
Yes, I know that as a mathematician. Imagine you are a military strategist. And some engineer says, you know what all our tanks, rifles, and missiles have in common? They are all WEAPONS satisfying a few simple formal properties!
Your sarcasm is noted (and pretty funny), but you should know that there are military theorists who are taken seriously despite being superficially silly.
For example, an Army field manual [1]: "Any use of force generates a series of reactions."
Like, duh, right? But if you read on, the manual makes a highly cogent, precise point (one that's especially relevant to a military that all-too-recently used "body count" as a success metric).
"There will be times when an overwhelming effort is necessary to destroy or intimidate an opponent and reassure the populace. However, counterinsurgency forces should calculate carefully the type and amount of force to be applied and who wields it for any operation."
If you fail to generalize from tanks, rifles, missiles, etc. to "force", it's a lot harder to think about how to apply force to get the outcome that you want.
The same is true of programming. For small programs, you don't need abstractions or patterns. But if you want to build large, resilient, performant systems, you'll need formal definitions for those terms, and formal definitions of components you can use to build them, and so on.
Re-reading, it sounds like you're saying that the concept of a monoid isn't useful by itself, and I guess that's fair. But I didn't know anything about them before, and now that I read this article I do. I've got a long way to go!
what a refreshing reply - good point & I agree with you. For certain questions, it helps to think in this fashion, and to make non-obvious points that might be lost in details otherwise. I have nothing against formal systems in computing, programming language research, or other forms theoretical CS. In support of this, in mathematics, Grothendieck took an exceedingly abstract perspective, eventually leading to the solution of some outstanding conjectures of the time.
While I haven't articulated this particularly well in my original comment, what I despair is the singular obsession with Monoids. It is popular because it is easy for people to wrap their minds around, they convince themselves that they've learned deep math and Something Very Important(tm), and it has a cool sounding name.
It's like you've given someone a book about the origins of the French Revolution and because they've heard the word "french", keep repeating "but the Eiffel Tower though amirite?" and keep writing blog posts and articles about the Eiffel Tower and nothing else.
In some ways I suppose my criticism is unfair and has an elitist / snobby vibe to it. It is common for people to find some 'sexy' hooks to initially get attracted to an area, and one shouldn't judge too much newbies. After all no one is forcing me to hang out at forums :)
>While I haven't articulated this particularly well in my original comment, what I despair is the singular obsession with Monoids. It is popular because it is easy for people to wrap their minds around, they convince themselves that they've learned deep math and Something Very Important(tm), and it has a cool sounding name. It's like you've given someone a book about the origins of the French Revolution and because they've heard the word "french", keep repeating "but the Eiffel Tower though amirite?" and keep writing blog posts and articles about the Eiffel Tower and nothing else.
That's not the case (though it might be for some).
The "singular obsession with Monoids"/monads is because we have a popular-ish language that has them as an abstraction. For many people that's a new abstraction they weren't aware of -- in the same way that in 2000 or so everybody talked about GoF Design Patterns.
If linear types where used in some other popular(ish) language and enabled new things and abstractions people would talk about that concept all the time (which is even simpler as a notion than monoids).
If there was a natural isomorphism between rifles and panzer tanks you can imagine it'd have pretty big implications for both manufacturing and the common foot solder's field tactics.
You 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.
The 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.
The real advantage is that we can express the abstraction in the language, which lets us write libraries around it. A single function like fold is much nicer than either having one per type or having to pass in the operation and identity manually:
fold :: (Monoid m, Foldable t) => t m -> m
The fact that monoids are so simple is actually what makes this powerful: fold works for a large set of the types I use day-to-day, whether they're from the base library or specific to my own codebase. There is only a handful of other generic operations that rely on the Monoid class, but that's enough to make the class quite useful. It's a simple abstraction that applies to a lot of different types.
I actually did a count recently; something like 30% of our modules import Data.Monoid. Many of them were just using the (<>) operator, but that's useful in and of itself: no need to define a distinct operator for each of our types that wants one.
It's a simple, incredibly general abstraction that pulls its weight—partly because it doesn't have much to pull.
The 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.
And 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.
The goal of programming is to reduce all parts to such simplicity that they become boringly simple, and thus impossible to get wrong. Concepts are only interesting while we don’t fully understand them yet; when we’re done fully understanding them, they become boring and we move on to the next thing. Thus, the solution to programming is to compose programs out of boringly simple parts, using a boringly simple method of composition.
> The goal of programming is to reduce all parts to such simplicity that they become boringly simple, and thus impossible to get wrong.
No, that's a strategy to achieve a goal of programming. Programming is about using machines that accept well defined instructions to automate processes for people. A complex and poorly understood program that still ends up reducing the overall amount of work required for individuals is still worthwhile, even if not reduced to being boringly simple.
The main selling point is that reduction and "boring simplicity" can lead to a formally correct program, or at least one where most errors are caught by static analysis/type checking/etc.
I'm not saying it's not worth while, I'm just saying that it's not the goal (in general. Some academic exercises might have goals such as that because the point is to learn).
It's sort of like saying the goal of owning a store is to match inventory to sales as closely as possible. That's a strategy or sub-goal towards reaching the real goal at best, which is to make enough money that the store pays for itself and hopefully supports the owner. Some stores don't even have inventory, so that strategy doesn't even apply to them. Similarly, that programming strategy may not apply well to some problems (and some problems cannot be proven formally correct, at least in whole).
My original reply was really just meant to point out that what they viewed as the goal of programming, is really just one of many competing strategies for producing software, and many others don't care about that at all.
And how do monoids play into this? This is just a vague generality; unless you can show exactly what more complex programming concepts you can reduce to monoids and how that helps with understanding programming, that doesn't mean much.
Sure. It's funny with these algebraic things. If they're simple, people complain that they're not interesting... but when you add some depth, people complain that it's too difficult!
I'm sure it's not! But even so it's interesting to be caught between these two antipodes. As your probably know there's another group of people, Andrej Bauer among them, who provide a different antithesis to "I don't want to have to understand category theory to use Haskell!" by exclaiming "Haskell doesn't use real category theory!".
It's just generally quite amusing to be caught in the middle of all this.
>The problem with this argument is that a monoid is one of the most basic constructs you can find in abstract algebra.
That's irrelevant, because we are not naming them to use them in abstract algebra, but as abstract constructs in a different domain with its own complexity (programming).
The lack of complexity comes from the fact that monoids are just defined by two simple axioms. Using them in a different domain does not change that. Associativity or having a neutral element do not become more complicated concepts in computer science.
The original argument was that naming them "monoids" reduces cognitive load. Can you explain how exactly you see this reduction in cognitive load coming to pass in programming? Because from your previous two responses, I don't see it. What aspects of associative operations with a neutral element are so central to teaching programming that naming such a construct "monoid" gives us a stepping stone towards better understanding programming?
>The original argument was that naming them "monoids" reduces cognitive load. Can you explain how exactly you see this reduction in cognitive load coming to pass in programming?
My original argument (in this thread above) is that identifying patterns like monoids (and monads) gives more power through better abstractions.
Not that it's simpler than not knowing those abstractions (obviously assembler which ditches all abstractions is as simple as it gets conceptually).
>What aspects of associative operations with a neutral element are so central to teaching programming that naming such a construct "monoid" gives us a stepping stone towards better understanding programming?
It's about unifying similar usage patterns and having a mechanism to treat things like optionals (Maybe), errors, IO etc in a uniform way.
As a simplified no-monady example, consider languages with a string distinction between primitives (ints, etc) and objects (like Java, at least before generics/auto-boxing). A language that comes and treats both of these things (primitives and objects) as the same -- all objects, is an eye opener, and allows for more kinds of expressions than a language that treats them as distinct kinds of variables does.
The original argument was that naming them "monoids" reduces cognitive load.
The argument as I see it written is only that naming them reduces cognitive load. I don't see anyone suggesting that the specific name they happen to have carries any special power.
* Under my Foo API you are able to combine Bars monoidally
* Under my Foo API you are able to combine Bars using baz such that `baz (baz bar1 bar2) bar3 == baz bar1 (baz bar2 bar3)` for all `bar1, bar2, bar3 :: Bar`, and also `baz == Bar quux baz == Bar baz quux` for all `baz :: Bar`.
How often do you document an API in such a way? Does the frequency with which this occurs justify introducing new terminology? Plus, you artificially inflated the wording to make "x is associative and has a neutral element y" look more complicated than it actually is, while not even naming in your "short" case what the operation and neutral element are.
"`baz` is associative and `quux` is an identity element."
(Though normally the latter would be more like "`quux` is a noop", "`quux` is an empty set", or whatever domain-specific term you need, and the associativity claim would be a brief parenthetical inside meaningful documentation.)
That's absolutely fine. Then you also have to mention that there's an identity element. Once you've used the words "associatively" and "identity" it's no longer scary to use the word "monoid" so you may as well use it.
Well, you still have to use the words "associativity" and "identity" when you describe the operation and say what the identity element is. You can't just say that you can "combine" elements "monoidally" for it to mean anything.
Also, the elements are still combined associatively. With closure and and identity properties, the set forms a monoid under this operation. "Monoidness" is not a property of operation (in a way that the language is usually used, at least in math).
For that matter, "combine monoidally" is a phrase that has 2 Google hits at the moment, which indicates to me that in real life, you still have to resort to less-shiny words to describe things.
> You can't just say that you can "combine" elements "monoidally" for it to mean anything. ... For that matter, "combine monoidally" is a phrase that has 2 Google hits at the moment, which indicates to me that in real life, you still have to resort to less-shiny words to describe things.
There doesn't seems anything hugely objectionable to me in saying "Bars combine monoidally". But if you prefer, one can say "Bar forms a monoid under baz and quux".
It may not be obvious to you that it increases simplicity merely to combine two words into one but across an ecosystem of perhaps a thousand Monoid instances it indeed is.
* Under my Foo API you are able to combine Bars just like adding numbers.
But seriously, the use of Bar/Baz etc. in this example makes it more convoluted, rather than less, precisely because the names offer no hint for how to understand the nature of each thingy.
I think it increases the cognitive load. These things already have names. A Monoid is an abstract category that doesn't 1-1 correspond to the particulars of each data structure, increasing overall cognitive load. It's not like I'm going to forget how sets work otherwise. I'm a mathematician. I like category theory. Mathematicians in fact strive for the right level of generality. I've never seen an algorithmic or programming challenge where thinking of something as a monoid helped me solve it better.
I only think it is useful once you're comfortable with it. Before you are you are probably better off using whatever mental intuition you already have about the idea. Personally I consider it useful to associate the concept to the idea of distributed systems (together with other concepts like commutativity). Having this association can help guide me towards either common appropriate ways of solving problems in that space, or as a good search-phrase to include when I google for algorithms.
In contrast, I, personally, have run into programming/design problems where monoids or semigroups seemed to be the correct level of abstraction to work at. People aren't appropriating language and concepts from algebra/category theory for no reason (well, perhaps some are), they're doing so because they find them to be useful tools when building and thinking about systems.
Of course we invent new words all the time, but the downside to using specialized jargon is that many people won't understand you. Many good writers will intentionally avoid obscure vocabulary to reach a larger audience.
This is a judgment to be made on a case-by-case basis. For example, when writing programs, I don't think the word "monoid" is useful enough to be worth explaining, so I would avoid using it in API's or documentation and see if I can get the point across in some clearer way.
You’re right that there’s not much to monoids. Though much hay has been made about monads, they barely rate having a name either, and you’d be surprised if they didn’t work the way they do.
That being said, they are useful abstractions and in Haskell, for example, open up all of Control.Monad[0] and Data.Monoid[1] to your code for free.
Similarly, All those GoF patterns would work just as fine without a pattern formalization, and one can use all their power with no attention given to the common pattern that all instances share.
When recruiters / interviewers ask me whether I know "Design Patterns" I shy away. It's sort of a red flag. I could just say "Singleton" and package them a cat in an object and the interview would go on.
I've recently preferred to be reluctant about this and just tell them I really don't like these words (OOD / Design Patterns)... One interview was over really quick, while at another place, I've actually signed now. Any thoughts?
Hit them back with a question about how they conceive the difference between design patterns as a general concept and methodology stemming from Alexander's work in collaborative architecture, and the one specific GoF pattern language for OO coding that accidentally took over the whole meme.
Sorry, Christopher Alexander, who wrote the book called "A Pattern Language" (and several others) which was the origin of the inspiration for design patterns in coding.
He also later wrote a foreword for a book by Richard P. Gabriel, "Patterns of Software", with this gem of a quote: (the book itself I really recommend for anyone interested in design patterns)
...
In my life as an architect, I find that the single thing which inhibits young professionals, new students most severely, is their acceptance of standards that are too low. If I ask a student whether her design is as good as Chartres, she often smiles tolerantly at me as if to say, “Of course not, that isn’t what I am trying to do. . . . I could never do that.”
Then, I express my disagreement, and tell her: “That standard must be our standard. If you are going to be a builder, no other standard is worthwhile. That is what I expect of myself in my own buildings, and it is what I expect of my students.” Gradually, I show the students that they have a right to ask this of themselves, and must ask this of themselves. Once that level of standard is in their minds, they will be able to figure out, for themselves, how to do better, how to make something that is as profound as that.
Two things emanate from this changed standard. First, the work becomes more fun. It is deeper, it never gets tiresome or boring, because one can never really attain this standard. One’s work becomes a lifelong work, and one keeps trying and trying. So it becomes very fulfilling, to live in the light of a goal like this. But secondly, it does change what people are trying to do. It takes away from them the everyday, lower-level aspiration that is purely technical in nature, (and which we have come to accept) and replaces it with something deep, which will make a real difference to all of us that inhabit the earth.
I would like, in the spirit of Richard Gabriel’s searching questions, to ask the same of the software people who read this book. But at once I run into a problem. For a programmer, what is a comparable goal? What is the Chartres of programming? What task is at a high enough level to inspire people writing programs, to reach for the stars? Can you write a computer program on the same level as Fermat’s last theorem? Can you write a program which has the enabling power of Dr. Johnson’s dictionary? Can you write a program which has the productive power of Watt’s steam engine? Can you write a program which overcomes the gulf between the technical culture of our civilization, and which inserts itself into our human life as deeply as Eliot’s poems of the wasteland or Virginia Woolf’s "The Waves"?
Christopher Alexander, an architect who wrote among others A Pattern Language: Towns, Buildings, Construction. A Pattern Language later inspired Gamma et al to write Design Patterns: Elements of Reusable Object-Oriented Software.
Right, like one of the examples is summing two amounts of money. As far as I know, that's just adding integers if you're doing it right. It's not clear what all the formalisms are bringing to the table there.
It may not be clear because it's very obvious but one of the primary optimizations in haskell that make it fast despite heavily using currying and lamba functions is that haskell doesn't have dynamic dispatch. This is completely unrelated to purity and lazyiness. This means it's possible to inline every lamba and partial function therefore use them at zero cost without the overhead of a JIT compiler or vm at runtime.
The JVM can do similar optimizations because it knows the class hierarchy at runtime and therefore declares every method as final until it finds a class with a method that overrides the previous definition. It's also capable inlining dynamic dispatch by profiling the type of the object it's dispatching on. If 99% of all calls go to class X then it can inline the method of class X and catch the remaining 1% with a fallback clause. Of course this comes at a cost. You need to retain the bytecode, class metadata, profiling information and duplicated code that is generated from inlining in memory.
It's saying that the operation can be made parallel.
Applying an operation to a total workload is identical to:
1) Split the total workload into smaller workloads.
2) Apply the operation to each smaller workload.
3) Apply the operation to the results from step 2.
Each smaller workload in step 2 can be run in parallel.
While that may seem obvious for adding numbers or money it may be less obvious when you have different operations for example a method in an OO class hierarchy.
I agree. But in some cases it might be nice to omit an explicit 0 or use some higher order combinator that is ergonomic just because it expects a monoid instance to be already prepared.
