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?
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.
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.
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.
- Bounding box semigroup
- Rock Paper Scissors magma
- Colour-mixing magma
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.