Composite as a monoid by Mark Seemann
When can you use the Composite design pattern? When the return types of your methods form monoids.
This article is part of a series of articles about design patterns and their universal abstraction counterparts.
The Composite design pattern is a powerful way to structure code, but not all objects are composable. When is an object composable? This article explores that question.
In short, Composites are monoids.
Not all monoids are Composites, but as far as I can tell, all Composites are monoids.
Composite #
First, I'll use various software design isomorphisms to put Composite in a canonical form. From unit isomorphisms, function isomorphisms, and argument list isomorphisms, we know that we can represent any method as a method or function that takes a single argument, and returns a single output value. From abstract class isomorphism we know that we can represent an abstract class with interfaces. Thus, you can represent the interface for a Composite like this:
public interface IInterface1 { Out1 Op1(In1 arg); Out2 Op2(In2 arg); Out3 Op3(In3 arg); // More operations... }
In order to create a Composite, we must be able to take an arbitrary number of implementations and make them look like a single object.
Composite as monoid #
You have a set of implementations of IInterface1. In order to create a Composite, you loop over all of those implementations in order to produce an aggregated result. Imagine that you have to implement a CompositeInterface1 class that composes imps, an IReadOnlyCollection<IInterface1>. In order to implement Op1, you'd have to write code like this:
public Out1 Op1(In1 arg) { foreach (var imp in this.imps) { var out1 = imp.Op1(arg); // Somehow combine this out1 value with previous values } // Return combined Out1 value }
This implies that we have an ordered, finite sequence of implementations: imp1, imp2, imp3, .... In C#, we could represent such a sequence with the type IReadOnlyCollection<IInterface1>. Somehow, we need to turn that collection into a single IInterface1 value. In other words, we need a translation of the type IReadOnlyCollection<IInterface1> -> IInterface1.
If we look to Haskell for inspiration for a moment, let's replace IReadOnlyCollection<T> with Haskell's built-in linked list. This means that we need a function of the type [IInterface1] -> IInterface1, or, more generally, [a] -> a. This function exists for all a as long as a forms a monoid; it's called mconcat:
mconcat :: Monoid a => [a] -> a
We also know from a previous article that a collection of monoids can be reduced to a single monoid. Notice how the above outline of a composite implementation of Op1 looks similar to the Accumulate method shown in the linked article. If IInterface1 can form a monoid, then you can make a Composite.
Objects as monoids #
When can an object (like IInterface1) form a monoid?
From object isomorphisms we know that we can decompose an object with n members to n static methods. This means that instead of analysing all of IInterface1, we can consider the properties of each method in isolation. The properties of an object is the consolidation of the properties of all the methods.
Recall, still from object isomorphisms, that we can represent an object as a tuple of functions. Moreover, if you have a tuple of monoids, then the tuple also forms monoid!
In order to make an object a monoid, then, you have to make each method a monoid. When is a method a monoid? A method is a monoid when its return type forms a monoid.
That's it. An interface like IInterface1 is a monoid when Out1, Out2, Out3, and so on, form monoids. If that's the case, you can make a Composite.
Examples #
From unit isomorphism, we know that we can represent C#'s and Java's void keywords with methods returning unit, and unit is a monoid. All methods that return void can be part of a Composite, but we already knew that Commands are composable. If you search for examples of the Composite design pattern, you'll find more than one variation involving drawing shapes on a digital canvas, with the central operation being a Draw method with a void return type.
Another example could be calculation of the price of a shopping basket. If you have an interface method of the type decimal Calculate(Basket basket), you could have several implementations:
- Add all the item prices together
- Apply a discount (a negative number)
- Calculate sales tax
Boolean values also form at least two monoids (any and all), so any method you have that returns a Boolean value can be used in a Composite. You could, for example, have a list of criteria for granting a loan. Each such business rule returns true if it evaluates that the loan should be granted, and false otherwise. If you have more than one business rule, you can create a Composite that returns true only if all the individual rules return true.
If you have a method that returns a string, then that is also a candidate for inclusion in a Composite, if string concatenation makes sense in the domain in question.
You probably find it fairly mundane that you can create a Composite if all the methods involved return numbers, strings, Booleans, or nothing. The result generalises, however, to all monoids, including more complex types, including methods that return other interfaces that themselves form monoids, and so on recursively.
Granularity #
The result, then, is that you can make a Composite when all methods in your interface have monoidal return types. If only a single method has a return type that isn't a monoid, you can't aggregate that value, and you can't make a Composite.
Your interface can have as many methods you like, but they must all be monoids. Even one rogue method will prevent you from being able to create a Composite. This is another argument for Role Interfaces. The smaller an interface is, the more likely it is that you can make a Composite out of it. If you follow that line of reasoning to its ultimate conclusion, you'll design your interfaces with a single member each.
Relaxation #
There can be some exceptions to the rule that all return values must be monoids. If you have at least one implementation of your interface, then a semigroup may be enough. Recall that monoids accumulate like this:
public static Foo Accumulate(IReadOnlyCollection<Foo> foos) { var acc = Identity; foreach (var f in foos) acc = acc.Op(f); return acc; }
You only need Identity in order to start the accumulation, and to have something to return in case you have no implementations. If you have at least one implementation, you don't need the identity, and then a semigroup is enough to accumulate. Consider the bounding box example. If you have a method that returns BoundingBox values, you can still make a Composite out of such an interface, as long as you have at least one implementation. There's no 'identity' bounding box, but it makes intuitive sense that you can still compose bounding boxes into bigger bounding boxes.
Haskell formalises the rule for semigroups:
sconcat :: Semigroup a => Data.List.NonEmpty.NonEmpty a -> a
The sconcat function reduces any non-empty list of any semigroup a to a single a value.
If you have a non-empty list of implementations, then perhaps you don't even need a semigroup. Perhaps any magma will work. Be aware, however, that the lack of associativity will cause the order of implementations to matter.
Technically, you may be able to program a Composite from a magma, but I'd suggest caution. The monoid and semigroup laws are intuitive. A magma without those properties may not form an intuitive Composite. While it may compile, it may have surprising, or counter-intuitive, behaviour. I'd favour sticking to monoids or semigroups.
Summary #
When is an object-oriented design composable? Composition could mean more than one thing, but this article has focused exclusively on the Composite design pattern. When can you use the Composite pattern? When all method return types are monoids.
