Composites are monoids. An example in C#, F#, and Haskell.

Towards the end of the first decade of the third millennium, I'd been writing object-oriented code for about ten years, and I'd started to notice some patterns in my code. I'd read Design Patterns 6-7 years earlier, but I noticed that I tended to use only a small subset of the patterns from the book - particularly Composite, Decorator, Chain of Responsibility, and a few others.

In particular, I noticed that modelling seemed to be easier, and the code better structured, when I could apply the Composite design pattern. It was also clear, however, that I couldn't always use the Composite pattern, so I started to speculate on what could be the distinguishing factors. In 2010, I made a first attempt at identifying when a Composite is possible, and when it isn't. Unfortunately, while it was a fine attempt (which I'll return to later), it didn't lead anywhere. Ultimately, I gave up on the subject and moved on to other things.

A revelation #

One of my interests in the next decade became functional programming. One day in late 2016 I came across this Code Review question by Scott Nimrod. It was an solution to the Business Rules kata, which, briefly told, is about implementing changing business rules in a sustainable manner.

In my answer to the question, I gave an outline (repeated below) of how I would address the problem in F#. As a comment to my answer, Scott wrote:

"Feels like the Decorator Pattern..."

I responded,

"Not really; it's the Composite pattern..."

A few days later, as I was doing something else, it suddenly dawned on me that not only was a few lines of F# code equivalent to the Composite design pattern, but those lines of code were also manifestations of fundamental abstractions from category theory. Originally, I thought Composite was a combination of applicative functors and monoids, but as I investigated, I discovered that Composites are simply monoids.

This article shows a concrete example of that discovery, starting with my original F# code, subsequently translating it to C# to demonstrate that it's a Composite, and concluding with a translation to Haskell in order to demonstrate that it all fits with the formalisation of Monoid there.

Original F# solution outline #

The kata is about modelling volatile business rules in a sustainable manner. Particularly, you must implement various business rules associated with payments for products and services. Making a rough outline of a model, I started by introducing some types in F#:

type Membership = Basic | Gold
 
type Good =
| PhysicalProduct of string
| Book of string
| Video of string
| Membership of Membership
| Upgrade
 
type Command =
| Slip of string * (Good list)
| Activate of Membership
| Upgrade
| PayAgent

This basically states that there's a closed hierarchy of goods, and a closed hierarchy of business commands, as well as a Membership enumeration. A good can be a physical product with a name, a book with a name, a membership or upgrade, and so on. A command can be a packing slip, a membership activation, and so on.

Since I was only interested in a rough outline of a solution, I only sketched four business rules, all implemented as functions. The first creates a packing slip for certain goods:

// Good -> Command list
let slipForShipping = function
| PhysicalProduct name -> [Slip ("Shipping", [PhysicalProduct name])]
| Book name            -> [Slip ("Shipping", [Book name])]
| Video name           -> [Slip ("Shipping", [Video name])]
| _                    -> []

This function takes a Good value as input and returns a list of Command values as output. If the Good is a PhysicalProduct, Book, or Video, it returns a packing slip command; otherwise, it returns an empty list of commands.

The next business rule is a similar function:

// Good -> Command list
let slipForRoyalty = function
| Book name -> [Slip ("Royalty", [Book name])]
| _         -> []

This business rule generates a royalty slip for any Book, but does nothing for any other Good.

The third business rule activates a membership:

// Good -> Command list
let activate = function | Membership x -> [Activate x] | _ -> []

If the Good is a Membership, the activate function returns a list containing a single Activate command; otherwise, it returns an empty list.

Finally, the last rule upgrades a membership:

// Good -> Command list
let upgrade = function | Good.Upgrade -> [Upgrade] | _ -> []

Similar to the previous functions, this one looks at the type of Good, and returns an Upgrade command when the input is an Upgrade good, and an empty list otherwise.

Notice that all four functions share the same type: Good -> Command list. I designed them like that on purpose, because this enables you to compose a list of business rules to a function that looks like a single rule:

// ('a -> 'b list) list -> 'a -> 'b list
let handle rules good = List.collect (fun r -> r good) rules

This handle function takes a list of business rules (rules) and returns a new function with the type Good -> Command list (or, actually, a function with the type 'a -> 'b list - once again I've fallen into the trap of using too descriptive names). Notice that this is the same type as the individual rules.

You can now compose the four specific business rules:

// Good -> Command list
let handleAll = handle [slipForShipping; slipForRoyalty; activate; upgrade]

This function also has the type Good -> Command list although it's a composition of four rules.

You can use it like this F# Interactive example:

> handleAll (Book "The Annotated Turing");;
val it : Command list =
  [Slip ("Shipping",[Book "The Annotated Turing"]);
   Slip ("Royalty",[Book "The Annotated Turing"])]

(Yes, I like The Annotated Turing - read my review on Goodreads.)

Notice that while each of the business rules produces only zero or one Command values, in this example handleAll returns two Command values.

This design, where a composition looks like the things it composes, sounds familiar.

Business rules in C# #

You can translate the above F# model to an object-oriented model in C#. Translating discriminated unions like Good and Command to C# always involves compromises. In order to keep the example as simple as possible, I decided to translate each of those to a marker interface, although I loathe that 'pattern':

public interface IGood { }

While the interface doesn't afford any behaviour, various classes can still implement it, like, for example, Book:

public class Book : IGood
{
    public Book(string name)
    {
        Name = name;
    }
 
    public string Name { get; }
}

Other IGood 'implementations' looks similar, and there's a comparable class hierarchy for ICommand, which is another marker interface.

The above F# code used a shared function type of Good -> Command list as a polymorphic type for a business rule. You can translate that to a C# interface:

public interface IRule
{
    IReadOnlyCollection<ICommand> Handle(IGood good);
}

The above slipForShipping function becomes a class that implements the IRule interface:

public class SlipForShippingRule : IRule
{
    public IReadOnlyCollection<ICommand> Handle(IGood good)
    {
        if (good is PhysicalProduct ||
            good is Book ||
            good is Video)
            return new[] { new SlipCommand("Shipping", good) };
 
        return new ICommand[0];
    }
}

Instead of pattern matching on a discriminated union, the Handle method examines the subtype of good and only returns a SlipCommand if the good is either a PhysicalProduct, a Book, or a Video.

The other implementations are similar, so I'm not going to show all of them, but here's one more:

public class ActivateRule : IRule
{
    public IReadOnlyCollection<ICommand> Handle(IGood good)
    {
        var m = good as MembershipGood;
        if (m != null)
            return new[] { new ActivateCommand(m.Membership) };
 
        return new ICommand[0];
    }
}

Since 'all' members of IRule return collections, which form monoids over concatenation, the interface itself gives rise to a monoid. This means that you can create a Composite:

public class CompositeRule : IRule
{
    private readonly IRule[] rules;
 
    public CompositeRule(params IRule[] rules)
    {
        this.rules = rules;
    }
 
    public IReadOnlyCollection<ICommand> Handle(IGood good)
    {
        var commands = new List<ICommand>();
        foreach (var rule in rules)
            commands.AddRange(rule.Handle(good));
        return commands;
    }
}

Notice how the implementation of Handle follows the template for monoid accumulation. It starts with the identity, which, for the collection concatenation monoid is the empty collection. It then loops through all the composed rules and updates the accumulator commands in each iteration. Here, I used AddRange, which mutates commands instead of returning a new value, but the result is the same. Finally, the method returns the accumulator.

You can now compose all the business rules and use the composition as though it was a single object:

var rule =
    new CompositeRule(
        new SlipForShippingRule(),
        new SlipForRoyaltyRule(),
        new ActivateRule(),
        new UpgradeRule());
 
var book = new Book("The Annotated Turing");
var commands = rule.Handle(book);

When the method returns, commands contains two SlipCommand objects - a packing slip, and a royalty slip.

Business rules in Haskell #

You can also port the F# code to Haskell, which is usually easy as long as the F# is written in a 'functional style'. Since Haskell has an explicit notion of monoids, you'll be able to see how the two above solutions are monoidal.

The data types are easy to translate to Haskell - you only have to adjust the syntax a bit:

data Membership = Basic | Gold deriving (ShowEqEnumBounded)
 
data Good =
    PhysicalProduct String
  | Book String
  | Video String
  | Membership Membership
  | UpgradeGood
  deriving (ShowEq)
 
data Command =
    Slip String [Good]
  | Activate Membership
  | Upgrade
  | PayAgent
  deriving (ShowEq)

The business rule functions are also easy to translate:

slipForShipping :: Good -> [Command]
slipForShipping pp@(PhysicalProduct _) = [Slip "Shipping" [pp]]
slipForShipping             b@(Book _) = [Slip "Shipping"  [b]]
slipForShipping            v@(Video _) = [Slip "Shipping"  [v]]
slipForShipping                     _  = []
 
slipForRoyalty :: Good -> [Command]
slipForRoyalty b@(Book _) = [Slip "Royalty" [b]]
slipForRoyalty         _  = []
 
activate :: Good -> [Command]
activate (Membership m) = [Activate m]
activate             _  = []
 
upgrade :: Good -> [Command]
upgrade (UpgradeGood) = [Upgrade]
upgrade            _  = []

Notice that all four business rules share the same type: Good -> [Command]. This is conceptually the same type as in the F# code; instead of writing Command list, which is the F# syntax, the Haskell syntax for a list of Command values is [Command].

All those functions are monoids because their return types form a monoid, so in Haskell, you can compose them without further ado:

handleAll :: Good -> [Command]
handleAll = mconcat [slipForShipping, slipForRoyalty, activate, upgrade]

mconcat is a built-in function that aggregates any list of monoidal values to a single value:

mconcat :: Monoid a => [a] -> a

Since all four functions are monoids, this just works out of the box. A Composite is just a monoid. Here's an example of using handleAll from GHCi:

*BusinessRules> handleAll $ Book "The Annotated Turing"
[Slip "Shipping" [Book "The Annotated Turing"],Slip "Royalty" [Book "The Annotated Turing"]]

The result is as you'd come to expect.

Notice that not only don't you have to write a CompositeRule class, you don't even have to write a handle helper function. Haskell already understands monoids, so composition happens automatically.

If you prefer, you could even skip the handle function too:

*BusinessRules> mconcat [slipForShipping, slipForRoyalty, activate, upgrade] $ Book "Blindsight"
[Slip "Shipping" [Book "Blindsight"],Slip "Royalty" [Book "Blindsight"]]

(Yes, you should also read Blindsight.)

It's not that composition as such is built into Haskell, but rather that the language is designed around a powerful ability to model abstractions, and one of the built-in abstractions just happens to be monoids. You could argue, however, that many of Haskell's fundamental abstractions are built from category theory, and one of the fundamental characteristics of a category is how morphisms compose.

Summary #

Composite are monoids. This article shows an example, starting with a solution in F#. You can translate the F# code to object-oriented C# and model the composition of business rules as a Composite. You can also translate the F# code 'the other way', to the strictly functional language Haskell, and thereby demonstrate that the solution is based on a monoid.

This article is a repost of a guest post on the NDC blog, reproduced here with kind permission.



Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.

Published

Thursday, 17 May 2018 06:45:00 UTC

Tags



"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!