# ploeh blog danish software design

## Null Object as identity

*When can you implement a Null Object? When the return types of your methods are monoids.*

This article is part of a series of articles about design patterns and their category theory counterparts. In a previous article you learned how there's a strong relationship between the Composite design pattern and monoids. In this article you'll see that the Null Object pattern is essentially a special case of the Composite pattern.

I also think that there's a relationship between monoidal *identity* and the Null Object pattern similar to the relationship between Composite and monoids in general:

Once more, I don't claim that an isomorphism exists. You may be able to produce Null Object examples that aren't monoidal, but on the other hand, I believe that all identities are Null Objects.

### Null Object #

While the Null Object design pattern isn't one of the patterns covered in Design Patterns, I consider it a *structural pattern* because Composite is a structural pattern, and Null Object is a special case of Composite.

Bobby Woolf's original text contains an example in Smalltalk, and while I'm no Smalltalk expert, I think a fair translation to C# would be an interface like this:

public interface IController { bool IsControlWanted(); bool IsControlActive(); void Startup(); }

The idea behind the Null Object pattern is to add an implementation that 'does nothing', which in the example would be this:

public class NullController : IController { public bool IsControlActive() { return false; } public bool IsControlWanted() { return false; } public void Startup() { } }

Woolf calls his implementation `NoController`

, but I find it more intent-revealing to call it `NullController`

. Both of the Boolean methods return `false`

, and the `Startup`

method literally does nothing.

### Doing nothing #

What exactly does it mean to 'do nothing'? In the case of the `Startup`

method, it's clear, because it's a bona fide no-op. This is possible for all methods without return values (i.e. methods that return `void`

), but for all other methods, the compiler will insist on a return value.

For `IsControlActive`

and `IsControlWanted`

, Woolf solves this by returning `false`

.

Is `false`

always the correct 'do nothing' value for Booleans? And what should you return if a method returns an integer, a string, or a custom type? The original text is vague on that question:

"Exactly what "do nothing" means is subjective and depends on the sort of behavior the Client is expecting."Sometimes, you can't get any closer than that, but I think that often it's possible to be more specific.

### Doing nothing as identity #

From unit isomorphisms you know that methods without return values are isomorphic to methods that return *unit*. You also know that *unit* is a monoid. What does *unit* and `bool`

have in common? They both form monoids; `bool`

, in fact, forms four different monoids, of which *all* and *any* are the best-known.

In my experience, you can implement the Null Object pattern by returning various 'do nothing' values, depending on their types:

- For
`bool`

, return a constant value. Usually,`false`

is the appropriate 'do nothing' value, but it does depend on the semantics of the operation. - For
`string`

, return`""`

. - For collections, return an empty collection.
- For numbers, return a constant value, such as
`0`

. - For
`void`

, do nothing, which is equivalent to returning*unit*.

*identity*of the monoid in question. Keep in mind that for some types, such as

`bool`

and `int`

, more than one monoid exist, and the identity depends on which one you pick:
- The identity for the
*any*monoid is`false`

. - The identity for
`string`

is`""`

. - The identity for collections is the empty collection.
- The identity for the
*addition*monoid is`0`

. - The identity for
*unit*is*unit*.

*identity*of a monoid is: it's the value that, when applied to another value, doesn't change the other value:

`foo.Op(Foo.Identity) == foo`

In other words: the *identity does nothing!*

As a preliminary result, then, when all return values of your interface form monoids, you can create a Null Object.

### Relationship with Composite #

In the previous article, you saw how the Composite design pattern was equivalent with the Haskell function `mconcat`

:

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

This function, however, seems more limited than it has to be. It says that if you have a linked list of monoidal values, you can reduce them to a single monoidal value. Is this only true for linked lists?

After all, in a language like C#, you'd typically express a Composite as a container of 'some collection' of objects, typically modelled by the `IReadOnlyCollection<T>`

interface. There are several implementations of that interface, including lists, arrays, collections, and so on.

It seems as though we ought to be able to generalise `mconcat`

, and, indeed, we can. The `Data.Foldable`

module defines a function called `fold`

:

fold :: (Monoid m, Foldable t) => t m -> m

Let me decipher that for you. It says that any monoid `m`

contained in a 'foldable' container `t`

can be reduced to a single value (still of the type `m`

). You can read `t m`

as 'a foldable container that contains monoids'. In C#, you could attempt to express it as `IFoldable<TMonoid>`

.

In other words, the Composite design pattern is equivalent to `fold`

. Here's how it relates to the Null Object pattern:

As a first step, consider methods like those defined by the above `IController`

interface. In order to implement `NullController`

, all of those methods ignore their (non-existent) input and return an identity value. In other words, we're looking for a Haskell function of the type `Monoid m => a -> m`

; that is: a function that takes input of the type `a`

and returns a monoidal value `m`

.

You can do that using `fold`

:

nullify :: Monoid m => a -> m nullify = fold (Identity $ const mempty)

Recall that the input to `fold`

must be a `Foldable`

container. The good old `Identity`

type is, among other capabilities, `Foldable`

. That takes care of the container. The value that we put into the container is a single function that ignores its input (`const`

) and always returns the identity value (`mempty`

). The result is a function that always returns the identity value.

This demonstrates that Null Object is a special case of Composite, because `nullify`

is a special application of `fold`

.

There's no reason to write `nullify`

in such a complicated way, though. You can simplify it like this:

nullify :: Monoid m => a -> m nullify = const mempty

Once you recall, however, that functions are monoids if their return values are monoids, you can simplify it even further:

nullify :: Monoid m => a -> m nullify = mempty

The identity element for monoidal functions is exactly a function that ignores its input and returns `mempty`

.

### Controller identity #

Consider the `IController`

interface. According to object isomorphisms, you can represent this interface as a tuple of three functions:

type Controller = (ControllerState -> Any, ControllerState -> Any, ControllerState -> ())

This is cheating a little, because the third tuple element (the one that corresponds to `Startup`

) is pure, although I strongly suspect that the intent is that it should mutate the state of the Controller. Two alternatives are to change the function to either `ControllerState -> ControllerState`

or `ControllerState -> IO ()`

, but I'm going to keep things simple. It doesn't change the conclusion.

Notice that I've used `Any`

as the return type for the two first tuples. As I've previously covered, Booleans form monoids like *any* and *all*. Here, we need to use `Any`

.

This tuple is a monoid because all three functions are monoids, and a tuple of monoids is itself a monoid. This means that you can easily create a Null Object using `mempty`

:

λ> nullController = mempty :: Controller

The `nullController`

is a triad of functions. You can access them by pattern-matching them, like this:

λ> (isControlWanted, isControlActive, startup) = nullController

Now you can try to call e.g. `isControlWanted`

with various values in order to verify that it always returns false. In this example, I cheated and simply made `ControllerState`

an alias for `String`

:

λ> isControlWanted "foo" Any {getAny = False} λ> isControlWanted "bar" Any {getAny = False}

You'll get similar behaviour from `isControlActive`

, and `startup`

always returns `()`

(*unit*).

### Relaxation #

As Woolf wrote in the original text, what 'do nothing' means is subjective. I think it's perfectly reasonable to say that monoidal identity fits the description of doing nothing, but you could probably encounter APIs where 'doing nothing' means something else.

As an example, consider avatars for online forums, such as Twitter. If you don't supply a picture when you create your profile, you get a default picture. One way to implement such a feature could be by having a 'null' avatar, which is used in place of a proper avatar. Such a default avatar object could (perhaps) be considered a Null Object, but wouldn't necessarily be monoidal. There may not even be a binary operation for avatars.

Thus, it's likely that you could encounter or create Null Objects that aren't monoids. That's the reason that I don't claim that a Null Object always is monoidal identity, although I do think that the reverse relationship holds: if it's *identity*, then it's a Null Object.

### Summary #

Monoids are associative binary operations with identity. The identity is the value that 'does nothing' in that binary operation, like, for example, *0* doesn't 'do' anything under addition. Monoids, however, can be more complex than operations on primitive values. Functions, for example, can be monoids as well, as can tuples of functions.

The implication of that is that objects can be monoids as well. When you have a monoidal object, then its *identity* is the 'natural' Null Object.

The question was: *when can you implement the Null Object pattern?* The answer is that you can do that when all involved methods return monoids.

**Next:** Visitor as a sum type.

## Endomorphic Composite as a monoid

*A variation of the Composite design pattern uses endomorphic composition. That's still a monoid.*

This article is part of a series of articles about design patterns and their category theory counterparts. In a previous article, you learned that the Composite design pattern is simply a monoid.

There is, however, a variation of the Composite design pattern where the return value from one step can be used as the input for the next step.

### Endomorphic API #

Imagine that you have to implement some scheduling functionality. For example, you may need to schedule something to happen a month from now, but it should happen on a bank day, during business hours, and you want to know what the resulting date and time will be, expressed in UTC. I've previously covered the various objects for performing such steps. The common behaviour is this interface:

public interface IDateTimeOffsetAdjustment { DateTimeOffset Adjust(DateTimeOffset value); }

The `Adjust`

method is an endomorphism; that is: the input type is the same as the return type, in this case `DateTimeOffset`

. A previous article already established that that's a monoid.

### Composite endomorphism #

If you have various implementations of `IDateTimeOffsetAdjustment`

, you can make a Composite from them, like this:

public class CompositeDateTimeOffsetAdjustment : IDateTimeOffsetAdjustment { private readonly IReadOnlyCollection<IDateTimeOffsetAdjustment> adjustments; public CompositeDateTimeOffsetAdjustment( IReadOnlyCollection<IDateTimeOffsetAdjustment> adjustments) { if (adjustments == null) throw new ArgumentNullException(nameof(adjustments)); this.adjustments = adjustments; } public DateTimeOffset Adjust(DateTimeOffset value) { var acc = value; foreach (var adjustment in this.adjustments) acc = adjustment.Adjust(acc); return acc; } }

The `Adjust`

method simply starts with the input `value`

and loops over all the composed `adjustments`

. For each `adjustment`

it adjusts `acc`

to produce a new `acc`

value. This goes on until all `adjustments`

have had a chance to adjust the value.

Notice that if `adjustments`

is empty, the `Adjust`

method simply returns the input value. In that degenerate case, the behaviour is similar to the identity function, which is the identity for the endomorphism monoid.

You can now compose the desired behaviour, as this parametrised xUnit.net test demonstrates:

[Theory] [InlineData("2017-01-31T07:45:55+2", "2017-02-28T07:00:00Z")] [InlineData("2017-02-06T10:03:02+1", "2017-03-06T09:03:02Z")] [InlineData("2017-02-09T04:20:00Z" , "2017-03-09T09:00:00Z")] [InlineData("2017-02-12T16:02:11Z" , "2017-03-10T16:02:11Z")] [InlineData("2017-03-14T13:48:29-1", "2017-04-13T14:48:29Z")] public void AdjustReturnsCorrectResult( string dtS, string expectedS) { var dt = DateTimeOffset.Parse(dtS); var sut = new CompositeDateTimeOffsetAdjustment( new NextMonthAdjustment(), new BusinessHoursAdjustment(), new DutchBankDayAdjustment(), new UtcAdjustment()); var actual = sut.Adjust(dt); Assert.Equal(DateTimeOffset.Parse(expectedS), actual); }

You can see the implementation for all four composed classes in the previous article. `NextMonthAdjustment`

adjusts a date by a month into its future, `BusinessHoursAdjustment`

adjusts a time to business hours, `DutchBankDayAdjustment`

takes bank holidays and weekends into account in order to return a bank day, and `UtcAdjustment`

convert a date and time to UTC.

### Monoidal accumulation #

As you've learned in that previous article that I've already referred to, an endomorphism is a monoid. In this particular example, the binary operation in question is called `Append`

. From another article, you know that monoids accumulate:

public static IDateTimeOffsetAdjustment Accumulate( IReadOnlyCollection<IDateTimeOffsetAdjustment> adjustments) { IDateTimeOffsetAdjustment acc = new IdentityDateTimeOffsetAdjustment(); foreach (var adjustment in adjustments) acc = Append(acc, adjustment); return acc; }

This implementation follows the template previously described:

- Initialize a variable
`acc`

with the identity element. In this case, the identity is a class called`IdentityDateTimeOffsetAdjustment`

. - For each
`adjustment`

in`adjustments`

,`Append`

the`adjustment`

to`acc`

. - Return
`acc`

.

`mconcat`

. We'll get back to that in a moment, but first, here's another parametrised unit test that exercises the same test cases as the previous test, only against a composition created by `Accumulate`

:

[Theory] [InlineData("2017-01-31T07:45:55+2", "2017-02-28T07:00:00Z")] [InlineData("2017-02-06T10:03:02+1", "2017-03-06T09:03:02Z")] [InlineData("2017-02-09T04:20:00Z" , "2017-03-09T09:00:00Z")] [InlineData("2017-02-12T16:02:11Z" , "2017-03-10T16:02:11Z")] [InlineData("2017-03-14T13:48:29-1", "2017-04-13T14:48:29Z")] public void AccumulatedAdjustReturnsCorrectResult( string dtS, string expectedS) { var dt = DateTimeOffset.Parse(dtS); var sut = DateTimeOffsetAdjustment.Accumulate( new NextMonthAdjustment(), new BusinessHoursAdjustment(), new DutchBankDayAdjustment(), new UtcAdjustment()); var actual = sut.Adjust(dt); Assert.Equal(DateTimeOffset.Parse(expectedS), actual); }

While the implementation is different, this monoidal composition has the same behaviour as the above `CompositeDateTimeOffsetAdjustment`

class. This, again, emphasises that Composites are simply monoids.

### Endo #

For comparison, this section demonstrates how to implement the above behaviour in Haskell. The code here passes the same test cases as those above. You can skip to the next section if you want to get to the conclusion.

Instead of classes that implement interfaces, in Haskell you can define functions with the type `ZonedTime -> ZonedTime`

. You can compose such functions using the `Endo`

`newtype`

'wrapper' that turns endomorphisms into monoids:

λ> adjustments = reverse [adjustToNextMonth, adjustToBusinessHours, adjustToDutchBankDay, adjustToUtc] λ> :type adjustments adjustments :: [ZonedTime -> ZonedTime] λ> adjust = appEndo $ mconcat $ Endo <$> adjustments λ> :type adjust adjust :: ZonedTime -> ZonedTime

In this example, I'm using GHCi (the Haskell REPL) to show the composition in two steps. The first step creates `adjustments`

, which is a list of functions. In case you're wondering about the use of the `reverse`

function, it turns out that `mconcat`

composes from right to left, which I found counter-intuitive in this case. `adjustToNextMonth`

should execute first, followed by `adjustToBusinessHours`

, and so on. Defining the functions in the more intuitive left-to-right direction and then reversing it makes the code easier to understand, I hope.

(For the Haskell connoisseurs, you can also achieve the same result by composing `Endo`

with the `Dual`

monoid, instead of reversing the list of adjustments.)

The second step composes `adjust`

from `adjustments`

. It first maps `adjustments`

to `Endo`

values. While `ZonedTime -> ZonedTime`

isn't a `Monoid`

instances, `Endo ZonedTime`

is. This means that you can reduce a list of `Endo ZonedTime`

with `mconcat`

. The result is a single `Endo ZonedTime`

value, which you can then unwrap to a function using `appEndo`

.

`adjust`

is a function that you can call:

λ> dt 2017-01-31 07:45:55 +0200 λ> adjust dt 2017-02-28 07:00:00 +0000

In this example, I'd already prepared a `ZonedTime`

value called `dt`

. Calling `adjust`

returns a new `ZonedTime`

adjusted by all four composed functions.

### Conclusion #

In general, you implement the Composite design pattern by calling all composed functions with the original input value, collecting the return value of each call. In the final step, you then reduce the collected return values to a single value that you return. This requires the return type to form a monoid, because otherwise, you can't reduce it.

In this article, however, you learned about an alternative implementation of the Composite design pattern. If the method that you compose has the same output type as its input, you can pass the output from one object as the input to the next object. In that case, you can escape the requirement that the return value is a monoid. That's the case with `DateTimeOffset`

and `ZonedTime`

: neither are monoids, because you can't add two dates and times together.

At first glance, then, it seems like a falsification of the original claim that Composites are monoids. As you've learned in this article, however, endomorphisms are monoids, so the claim still stands.

**Next:** Null Object as identity.

## Coalescing Composite as a monoid

*A variation of the Composite design pattern uses coalescing behaviour to return non-composable values. That's still a monoid.*

This article is part of a series of articles about design patterns and their category theory counterparts. In a previous article, you learned that the Composite design pattern is simply a monoid.

### Monoidal return types #

When all methods of an interface return monoids, you can create a Composite. This is fairly intuitive once you understand what a monoid is. Consider this example interface:

public interface ICustomerRepository { void Create(Customer customer); Customer Read(Guid id); void Update(Customer customer); void Delete(Guid id); }

While this interface is, in fact, not readily composable, most of the methods are. It's easy to compose the three `void`

methods. Here's a composition of the `Create`

method:

public void Create(Customer customer) { foreach (var repository in this.repositories) repository.Create(customer); }

In this case it's easy to compose multiple repositories, because `void`

(or, rather, *unit*) forms a monoid. If you have methods that return numbers, you can add the numbers together (a monoid). If you have methods that return strings, you can concatenate the strings (a monoid). If you have methods that return Boolean values, you can *or* or *and* them together (more monoids).

What about the above `Read`

method, though?

### Picking the first Repository #

Why would you even want to compose two repositories? One scenario is where you have an old data store, and you want to move to a new data store. For a while, you wish to write to both data stores, but one of them stays the 'primary' data store, so this is the one from which you read.

Imagine that the old repository saves customer information as JSON files on disk. The new data store, on the other hand, saves customer data as JSON documents in Azure Blob Storage. You've already written two implementations of `ICustomerRepository`

: `FileCustomerRepository`

and `AzureCustomerRepository`

. How do you compose them?

The three methods that return `void`

are easy, as the above `Create`

implementation demonstrates. The `Read`

method, however, is more tricky.

One option is to only query the first repository, and return its return value:

public Customer Read(Guid id) { return this.repositories.First().Read(id); }

This works, but doesn't generalise. It works if you know that you have a non-empty collection of repositories, but if you want to adhere to the Liskov Substitution Principle, you should be able to handle the case where there's no repositories.

A Composite should be able to compose an arbitrary number of other objects. This includes a collection of no objects. The `CompositeCustomerRepository`

class has this constructor:

private readonly IReadOnlyCollection<ICustomerRepository> repositories; public CompositeCustomerRepository( IReadOnlyCollection<ICustomerRepository> repositories) { if (repositories == null) throw new ArgumentNullException(nameof(repositories)); this.repositories = repositories; }

It uses standard Constructor Injection to inject an `IReadOnlyCollection<ICustomerRepository>`

. Such a collection is finite, but can be empty.

Another problem with blindly returning the value from the first repository is that the return value may be empty.

In C#, people often use `null`

to indicate a missing value, and while I find such practice unwise, I'll pursue this option for a bit.

A more robust Composite would return the first non-null value it gets:

public Customer Read(Guid id) { foreach (var repository in this.repositories) { var customer = repository.Read(id); if (customer != null) return customer; } return null; }

This implementation loops through all the injected `repositories`

and calls `Read`

on each until it gets a result that is not `null`

. This will often be the first value, but doesn't have to be. If all repositories return `null`

, then the Composite also returns `null`

. To emphasise my position, I would never design C# code like this, but at least it's consistent.

If you've ever worked with relational databases, you may have had an opportunity to use the `COALESCE`

function, which works in exactly the same way. This is the reason I call such an implementation a *coalescing Composite*.

### The First monoid #

The T-SQL documentation for COALESCE describes the operation like this:

```
"Evaluates the arguments in order and returns the current value of the first expression that initially does not evaluate to
````NULL`

."

The Oracle documentation expresses it as:
"This may not be apparent, but that's a monoid.`COALESCE`

returns the first non-null`expr`

in the expression list."

Haskell's base library comes with a monoidal type called `First`

, which is a

"Maybe monoid returning the leftmost non-Nothing value."Sounds familiar?

Here's how you can use it in GHCi:

λ> First (Just (Customer id1 "Joan")) <> First (Just (Customer id2 "Nigel")) First {getFirst = Just (Customer {customerId = 1243, customerName = "Joan"})} λ> First (Just (Customer id1 "Joan")) <> First Nothing First {getFirst = Just (Customer {customerId = 1243, customerName = "Joan"})} λ> First Nothing <> First (Just (Customer id2 "Nigel")) First {getFirst = Just (Customer {customerId = 5cd5, customerName = "Nigel"})} λ> First Nothing <> First Nothing First {getFirst = Nothing}

(To be clear, the above examples uses `First`

from `Data.Monoid`

, not `First`

from `Data.Semigroup`

.)

The operator `<>`

is an infix alias for `mappend`

- Haskell's polymorphic binary operation.

As long as the left-most value is present, that's the return value, regardless of whether the right value is `Just`

or `Nothing`

. Only when the left value is `Nothing`

is the right value returned. Notice that this value may also be `Nothing`

, causing the entire expression to be `Nothing`

.

That's exactly the same behaviour as the above implementation of the `Read`

method.

### First in C# #

It's easy to port Haskell's `First`

type to C#:

public class First<T> { private readonly T item; private readonly bool hasItem; public First() { this.hasItem = false; } public First(T item) { if (item == null) throw new ArgumentNullException(nameof(item)); this.item = item; this.hasItem = true; } public First<T> FindFirst(First<T> other) { if (this.hasItem) return this; else return other; } }

Instead of nesting `Maybe`

inside of `First`

, as Haskell does, I simplified a bit and gave `First<T>`

two constructor overloads: one that takes a value, and one that doesn't. The `FindFirst`

method is the binary operation that corresponds to Haskell's `<>`

or `mappend`

.

This is only one of several alternative implementations of the *first* monoid.

In order to make `First<T>`

a monoid, it must also have an identity, which is just an empty value:

public static First<T> Identity<T>() { return new First<T>(); }

This enables you to accumulate an arbitrary number of `First<T>`

values to a single value:

public static First<T> Accumulate<T>(IReadOnlyList<First<T>> firsts) { var acc = Identity<T>(); foreach (var first in firsts) acc = acc.FindFirst(first); return acc; }

You start with the identity, which is also the return value if `firsts`

is empty. If that's not the case, you loop through all `firsts`

and update `acc`

by calling `FindFirst`

.

### A composable Repository #

You can formalise such a design by changing the `ICustomerRepository`

interface:

public interface ICustomerRepository { void Create(Customer customer); First<Customer> Read(Guid id); void Update(Customer customer); void Delete(Guid id); }

In this modified version, `Read`

explicitly returns `First<Customer>`

. The rest of the methods remain as before.

The reusable API of `First`

makes it easy to implement a Composite version of `Read`

:

public First<Customer> Read(Guid id) { var candidates = new List<First<Customer>>(); foreach (var repository in this.repositories) candidates.Add(repository.Read(id)); return First.Accumulate(candidates); }

You could argue that this seems to be wasteful, because it calls `Read`

on all repositories. If the first Repository returns a value, all remaining queries are wasted. You can address that issue with lazy evaluation.

You can see (a recording of) a live demo of the example in this article in my Clean Coders video Composite as Universal Abstraction.

### Summary #

While the typical Composite is implemented by directly aggregating the return values from the composed objects, variations exist. One variation picks the first non-empty value from a collection of candidates, reminiscent of the SQL `COALESCE`

function. This is, however, still a monoid, so the overall conjecture that Composites are monoids still holds.

Another Composite variation exists, but that one turns out to be a monoid as well. Read on!

## Maybe monoids

*You can combine Maybe objects in several ways. An article for object-oriented programmers.*

This article is part of a series about monoids. In short, a monoid is an associative binary operation with a neutral element (also known as identity).

You can combine Maybe objects in various ways, thereby turning them into monoids. There's at least two unconstrained monoids over Maybe values, as well as some constrained monoids. By *constrained* I mean that the monoid only exists for Maybe objects that contain certain values. You'll see such an example first.

### Combining Maybes over semigroups #

If you have two Maybe objects, and they both (potentially) contain values that form a semigroup, you can combine the Maybe values as well. Here's a few examples.

public static Maybe<int> CombineMinimum(Maybe<int> x, Maybe<int> y) { if (x.HasItem && y.HasItem) return new Maybe<int>(Math.Min(x.Item, y.Item)); if (x.HasItem) return x; return y; }

In this first example, the semigroup operation in question is the *minimum* operation. Since C# doesn't enable you to write generic code over mathematical operations, the above method just gives you an example implemented for `Maybe<int>`

values. If you also want to support e.g. `Maybe<decimal>`

or `Maybe<long>`

, you'll have to add overloads for those types.

If both `x`

and `y`

have values, you get the minimum of those, still wrapped in a Maybe container:

var x = new Maybe<int>(42); var y = new Maybe<int>(1337); var m = Maybe.CombineMinimum(x, y);

Here, `m`

is a `new Maybe<int>(42)`

.

It's possible to combine any two Maybe objects as long as you have a way to combine the contained values in the case where both Maybe objects contain values. In other words, you need a binary operation, so the contained values must form a semigroup, like, for example, the *minimum* operation. Another example is *maximum:*

public static Maybe<decimal> CombineMaximum(Maybe<decimal> x, Maybe<decimal> y) { if (x.HasItem && y.HasItem) return new Maybe<decimal>(Math.Max(x.Item, y.Item)); if (x.HasItem) return x; return y; }

In order to vary the examples, I chose to implement this operation for `decimal`

instead of `int`

, but you can see that the implementation code follows the same template. When both `x`

and `y`

contains values, you invoke the binary operation. If, on the other hand, `y`

is empty, then right identity still holds:

var x = new Maybe<decimal>(42); var y = new Maybe<decimal>(); var m = Maybe.CombineMaximum(x, y);

Since `y`

in the above example is empty, the resulting object `m`

is a `new Maybe<decimal>(42)`

.

You don't have to constrain yourself to semigroups exclusively. You can use a monoid as well, such as the *sum* monoid:

public static Maybe<long> CombineSum(Maybe<long> x, Maybe<long> y) { if (x.HasItem && y.HasItem) return new Maybe<long>(x.Item + y.Item); if (x.HasItem) return x; return y; }

Again, notice how most of this code is boilerplate code that follows the same template as above. In C#, unfortunately, you have to write out all the combinations of operations and contained types, but in Haskell, with its stronger type system, it all comes in the base library:

Prelude Data.Semigroup> Option (Just (Min 42)) <> Option (Just (Min 1337)) Option {getOption = Just (Min {getMin = 42})} Prelude Data.Semigroup> Option (Just (Max 42)) <> mempty Option {getOption = Just (Max {getMax = 42})} Prelude Data.Semigroup> mempty <> Option (Just (Sum 1337)) Option {getOption = Just (Sum {getSum = 1337})}

That particular monoid over Maybe, however, does require as a minimum that the contained values form a semigroup. There are other monoids over Maybe that don't have any such constraints.

### First #

As you can read in the introductory article about semigroups, there's two semigroup operations called *first* and *last*. Similarly, there's two operations by the same name defined over monoids. They behave a little differently, although they're related.

The *first* monoid operation *returns the left-most non-empty value* among candidates. You can view *nothing* as being a type-safe equivalent to null, in which case this monoid is equivalent to a null coalescing operator.

public static Maybe<T> First<T>(Maybe<T> x, Maybe<T> y) { if (x.HasItem) return x; return y; }

As long as `x`

contains a value, `First`

returns it. The contained values don't have to form monoids or semigroups, as this example demonstrates:

var x = new Maybe<Guid>(new Guid("03C2ECDBEF1D46039DE94A9994BA3C1E")); var y = new Maybe<Guid>(new Guid("A1B7BC82928F4DA892D72567548A8826")); var m = Maybe.First(x, y);

While I'm not aware of any reasonable way to combine GUIDs, you can still pick the left-most non-empty value. In the above example, `m`

contains `03C2ECDBEF1D46039DE94A9994BA3C1E`

. If, on the other hand, the first value is empty, you get a different result:

var x = new Maybe<Guid>(); var y = new Maybe<Guid>(new Guid("2A2D19DE89D84EFD9E5BEE7C4ADAFD90")); var m = Maybe.First(x, y);

In this case, `m`

contains `2A2D19DE89D84EFD9E5BEE7C4ADAFD90`

, even though it comes from `y`

.

Notice that there's no guarantee that `First`

returns a non-empty value. If both `x`

and `y`

are empty, then the result is also empty. The `First`

operation is an associative binary operation, and the identity is the empty value (often called *nothing* or *none*). It's a monoid.

### Last #

Since you can define a binary operation called `First`

, it's obvious that you can also define one called `Last`

:

public static Maybe<T> Last<T>(Maybe<T> x, Maybe<T> y) { if (y.HasItem) return y; return x; }

This operation *returns the right-most non-empty value*:

var x = new Maybe<Guid>(new Guid("1D9326CDA0B3484AB495DFD280F990A3")); var y = new Maybe<Guid>(new Guid("FFFC6CE263C7490EA0290017FE02D9D4")); var m = Maybe.Last(x, y);

In this example, `m`

contains `FFFC6CE263C7490EA0290017FE02D9D4`

, but while `Last`

favours `y`

, it'll still return `x`

if `y`

is empty. Notice that, like `First`

, there's no guarantee that you'll receive a populated Maybe. If both `x`

and `y`

are empty, the result will be empty as well.

Like `First`

, `Last`

is an associative binary operation with *nothing* as the identity.

### Generalisation #

The first examples you saw in this article (`CombineMinimum`

, `CombineMaximum`

, and so on), came with the constraint that the contained values form a semigroup. The `First`

and `Last`

operations, on the other hand, seem unconstrained. They work even on GUIDs, which notoriously can't be combined.

If you recall, though, *first* and *last* are both associative binary operations. They are, in fact, unconstrained semigroups. Recall the `Last`

semigroup:

public static T Last<T>(T x, T y) { return y; }

This binary operation operates on any unconstrained type `T`

, including `Guid`

. It unconditionally returns `y`

.

You could implement the `Last`

monoid over Maybe using the same template as above, utilising the underlying semigroup:

public static Maybe<T> Last<T>(Maybe<T> x, Maybe<T> y) { if (x.HasItem && y.HasItem) return new Maybe<T>(Last(x.Item, y.Item)); if (x.HasItem) return x; return y; }

This implementation has exactly the same behaviour as the previous implementation of `Last`

shown earlier. You can implement `First`

in the same way.

That's exactly how Haskell works:

Prelude Data.Semigroup Data.UUID.Types> x = sequence $ Last $ fromString "03C2ECDB-EF1D-4603-9DE9-4A9994BA3C1E" Prelude Data.Semigroup Data.UUID.Types> x Just (Last {getLast = 03c2ecdb-ef1d-4603-9de9-4a9994ba3c1e}) Prelude Data.Semigroup Data.UUID.Types> y = sequence $ Last $ fromString "A1B7BC82-928F-4DA8-92D7-2567548A8826" Prelude Data.Semigroup Data.UUID.Types> y Just (Last {getLast = a1b7bc82-928f-4da8-92d7-2567548a8826}) Prelude Data.Semigroup Data.UUID.Types> Option x <> Option y Option {getOption = Just (Last {getLast = a1b7bc82-928f-4da8-92d7-2567548a8826})} Prelude Data.Semigroup Data.UUID.Types> Option x <> mempty Option {getOption = Just (Last {getLast = 03c2ecdb-ef1d-4603-9de9-4a9994ba3c1e})}

The `<>`

operator is the generic binary operation, and the way Haskell works, it changes behaviour depending on the type upon which it operates. `Option`

is a wrapper around `Maybe`

, and `Last`

represents the *last* semigroup. When you stack `UUID`

values inside of `Option Last`

, you get the behaviour of selecting the right-most non-empty value.

In fact,

Any semigroupSmay be turned into a monoid simply by adjoining an elementenot inSand defininge•s=s=s•efor alls∈S.

That's just a mathematical way of saying that if you have a semigroup, you can add an extra value *e* and make *e* behave like the identity for the monoid you're creating. That extra value is *nothing*. The way Haskell's `Data.Semigroup`

module models a monoid over Maybe instances aligns with the underlying mathematics.

### Conclusion #

Just as there's more than one monoid over numbers, and more than one monoid over Boolean values, there's more than one monoid over Maybe values. The most useful one may be the one that elevates any semigroup to a monoid by adding *nothing* as the identity, but others exist. While, at first glance, the *first* and *last* monoids over Maybes look like operations in their own right, they're just applications of the general rule. They elevate the *first* and *last* semigroups to monoids by 'wrapping' them in Maybes, and using *nothing* as the identity.

**Next:** Monoids accumulate.

## The Maybe functor

*A introduction to the Maybe functor for object-oriented programmers.*

This article is an instalment in an article series about functors.

One of the simplest, and easiest to understand, functors is *Maybe*. It's also sometimes known as the *Maybe monad*, but this is not a monad tutorial; it's a functor tutorial. Maybe is many things; one of them is a functor. In F#, Maybe is called `option`

.

### Motivation #

Maybe enables you to model a value that may or may not be present. Object-oriented programmers typically have a hard time grasping the significance of Maybe, since it essentially does the same as *null* in mainstream object-oriented languages. There are differences, however. In languages like C# and Java, most things can be null, which can lead to much defensive coding. What happens more frequently, though, is that programmers forget to check for null, with run-time exceptions as the result.

A Maybe value, on the other hand, makes it explicit that a value may or may not be present. In statically typed languages, it also forces you to deal with the case where no data is present; if you don't, your code will not compile.

Finally, in a language like C#, null has no type, but a Maybe value always has a type.

If you appreciate the tenet that explicit is better than implicit, then you should favour Maybe over null.

### Implementation #

If you've read the introduction, then you know that `IEnumerable<T>`

is a functor. In many ways, Maybe is like `IEnumerable<T>`

, but it's a particular type of collection that can only contain zero or one element(s). There are various ways in which you can implement Maybe in an object-oriented language like C#; here's one:

public sealed class Maybe<T> { internal bool HasItem { get; } internal T Item { get; } public Maybe() { this.HasItem = false; } public Maybe(T item) { if (item == null) throw new ArgumentNullException(nameof(item)); this.HasItem = true; this.Item = item; } public Maybe<TResult> Select<TResult>(Func<T, TResult> selector) { if (selector == null) throw new ArgumentNullException(nameof(selector)); if (this.HasItem) return new Maybe<TResult>(selector(this.Item)); else return new Maybe<TResult>(); } public T GetValueOrFallback(T fallbackValue) { if (fallbackValue == null) throw new ArgumentNullException(nameof(fallbackValue)); if (this.HasItem) return this.Item; else return fallbackValue; } public override bool Equals(object obj) { var other = obj as Maybe<T>; if (other == null) return false; return object.Equals(this.Item, other.Item); } public override int GetHashCode() { return this.HasItem ? this.Item.GetHashCode() : 0; } }

This is a generic class with two constructors. The parameterless constructor indicates the case where no value is present, whereas the other constructor overload indicates the case where exactly one value is available. Notice that a guard clause prevents you from accidentally passing null as a value.

The `Select`

method has the correct signature for a functor. If a value is present, it uses the `selector`

method argument to map `item`

to a new value, and return a new `Maybe<TResult>`

value. If no value is available, then a new empty `Maybe<TResult>`

value is returned.

This class also override `Equals`

. This isn't necessary in order for it to be a functor, but it makes it easier to compare two `Maybe<T>`

values.

A common question about such generic containers is: *how do you get the value out of the container?*

The answer depends on the particular container, but in this example, I decided to enable that functionality with the `GetValueOrFallback`

method. The only way to get the item out of a `Maybe`

value is by supplying a fall-back value that can be used if no value is available. This is one way to guarantee that you, as a client developer, always remember to deal with the empty case.

### Usage #

It's easy to use this `Maybe`

class:

var source = new Maybe<int>(42);

This creates a new `Maybe<int>`

object that contains the value `42`

. If you need to change the value inside the object, you can, for example, do this:

Maybe<string> dest = source.Select(x => x.ToString());

Since C# natively understands functors through its query syntax, you could also have written the above translation like this:

Maybe<string> dest = from x in source select x.ToString();

It's up to you and your collaborators whether you prefer one or the other of those alternatives. In both examples, though, `dest`

is a new populated `Maybe<string>`

object containing the string `"42"`

.

A more realistic example could be as part of a line-of-business application. Many enterprise developers are familiar with the Repository pattern. Imagine that you'd like to query a repository for a `Reservation`

object. If one is found in the database, you'd like to convert it to a view model, so that you can display it.

var viewModel = repository.Read(id) .Select(r => r.ToViewModel()) .GetValueOrFallback(ReservationViewModel.Null);

The repository's `Read`

method returns `Maybe<Reservation>`

, indicating that it's possible that no object is returned. This will happen if you're querying the repository for an `id`

that doesn't exist in the underlying database.

While you can translate the (potential) `Reservation`

object to a view model (using the `ToViewModel`

extension method), you'll have to supply a default view model to handle the case when the reservation wasn't found.

`ReservationViewModel.Null`

is a static read-only class field implementing the Null Object pattern. Here, it's used for the fall-back value, in case no object was returned from the repository.

Notice that while you need a fall-back value at the end of your fluent interface pipeline, you don't need fall-back values for any intermediate steps. Specifically, you don't need a Null Object implementation for your domain model (`Reservation`

). Furthermore, no defensive coding is required, because `Maybe<T>`

guarantees that the object passed to `selector`

is never `null`

.

### First functor law #

A `Select`

method with the right signature isn't enough to be a functor. It must also obey the functor laws. Maybe obeys both laws, which you can demonstrate with a few examples. Here's some test cases for a populated Maybe:

[Theory] [InlineData("")] [InlineData("foo")] [InlineData("bar")] [InlineData("corge")] [InlineData("antidisestablishmentarianism")] public void PopulatedMaybeObeysFirstFunctorLaw(string value) { Func<string, string> id = x => x; var m = new Maybe<string>(value); Assert.Equal(m, m.Select(id)); }

This parametrised unit test uses xUnit.net to demonstrate that a populated Maybe value doesn't change when translated with the local `id`

function, since `id`

returns the input unchanged.

The first functor law holds for an empty Maybe as well:

[Fact] public void EmptyMaybeObeysFirstFunctorLaw() { Func<string, string> id = x => x; var m = new Maybe<string>(); Assert.Equal(m, m.Select(id)); }

When a Maybe starts empty, translating it with `id`

doesn't change that it's empty. It's worth noting, however, that the original and the translated objects are considered equal because `Maybe<T>`

overrides `Equals`

. Even in the case of the empty Maybe, the value returned by `Select(id)`

is a new object, with a memory address different from the original value.

### Second functor law #

You can also demonstrate the second functor law with some examples, starting with some test cases for the populated case:

[Theory] [InlineData("", true)] [InlineData("foo", false)] [InlineData("bar", false)] [InlineData("corge", false)] [InlineData("antidisestablishmentarianism", true)] public void PopulatedMaybeObeysSecondFunctorLaw(string value, bool expected) { Func<string, int> g = s => s.Length; Func<int, bool> f = i => i % 2 == 0; var m = new Maybe<string>(value); Assert.Equal(m.Select(g).Select(f), m.Select(s => f(g(s)))); }

In this parametrised test, `f`

and `g`

are two local functions. `g`

returns the length of a string (for example, the length of *antidisestablishmentarianism* is *28*). `f`

evaluates whether or not a number is even.

Whether you decide to first translate `m`

with `g`

, and then translate the return value with `f`

, or you decide to translate the composition of those functions in a single `Select`

method call, the result should be the same.

The second functor law holds for the empty case as well:

[Fact] public void EmptyMaybeObeysSecondFunctorLaw() { Func<string, int> g = s => s.Length; Func<int, bool> f = i => i % 2 == 0; var m = new Maybe<string>(); Assert.Equal(m.Select(g).Select(f), m.Select(s => f(g(s)))); }

Since `m`

is empty, applying the translations doesn't change that fact - it only changes the type of the resulting object, which is an empty `Maybe<bool>`

.

### Haskell #

In Haskell, Maybe is built in. You can create a `Maybe`

value containing an integer like this (the type annotations are optional):

source :: Maybe Int source = Just 42

Mapping `source`

to a `String`

can be done like this:

dest :: Maybe String dest = fmap show source

The function `fmap`

corresponds to the above C# `Select`

method.

It's also possible to use infix notation:

dest :: Maybe String dest = show <$> source

The `<$>`

operator is an alias for `fmap`

.

Whether you use `fmap`

or `<$>`

, the resulting `dest`

value is `Just "42"`

.

If you want to create an empty `Maybe`

value, you use the `Nothing`

data constructor.

### F# #

Maybe is also a built-in type in F#, but here it's called `option`

instead of `Maybe`

. You create an option containing an integer like this:

// int option let source = Some 42

While the case where a value is present was denoted with `Just`

in Haskell, in F# it's called `Some`

.

You can translate option values using the `map`

function from the `Option`

module:

// string option let dest = source |> Option.map string

Finally, if you want to create an empty `option`

value, you can use the `None`

case constructor.

### Summary #

Together with a functor called *Either*, Maybe is one of the workhorses of statically typed functional programming. You aren't going to write much F# or Haskell before you run into it. In C# I've used variations of the above `Maybe<T>`

class for years, with much success.

In this article, I only discussed Maybe in its role of being a functor, but it's so much more than that! It's also an applicative functor, a monad, and traversable (enumerable). Not all functors are that rich.

**Next:** Tree.

## Functors

*A functor is a common abstraction. While typically associated with functional programming, functors exist in C# as well.*

This article series is part of a larger series of articles about functors, applicatives, and other mappable containers.

Programming is about abstraction, since you can't manipulate individual sub-atomic particles on your circuit boards. Some abstractions are well-known because they're rooted in mathematics. Particularly, category theory has proven to be fertile ground for functional programming. Some of the concepts from category theory apply to object-oriented programming as well; all you need is generics, which is a feature of both C# and Java.

In previous articles, you got an introduction to the specific Test Data Builder and Test Data Generator functors. Functors are more common than you may realise, although in programming, we usually work with a subset of functors called *endofunctors*. In daily speak, however, we just call them *functors*.

In the next series of articles, you'll see plenty of examples of functors, with code examples in both C#, F#, and Haskell. These articles are mostly aimed at object-oriented programmers curious about the concept.

- Maybe
- Tree
- Visitor
- Observable

`IEnumerable<T>`

. Since the combination of `IEnumerable<T>`

and query syntax is already well-described, I'm not going to cover it explicitly here.
If you understand how LINQ, `IEnumerable<T>`

, and C# query syntax works, however, all other functors should feel intuitive. That's the power of abstractions.

### Overview #

The purpose of this article isn't to give you a comprehensive introduction to the category theory of functors. Rather, the purpose is to give you an opportunity to learn how it translates to object-oriented code like C#. For a great introduction to functors, see Bartosz Milewski's explanation with illustrations.

In short, a functor is a mapping between two categories. A functor maps not only objects, but also functions (called *morphisms*) between objects. For instance, a functor *F* may be a mapping between the categories *C* and *D*:

Not only does *F* map *a* from *C* to *F a* in *D* (and likewise for *b*), it also maps the function *f* to *F f*. Functors preserve the structure between objects. You'll often hear the phrase that a functor is a *structure-preserving map*. One example of this regards lists. You can translate a `List<int>`

to a `List<string>`

, but the translation preserves the structure. This means that the resulting object is also a list, and the order of values within the lists doesn't change.

In category theory, categories are often named *C*, *D*, and so on, but an example of a category could be `IEnumerable<T>`

. If you have a function that translates integers to strings, the source *object* (that's what it's called, but it's not the same as an OOP object) could be `IEnumerable<int>`

, and the destination object could be `IEnumerable<string>`

. A functor, then, represents the ability to go from `IEnumerable<int>`

to `IEnumerable<string>`

, and since the Select method gives you that ability, `IEnumerable<T>.Select`

is a functor. In this case, you sort of 'stay within' the category of `IEnumerable<T>`

, only you change the generic type argument, so this functor is really an endofunctor (the *endo* prefix is from Greek, meaning *within*).

As a rule of thumb, if you have a type with a generic type argument, it's a candidate to be a functor. Such a type is not always a functor, because it also depends on where the generic type argument appears, and some other rules.

Fundamentally, you must be able to implement a method for your generic type that looks like this:

public Functor<TResult> Select<TResult>(Func<T, TResult> selector)

Here, I've defined the `Select`

method as an instance method on a class called `Functor<T>`

, but often, as is the case with `IEnumerable<T>`

, the method is instead implemented as an extension method. You don't have to name it `Select`

, but doing so enables query syntax in C#:

var dest = from x in source select x.ToString();

Here, `source`

is a `Functor<int>`

object.

If you don't name the method `Select`

, it could still be a functor, but then query syntax wouldn't work. Instead, normal method-call syntax would be your only option. This is, however, a specific C# language feature. F#, for example, has no particular built-in awareness of functors, although most libraries name the central function `map`

. In Haskell, `Functor`

is a typeclass that defines a function called `fmap`

.

The common trait is that there's an input value (`Functor<T>`

in the above C# code snippet), which, when combined with a mapping function (`Func<T, TResult>`

), returns an output value of the same generic type, but with a different generic type argument (`Functor<TResult>`

).

### Laws #

Defining a `Select`

method isn't enough. The method must also obey the so-called *functor laws*. These are quite intuitive laws that govern that a functor behaves correctly.

The first law is that mapping the identity function returns the functor unchanged. The *identity function* is a function that returns all input unchanged. (It's called the *identity function* because it's the *identity* for the endomorphism monoid.) In F# and Haskell, this is simply a built-in function called `id`

.

In C#, you can write a demonstration of the law as a unit test:

[Theory] [InlineData(-101)] [InlineData(-1)] [InlineData(0)] [InlineData(1)] [InlineData(42)] [InlineData(1337)] public void FunctorObeysFirstFunctorLaw(int value) { Func<int, int> id = x => x; var sut = new Functor<int>(value); Assert.Equal(sut, sut.Select(id)); }

While this doesn't *prove* that the first law holds for all values and all generic type arguments, it illustrates what's going on.

Since C# doesn't have a built-in identity function, the test creates a specialised identity function for integers, and calls it `id`

. It simply returns all input values unchanged. Since `id`

doesn't change the value, then `Select(id)`

shouldn't change the functor, either. There's nothing more to the first law than this.

The second law states that if you have two functions, `f`

and `g`

, then mapping over one after the other should be the same as mapping over the composition of `f`

and `g`

. In C#, you can illustrate it like this:

[Theory] [InlineData(-101)] [InlineData(-1)] [InlineData(0)] [InlineData(1)] [InlineData(42)] [InlineData(1337)] public void FunctorObeysSecondFunctorLaw(int value) { Func<int, string> g = i => i.ToString(); Func<string, string> f = s => new string(s.Reverse().ToArray()); var sut = new Functor<int>(value); Assert.Equal(sut.Select(g).Select(f), sut.Select(i => f(g(i)))); }

Here, `g`

is a function that translates an `int`

to a `string`

, and `f`

reverses a string. Since `g`

returns `string`

, you can compose it with `f`

, which takes `string`

as input.

As the assertion points out, it shouldn't matter if you call `Select`

piecemeal, first with `g`

and then with `f`

, or if you call `Select`

with the composed function `f(g(i))`

.

### Summary #

This is not a monad tutorial; it's a functor tutorial. Functors are commonplace, so it's worth keeping an eye out for them. If you already understand how LINQ (or similar concepts in Java) work, then functors should be intuitive, because they are all based on the same underlying maths.

While this article is an overview article, it's also a part of a larger series of articles that explore what object-oriented programmers can learn from category theory.

**Next:** Maybe.

## Functors, applicatives, and friends

*Functors and related data structures are containers of values. It's a family of abstractions. An overview 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.

If you've worked with C# or Java recently, you've most likely encountered types such as `Foo<T>`

or `Bar<T>`

(specifically, on .NET, e.g. List<T>). Perhaps you've also noticed that often, you can translate the type inside of the container. For example, if you have a `Foo<string>`

, perhaps you can call some method on it that returns a `Foo<int>`

. If so, it may be a *functor*.

Not all generic types are functors. In order to be a functor, a generic type must obey a couple of intuitive laws. You'll learn about those in future articles.

Some functors have extra capabilities, and you'll learn about some of those as well. Some are called *applicative functors*, and some are called *bifunctors*. There are others, as well.

All applicative functors are functors, and this is true for bifunctors as well.

In this article series, you'll learn about the following categories:

- Functors
- Maybe
- Tree
- Visitor
- Observable

- Applicative functors
- Deck of cards
- Guess a password
- Applicative sequences as combinations
- Maybe
- Validation
- Test Data Generator
- Danish CPR numbers in F#

- Bifunctors
- Tuple bifunctor
- Either bifunctor

**Next:** Functors.

## Composite as a monoid

*When can you use the Composite design pattern? When the return types of your methods are 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.

## Some design patterns as universal abstractions

*Some design patterns can be formalised by fundamental abstractions.*

This article series submits results based on the work presented in an even larger series of articles about the relationship between design patterns and category theory.

Wouldn't it be wonderful if you could assemble software from predefined building blocks? This idea is *old*, and has been the driving force behind object-oriented programming (OOP). In Douglas Coupland's 1995 novel Microserfs, the characters attempt to reach that goal through a project called *Oop!*. Lego bricks play a role as a metaphor as well.

Decades later, it doesn't look like we're much nearer that goal than before, but I believe that we'd made at least two (rectifiable) mistakes along the way:

- Granularity
- Object-orientation

### Granularity #

Over the years, I've seen several attempts at reducing software development to a matter of putting things together. These attempts have invariably failed.

I believe that one of the reasons for failure is that such projects tend to aim at coarse-grained building blocks. As I explain in the *Interface Segregation Principle* module of my Encapsulation and SOLID Pluralsight course, granularity is a crucial determinant for your ability to create. The coarser-grained the building blocks, the harder it is to create something useful.

Most attempts at software-as-building-blocks have used big, specialised building blocks aimed at non-technical users (*"Look! Create an entire web site without writing a single line of code!"*). That's just like Duplo. You can create exactly what the blocks were designed for, but as soon as you try to create something new and original, you can't.

### Object-orientation #

OOP is another attempt at software-as-building-blocks. In .NET (the OOP framework with which I'm most familiar) the Base Class Library (BCL) is enormous. Many of the reusable objects in the BCL are fine-grained, so at least it's often possible to put them together to create something useful. The problem with an object-oriented library like the .NET BCL, however, is that all the objects are *special*.

The vision was always that software 'components' would be able to 'click' together, just like Lego bricks. The BCL isn't like that. Typically, objects have nothing in common apart from the useless `System.Object`

base class. There's no system. In order to learn how the BCL works, you have to learn the ins and outs of every single class.

Better know a framework.

It doesn't help that OOP was never formally defined. Every time you see or hear a discussion about what 'real' object-orientation is, you can be sure that sooner or later, someone will say: "...but that's not what Alan Kay had in mind."

What Alan Kay had in mind is still unclear to me, but it seems safe to say that it wasn't what we have now (C++, Java, C#).

### Building blocks from category theory #

While we (me included) have been on an a thirty-odd year long detour around object-orientation, I don't think all is lost. I still believe that a Lego-brick-like system exists for software development, but I think that it's a system that we have to *discover* instead of invent.

As I already covered in the introductory article, category theory does, in fact, discuss 'objects'. It's not the same type of object that you know from C# or Java, but some of them do consist of data and behaviour - monoids, for example, or functors. Such object are more like types than objects in the OOP sense.

Another, more crucial, difference to object-oriented programming is that these objects are lawful. An object is only a monoid if it obeys the monoid laws. An object is only a functor if it obeys the functor laws.

Such objects are still fine-grained building blocks, but they fit into a system. You don't have to learn tens of thousands of specific objects in order to get to know a framework. You need to understand the system. You need to understand monoids, functors, applicatives, and a few other universal abstractions (yes: monads too).

Many of these universal abstractions were almost discovered by the Gang of Four twenty years ago, but they weren't quite in place then. Much of that has to do with the fact that functional programming didn't seem like a realistic alternative back then, because of hardware limitations. This has all changed to the better.

### Specific patterns #

In the introductory article about the relationship between design patterns and category theory, you learned that some design patterns significantly overlap concepts from category theory. In this article series, we'll explore the relationships between some of the classic patterns and category theory. I'm not sure that all the patterns from Design Patterns can be reinterpreted as universal abstractions, but the following subset seems promising:

Granted, Null Object is actually not from*Design Patterns*, but as we shall see, it's a special case of Composite, so it fits well into that group.

### Summary #

Some design patterns closely resemble categorical objects. This article provides an overview, whereas the next articles in the series will dive into specifics.

**Next:** Composite as a monoid.

## Inheritance-composition isomorphism

*Reuse via inheritance is isomorphic to composition.*

This article is part of a series of articles about software design isomorphisms.

Chapter 1 of Design Patterns admonishes:

Favor object composition over class inheritancePeople sometimes struggle with this, because they use inheritance as a means to achieve reuse. That's not necessary, because you can use object composition instead.

In the previous article, you learned that an abstract class can be refactored to a concrete class with injected dependencies.

Did you you notice that there was an edge case that I didn't cover?

I didn't cover it because I think it deserves its own article. The case is when you want to reuse a base class' functionality in a derived class. How do you do that with Dependency Injection?

### Calling base #

Imagine a virtual method:

public virtual OutVirt1 Virt1(InVirt1 arg)

In C#, a method is virtual when explicitly marked with the `virtual`

keyword, whereas this is the default in Java. When you override a virtual method in a derived class, you can still invoke the parent class' implementation:

public override OutVirt1 Virt1(InVirt1 arg) { // Do stuff with this and arg var baseResult = base.Virt1(arg); // return an OutVirt1 value }

When you override a virtual method, you can use the `base`

keyword to invoke the parent implementation of the method that you're overriding. The enables you to reuse the base implementation, while at the same time adding new functionality.

### Virtual method as interface #

If you perform the refactoring to Dependency Injection shown in the previous article, you now have an interface:

public interface IVirt1 { OutVirt1 Virt1(InVirt1 arg); }

as well as a default implementation. In the previous article, I showed an example where a single class implements several 'virtual member interfaces'. In order to make this particular example clearer, however, here you instead see a variation where the default implementation of `IVirt1`

is in a class that only implements that interface:

public class DefaultVirt1 : IVirt1 { public OutVirt1 Virt1(InVirt1 arg) { // Do stuff with this and arg; return an OutVirt1 value. } }

`DefaultVirt1.Virt1`

corresponds to the original virtual method on the abstract class. How can you 'override' this default implementation, while still make use of it?

### From base to composition #

You have a default implementation, and instead of replacing all of it, you want to somehow enhance it, but still use the 'base' implementation. Instead of inheritance, you can use composition:

public class OverridingVirt1 : IVirt1 { private readonly IVirt1 @base = new DefaultVirt1(); public OutVirt1 Virt1(InVirt1 arg) { // Do stuff with this and arg var baseResult = @base.Virt1(arg); // return an OutVirt1 value } }

In order to drive home the similarity, I named the class field `@base`

. I couldn't use `base`

as a name, because that's a keyword in C#, but you can use the prefix `@`

in order to use a keyword as a legal C# name. Notice that the body of `OverridingVirt1.Virt1`

is almost identical to the above, inheritance-based overriding method.

As a variation, you can inject `@base`

via the constructor of `OverridingVirt1`

, in which case you have a Decorator.

### Isomorphism #

If you already have an interface with a 'default implementation', and you want to reuse the default implementation, then you can use object composition as shown above. At its core, it's reminiscent of the Decorator design pattern, but instead of receiving the inner object via its constructor, it creates the object itself. You can, however, also use a Decorator in order to achieve the same effect. This will make your code more flexible, but possibly also more error-prone, because you no longer have any guarantee what the 'base' is. This is where the Liskov Substitution Principle becomes important, but that's a digression.

If you're using the previous abstract class isomorphism to refactor to Dependency Injection, you can refactor any use of `base`

to object composition as shown here.

This is a special case of *Replace Inheritance with Delegation* from Refactoring, which also describes the inverse refactoring *Replace Delegation with Inheritance*, thereby making these two refactorings an isomorphism.

### Summary #

This article focuses on a particular issue that you may run into if you try to avoid the use of abstract classes. Many programmers use inheritance in order to achieve reuse, but this is in no way necessary. Favour composition over inheritance.

**Next:** Church encoding.

## Comments

All the examples of using Maybe I recall seeing always wrapped a data type that had a neutral element. So Maybe<int> would resolve to 0 or 1, while Maybe<string> to string.Empty. But what about data types that do not have a neutral element?

Suppose we have this DDD value object, NonEmptyString, written in C#. It has no public constructor and it is instantiated through a static factory method that returns a Maybe<NonEmptyString> containing an initialized NonEmptyString if the given input is not null or whitespace and None otherwise.

How do you treat the None case when calling the maybe.Match method? Since the neutral element for string concatenation is string.empty, an invalid value for this value object, this type has no possibility of having a Null Object.

Can this situation be resolved in the functional way (without throwing an exception) or does it warrant throwing an exception?

Ciprian, thank you for writing. I'm not sure I understand what you man by

Maybewrapping a neutral element. I hope that's not how my introduction to Maybe comes across. Could you point to specific examples?If

`NonEmptyString`

is, as the name implies, a`string`

guaranteed to be non-empty, isn't it just a specialisation of NotEmptyCollection<T>? If so, indeed, there's noidentityfor`NonEmptyString`

(but it does form a Semigroup).Since it's a semigroup, though, you can lift it to a monoid my wrapping it in Maybe. If you do that, the identity of

`Maybe<NonEmptyString>`

would benothing.You are right, Mark. The

`NonEmptyString`

class is indeed a semigroup, thus has no neutral element.This is not what confuses me, but what function to supply in the None case of a

`Maybe<SomeSemigroup>`

when calling the`.Match`

method. In the case of`Maybe<SomeMonoid>`

, it's simple and intuitive, as you simply supply a function that returns the neutral element of that monoid.But what about semigroups?

Here's a couple of generalized examples to better illustrate the question I'm having:

`Maybe<SomeMonoid> firstMaybe = someService.GetSomeMonoid();`

SomeMonoid value = firstMaybe.Match(Some: containedValue => containedValue, None: () => SomeMonoid.NeutralElement);

Maybe<SomeSemigroup> secondMaybe = someService.GetSomeSemigroup();

SomeSemigroup someSemigroup = secondMaybe.Match(Some: containedValue => containedValue, None: () => /*What to do here? Is it appropriate to throw an exception?*/);

I hope this time my question became clearer. I'm still in the process of wrapping my head around functional and category theory concepts, so my terminology may not be pinpoint accurate.

Ciprian, that's the problem with semigroups, isn't it? There's no single natural element to use in the absence of data.

Lifting a semigroup to a Maybe is one way to resolve that problem. Since Maybe is a functor, you can map the contents of the Maybe until you've mapped it into a value for which an identity exists.

In some cases, you can also fold a Maybe value by supplying a default value that makes sense in the specific context. A default value can be an appropriate fall-back value in a given context, even if it isn't a general identity.

I think I got it!

If you want to process that

`Maybe<SomeSemigroup>`

in a functional way, using the .Match(Some: ..., None: ...) method, you actually have to transform the method using it from a mostly statement based one, to a mostly expression based one. You have to pretend you don't know what's inside that Maybe for as long as possible, similar to using Lazy (or lazy evaluation in general).In this fiddle I've played around and created both an imperative and functional query method for retrieving a book by title and author, in order to prove myself that they can be made isomorphic. These two methods are GetBookFunctional and GetBookImperative.

However, I'm now trying to transform the GetBookImperativeWithoutElses into something functional using that .Match method, but I don't think it's possible.

The .Match method's signature is, practically speaking, equivalent to the if-else statement, whereas the GetBookImperativeWithoutElses method uses the if statement, meaning the functional approach will be forced to treat the elses, whereas the imperative one won't.

Wow, so if you want to use this Maybe of semigroup and/or go fully functional, you really have to go deep down the functional rabbit hole.

Also, my guess is there is no guarantee that going from imperative to functional does not introduce more redundancy (like the elses in the second set of methods) into your system.

Am I right in these regards?

Ciprian, thank you for the link to the code. This explains why you're running into trouble. You absolutely can address the scenario that causes you trouble in a nice functional style, but once you start having the need to keep track of error data as well as happy-path data,

Maybeis no longer the data structure you need.Maybeenables you to model a case where data may or may not be available. It enables you distinguish something from nothing. On the other hand, in the absence of data, you have no information about the reason that data is missing.In order to keep track of such information, you need

Either, which models data that's either this or that.I'll cover

Eitherin future posts.