Monoids, semigroups, and friends by Mark Seemann
Introduction to monoids, semigroups, and similar concepts, for object-oriented programmers.
This article series is part of an even larger series of articles about the relationship between design patterns and category theory.
Functional programming has often been criticised for its abstruse jargon. Terminology like zygohistomorphic prepromorphism doesn't help sell the message, but before we start throwing stones, we should first exit our own glass house. In object-oriented design, we have names like Bridge, Visitor, SOLID, cohesion, and so on. The words sound familiar, but can you actually explain or implement the Visitor design pattern, or characterise cohesion?
That Bridge is a word you know doesn't make object-oriented terminology better. Perhaps it even makes it worse. After all, now the word has become ambiguous: did you mean a physical structure connecting two places, or are you talking about the design pattern? Granted, in practical use, it will often be clear from the context, but it doesn't change that if someone talks about the Bridge pattern, you'll have no idea what it is, unless you've actually learned it. Thus, that the word is familiar doesn't make it better.
More than one object-oriented programmer have extolled the virtues of 'operations whose return type is the same as the type of its argument(s)'. Such vocabulary, however, is inconvenient. Wouldn't it be nice to have a single, well-defined word for this? Perhaps monoid, or semigroup?
Object-oriented hunches #
In Domain-Driven Design, Eric Evans discusses the notion of Closure of Operations, that is, operations "whose return type is the same as the type of its argument(s)." In C#, it could be a method with the signature public Foo Bar(Foo f1, Foo f2). This method takes two Foo objects as input, and returns a new Foo object as output.
As Evans points out, object designs with that quality begins to look like arithmetic. If you have an operation that takes two Foo and returns a Foo, what could it be? Could it be like addition? Multiplication? Another mathematical operation?
Some enterprise developers just 'want to get stuff done', and don't care about mathematics. To them, the value of making code more mathematical is disputable. Still, even if you 'don't like maths', you understand addition, multiplication, and so on. Arithmetic is a powerful metaphor, because all programmers understand it.
In his book Test-Driven Development: By Example, Kent Beck seems to have the same hunch, although I don't think he ever explicitly calls it out.
What Evans describes are monoids, semigroups, and similar concepts from abstract algebra. To be fair, I recently had the opportunity to discuss the matter with him, and he's perfectly aware of those concepts today. Whether he was aware of them when he wrote DDD in 2003 I don't know, but I certainly wasn't; my errand isn't to point fingers, but to point out that clever people have found this design principle valuable in object-oriented design long before they gave it a distinct name.
Relationships #
Monoids and semigroups belong to a larger group of operations called magmas. You'll learn about those later, but we'll start with monoids, move on to semigroups, and then explore other magmas. All monoids are semigroups, while the inverse doesn't hold. In other words, monoids form a subset of semigroups.
All magmas describe binary operations of the form: an operation takes two Foo values as input and returns a Foo value as output. Both categories are governed by (intuitive) laws. The difference is that the laws governing monoids are stricter than the laws governing semigroups. Don't be put off by the terminology; 'law' may sound like you have to get involved in complicated maths, but these laws are simple and intuitive. You'll learn them as you read on.
Summary #
To the average object-oriented programmer, terms like monoid and semigroup smell of mathematics, academia, and ivory-tower astronaut architects, but they're plain and simple concepts that anyone can understand, if they wish to invest 15 minutes of their time.
Whether or not an object is a magma tells us whether Evans' Closure of Operations is possible. It might teach us other things about our code, as well.
Next: Monoids.
Comments
Hi Mark,
Thank you for taking the time to write such interesting articles. I'm personally fascinated by the relationship between ancient subjects like algebra and modern ones like programming. I can't wait to read more.
That said, I understand the feeling of being put off by some of the terms used in functional programming (I'm looking at you, "zygohistomorphic"). I think the reason for it is that the vast majority of those words come from Greek or Latin, and to many people (me included) Greek is exactly what it sounds like — Greek.
Granted, things aren't much better in the object-oriented programming world, where a Visitor isn't necessarily what you think it is, even if you recognize the word.
However, in my experience, knowing the etymology of a word is the first step in understanding it. I think that including a translation for every new term would make the subjects of these articles feel less alien. It would be a way to "break the ice", so to speak.
One example I came to think of is the word polymorphism — perhaps one of the most "academic-sounding" words thrown around in object-oriented programming conversations. It may feel intimidating at first, but it quickly falls off the ivory tower once you know that it literally means "when things can take many shapes" (from the Greek polys, "many", morphē, "shape" and "ismós", the general concept).
/Enrico
Enrico, thank you for writing. Funny you should write that, because leading with an explanation of monoid is exactly what I do in my new Clean Coders episode Composite as Universal Abstraction. In short, monoid means 'one-like'. In the video, I go into more details on why that's a useful name.
Hey, Mark, what a great start on a very promising series! One more accessibility suggestion along the same lines as Enrico's: You might consider including pronunciation for new terms that aren't obvious.
Eagerly anticipating future installments!