Chain of Responsibility as catamorphisms by Mark Seemann
The Chain of Responsibility design pattern can be viewed as a list fold over the First monoid, followed by a Maybe fold.
This article is part of a series of articles about specific design patterns and their category theory counterparts. In it, you'll see how the Chain of Responsibility design pattern is equivalent to a succession of catamorphisms. First, you apply the First Maybe monoid over the list catamorphism, and then you conclude the reduction with the Maybe catamorphism.
Pattern #
The Chain of Responsibility design pattern gives you a way to model cascading conditionals with an object structure. It's a chain (or linked list) of objects that all implement the same interface (or base class). Each object (apart from the the last) has a reference to the next object in the list.
A client (some other code) calls a method on the first object in the list. If that object can handle the request, it does so, and the interaction ends there. If the method returns a value, the object returns the value.
If the first object determines that it can't handle the method call, it calls the next object in the chain. It only knows the next object as the interface, so the only way it can delegate the call is by calling the same method as the first one. In the above diagram, Imp1 can't handle the method call, so it calls the same method on Imp2, which also can't handle the request and delegates responsibility to Imp3. In the diagram, Imp3 can handle the method call, so it does so and returns a result that propagates back up the chain. In that particular example, Imp4 never gets involved.
You'll see an example below.
One of the advantages of the pattern is that you can rearrange the chain to change its behaviour. You can even do this at run time, if you'd like, since all objects implement the same interface.
User icon example #
Consider an online system that maintains user profiles for users. A user is modelled with the User class:
public User(int id, string name, string email, bool useGravatar, bool useIdenticon)
While I only show the signature of the class' constructor, it should be enough to give you an idea. If you need more details, the entire example code base is available on GitHub.
Apart from an id, a name and email address, a user also has two flags. One flag tracks whether the user wishes to use his or her Gravatar, while another flag tracks if the user would like to use an Identicon. Obviously, both flags could be true, in which case the current business rule states that the Gravatar should take precedence.
If none of the flags are set, users might still have a picture associated with their profile. This could be a picture that they've uploaded to the system, and is being tracked by a database.
If no user icon can be found or generated, ultimately the system should use a fallback, default icon:
To summarise, the current rules are:
- Use Gravatar if flag is set.
- Use Identicon if flag is set.
- Use uploaded picture if available.
- Use default icon.
To request an icon, a client can use the IIconReader interface:
public interface IIconReader { Icon ReadIcon(User user); }
The Icon class is just a Value Object wrapper around a URL. The idea is that such a URL can be used in an img tag to show the icon. Again, the full source code is available on GitHub if you'd like to investigate the details.
The various rules for icon retrieval can be implemented using this interface.
Gravatar reader #
Although you don't have to implement the classes in the order in which you are going to compose them, it seems natural to do so, starting with the Gravatar implementation.
public class GravatarReader : IIconReader { private readonly IIconReader next; public GravatarReader(IIconReader next) { this.next = next; } public Icon ReadIcon(User user) { if (user.UseGravatar) return new Icon(new Gravatar(user.Email).Url); return next.ReadIcon(user); } }
The GravatarReader class both implements the IIconReader interface, but also decorates another object of the same polymorphic type. If user.UseGravatar is true, it generates the appropriate Gravatar URL based on the user's Email address; otherwise, it delegates the work to the next object in the Chain of Responsibility.
The Gravatar class contains the implementation details to generate the Gravatar Url. Again, please refer to the GitHub repository if you're interested in the details.
Identicon reader #
When you compose the chain, according to the above business logic, the next type of icon you should attempt to generate is an Identicon. It's natural to implement the Identicon reader next, then:
public class IdenticonReader : IIconReader { private readonly IIconReader next; public IdenticonReader(IIconReader next) { this.next = next; } public Icon ReadIcon(User user) { if (user.UseIdenticon) return new Icon(new Uri(baseUrl, HashUser(user))); return next.ReadIcon(user); } // Implementation details go here... }
Again, I'm omitting implementation details in order to focus on the Chain of Responsibility design pattern. If user.UseIdenticon is true, the IdenticonReader generates the appropriate Identicon and returns the URL for it; otherwise, it delegates the work to the next object in the chain.
Database icon reader #
The DBIconReader class attempts to find an icon ID in a database. If it succeeds, it creates a URL corresponding to that ID. The assumption is that that resource exists; either it's a file on disk, or it's an image resource generated on the spot based on binary data stored in the database.
public class DBIconReader : IIconReader { private readonly IUserRepository repository; private readonly IIconReader next; public DBIconReader(IUserRepository repository, IIconReader next) { this.repository = repository; this.next = next; } public Icon ReadIcon(User user) { if (!repository.TryReadIconId(user.Id, out string iconId)) return next.ReadIcon(user); var parameters = new Dictionary<string, string> { { "iconId", iconId } }; return new Icon(urlTemplate.BindByName(baseUrl, parameters)); } private readonly Uri baseUrl = new Uri("https://example.com"); private readonly UriTemplate urlTemplate = new UriTemplate("users/{iconId}/icon"); }
This class demonstrates some variations in the way you can implement the Chain of Responsibility design pattern. The above GravatarReader and IdenticonReader classes both follow the same implementation pattern of checking a condition, and then performing work if the condition is true. The delegation to the next object in the chain happens, in those two classes, outside of the if statement.
The DBIconReader class, on the other hand, reverses the structure of the code. It uses a Guard Clause to detect whether to exit early, which is done by delegating work to the next object in the chain.
If TryReadIconId returns true, however, the ReadIcon method proceeds to create the appropriate icon URL.
Another variation on the Chain of Responsibility design pattern demonstrated by the DBIconReader class is that it takes a second dependency, apart from next. The repository is the usual misapplication of the Repository design pattern that everyone think they use correctly. Here, it's used in the common sense to provide access to a database. The main point, though, is that you can add as many other dependencies to a link in the chain as you'd like. All links, apart from the last, however, must have a reference to the next link in the chain.
Default icon reader #
Like linked lists, a Chain of Responsibility has to ultimately terminate. You can use the following DefaultIconReader for that.
public class DefaultIconReader : IIconReader { public Icon ReadIcon(User user) { return Icon.Default; } }
This class unconditionally returns the Default icon. Notice that it doesn't have any next object it delegates to. This terminates the chain. If no previous implementation of the IIconReader has returned an Icon for the user, this one does.
Chain composition #
With four implementations of IIconReader, you can now compose the Chain of Responsibility:
IIconReader reader = new GravatarReader( new IdenticonReader( new DBIconReader(repo, new DefaultIconReader())));
The first link in the chain is a GravatarReader object that contains an IdenticonReader object as its next link, and so on. Referring back to the source code of GravatarReader, notice that its next dependency is declared as an IIconReader. Since the IdenticonReader class implements that interface, you can compose the chain like this, but if you later decide to change the order of the objects, you can do so simply by changing the composition. You could remove objects altogether, or add new classes, and you could even do this at run time, if required.
The DBIconReader class requires an extra IUserRepository dependency, here simply an existing object called repo.
The DefaultIconReader takes no other dependencies, so this effectively terminates the chain. If you try to pass another IIconReader to its constructor, the code doesn't compile.
Haskell proof of concept #
When evaluating whether a design is a functional architecture, I often port the relevant parts to Haskell. You can do the same with the above example, and put it in a form where it's clearer that the Chain of Responsibility pattern is equivalent to two well-known catamorphisms.
Readers not comfortable with Haskell can skip the next few sections. The object-oriented example continues below.
User and Icon types are defined by types equivalent to above. There's no explicit interface, however. Creation of Gravatars and Identicons are both pure functions with the type User -> Maybe Icon. Here's the Gravatar function, but the Identicon function looks similar:
gravatarUrl :: String -> String gravatarUrl email = "https://www.gravatar.com/avatar/" ++ show (hashString email :: MD5Digest) getGravatar :: User -> Maybe Icon getGravatar u = if useGravatar u then Just $ Icon $ gravatarUrl $ userEmail u else Nothing
Reading an icon ID from a database, however, is an impure operation, so the function to do this has the type User -> IO (Maybe Icon).
Lazy I/O in Haskell #
Notice that the database icon-querying function has the return type IO (Maybe Icon). In the introduction you read that the Chain of Responsibility design pattern is a sequence of catamorphisms - the first one over a list of First values. While First is, in itself, a Semigroup instance, it gives rise to a Monoid instance when combined with Maybe. Thus, to showcase the abstractions being used, you could create a list of Maybe (First Icon) values. This forms a Monoid, so is easy to fold.
The problem with that, however, is that IO is strict under evaluation, so while it works, it's no longer lazy. You can combine IO (Maybe (First Icon)) values, but it leads to too much I/O activity.
You can solve this problem with a newtype wrapper:
newtype FirstIO a = FirstIO (MaybeT IO a) deriving (Functor, Applicative, Monad, Alternative) firstIO :: IO (Maybe a) -> FirstIO a firstIO = FirstIO . MaybeT getFirstIO :: FirstIO a -> IO (Maybe a) getFirstIO (FirstIO (MaybeT x)) = x instance Semigroup (FirstIO a) where (<>) = (<|>) instance Monoid (FirstIO a) where mempty = empty
This uses the GeneralizedNewtypeDeriving GHC extension to automatically make FirstIO Functor, Applicative, Monad, and Alternative. It also uses the Alternative instance to implement Semigroup and Monoid. You may recall from the documentation that Alternative is already a "monoid on applicative functors."
Alignment #
You now have three functions with different types: two pure functions with the type User -> Maybe Icon and one impure database-bound function with the type User -> IO (Maybe Icon). In order to have a common abstraction, you should align them so that all types match. At first glance, User -> IO (Maybe (First Icon)) seems like a type that fits all implementations, but that causes too much I/O to take place, so instead, use User -> FirstIO Icon. Here's how to lift the pure getGravatar function:
getGravatarIO :: User -> FirstIO Icon getGravatarIO = firstIO . return . getGravatar
You can lift the other functions in similar fashion, to produce getGravatarIO, getIdenticonIO, and getDBIconIO, all with the mutual type User -> FirstIO Icon.
Haskell composition #
The goal of the Haskell proof of concept is to compose a function that can provide an Icon for any User - just like the above C# composition that uses Chain of Responsibility. There's, however, no way around impurity, because one of the steps involve a database, so the aim is a composition with the type User -> IO Icon.
While a more compact composition is possible, I'll show it in a way that makes the catamorphisms explicit:
getIcon :: User -> IO Icon getIcon u = do let lazyIcons = fmap (\f -> f u) [getGravatarIO, getIdenticonIO, getDBIconIO] m <- getFirstIO $ fold lazyIcons return $ fromMaybe defaultIcon m
The getIcon function starts with a list of all three functions. For each of them, it calls the function with the User value u. This may seem inefficient and redundant, because all three function calls may not be required, but since the return values are FirstIO values, all three function calls are lazily evaluated - even under IO. The result, lazyIcons, is a [FirstIO Icon] value; i.e. a lazily evaluated list of lazily evaluated values.
This first step is just to put the potential values in a form that's recognisable. You can now fold the lazyIcons to a single FirstIO Icon value, and then use getFirstIO to unwrap it. Due to do notation, m is a Maybe Icon value.
This is the first catamorphism. Granted, the generalisation that fold offers is not really required, since lazyIcons is a list; mconcat would have worked just as well. I did, however, choose to use fold (from Data.Foldable) to emphasise the point. While the fold function itself isn't the catamorphism for lists, we know that it's derived from the list catamorphism.
The final step is to utilise the Maybe catamorphism to reduce the Maybe Icon value to an Icon value. Again, the getIcon function doesn't use the Maybe catamorphism directly, but rather the derived fromMaybe function. The Maybe catamorphism is the maybe function, but you can trivially implement fromMaybe with maybe.
For golfers, it's certainly possible to write this function in a more compact manner. Here's a point-free version:
getIcon :: User -> IO Icon getIcon = fmap (fromMaybe defaultIcon) . getFirstIO . fold [getGravatarIO, getIdenticonIO, getDBIconIO]
This alternative version utilises that a -> m is a Monoid instance when m is a Monoid instance. That's the reason that you can fold a list of functions. The more explicit version above doesn't do that, but the behaviour is the same in both cases.
That's all the Haskell code we need to discern the universal abstractions involved in the Chain of Responsibility design pattern. We can now return to the C# code example.
Chains as lists #
The Chain of Responsibility design pattern is often illustrated like above, in a staircase-like diagram. There's, however, no inherent requirement to do so. You could also flatten the diagram:
This looks a lot like a linked list.
The difference is, however, that the terminator of a linked list is usually empty. Here, however, you have two types of objects. All objects apart from the rightmost object represent a potential. Each object may, or may not, handle the method call and produce an outcome; if an object can't handle the method call, it'll delegate to the next object in the chain.
The rightmost object, however, is different. This object can't delegate any further, but must handle the method call. In the icon reader example, this is the DefaultIconReader class.
Once you start to see most of the list as a list of potential values, you may realise that you'll be able to collapse into it a single potential value. This is possible because a list of values where you pick the first non-empty value forms a monoid. This is sometimes called the First monoid.
In other words, you can reduce, or fold, all of the list, except the rightmost value, to a single potential value:
When you do that, however, you're left with a single potential value. The result of folding most of the list is that you get the leftmost non-empty value in the list. There's no guarantee, however, that that value is non-empty. If all the values in the list are empty, the result is also empty. This means that you somehow need to combine a potential value with a value that's guaranteed to be present: the terminator.
You can do that wither another fold:
This second fold isn't a list fold, but rather a Maybe fold.
Maybe #
The First monoid is a monoid over Maybe, so add a Maybe class to the code base. In Haskell, the catamorphism for Maybe is called maybe, but that's not a good method name in object-oriented design. Another option is some variation of fold, but in C#, this functionality tends to be called Aggregate, at least for IEnumerable<T>, so I'll reuse that terminology:
public TResult Aggregate<TResult>(TResult @default, Func<T, TResult> func) { if (func == null) throw new ArgumentNullException(nameof(func)); return hasItem ? func(item) : @default; }
You can implement another, more list-like Aggregate overload from this one, but for this article, you don't need it.
From TryReadIconId to Maybe #
In the above code examples, DBIconReader depends on IUserRepository, which defined this method:
bool TryReadIconId(int userId, out string iconId);
From Tester-Doer isomorphisms we know, however, that such a design is isomorphic to returning a Maybe value, and since that's more composable, do that:
Maybe<string> ReadIconId(int userId);
This requires you to refactor the DBIconReader implementation of the ReadIcon method:
public Icon ReadIcon(User user) { Maybe<string> mid = repository.ReadIconId(user.Id); Lazy<Icon> lazyResult = mid.Aggregate( @default: new Lazy<Icon>(() => next.ReadIcon(user)), func: id => new Lazy<Icon>(() => CreateIcon(id))); return lazyResult.Value; }
A few things are worth a mention. Notice that the above Aggregate method (the Maybe catamorphism) requires you to supply a @default value (to be used if the Maybe object is empty). In the Chain of Responsibility design pattern, however, the fallback value is produced by calling the next object in the chain. If you do this unconditionally, however, you perform too much work. You're only supposed to call next if the current object can't handle the method call.
The solution is to aggregate the mid object to a Lazy<Icon> and then return its Value. The @default value is now a lazy computation that calls next only if its Value is read. When mid is populated, on the other hand, the lazy computation calls the private CreateIcon method when Value is accessed. The private CreateIcon method contains the same logic as before the refactoring.
This change of DBIconReader isn't strictly necessary in order to change the overall Chain of Responsibility to a pair of catamorphisms, but serves, I think, as a nice introduction to the use of the Maybe catamorphism.
Optional icon readers #
Previously, the IIconReader interface required each implementation to return an Icon object:
public interface IIconReader { Icon ReadIcon(User user); }
When you have an object like GravatarReader that may or may not return an Icon, this requirement leads toward the Chain of Responsibility design pattern. You can, however, shift the responsibility of what to do next by changing the interface:
public interface IIconReader { Maybe<Icon> ReadIcon(User user); }
An implementation like GravatarReader becomes simpler:
public class GravatarReader : IIconReader { public Maybe<Icon> ReadIcon(User user) { if (user.UseGravatar) return new Maybe<Icon>(new Icon(new Gravatar(user.Email).Url)); return new Maybe<Icon>(); } }
No longer do you have to pass in a next dependency. Instead, you just return an empty Maybe<Icon> if you can't handle the method call. The same change applies to the IdenticonReader class.
Since Maybe is a functor, and the DBIconReader already works on a Maybe<string> value, its implementation is greatly simplified:
public Maybe<Icon> ReadIcon(User user) { return repository.ReadIconId(user.Id).Select(CreateIcon); }
Since ReadIconId returns a Maybe<string>, you can simply use Select to transform the icon ID to an Icon object if the Maybe is populated.
Coalescing Composite #
As an intermediate step, you can compose the various readers using a Coalescing Composite:
public class CompositeIconReader : IIconReader { private readonly IIconReader[] iconReaders; public CompositeIconReader(params IIconReader[] iconReaders) { this.iconReaders = iconReaders; } public Maybe<Icon> ReadIcon(User user) { foreach (var iconReader in iconReaders) { var mIcon = iconReader.ReadIcon(user); if (IsPopulated(mIcon)) return mIcon; } return new Maybe<Icon>(); } private static bool IsPopulated<T>(Maybe<T> m) { return m.Aggregate(false, _ => true); } }
I prefer a more explicit design over this one, so this is just an intermediate step. This IIconReader implementation composes an array of other IIconReader objects and queries each in order to return the first populated Maybe value it finds. If it doesn't find any populated value, it returns an empty Maybe object.
You can now compose your IIconReader objects into a Composite:
IIconReader reader = new CompositeIconReader( new GravatarReader(), new IdenticonReader(), new DBIconReader(repo));
While this gives you a single object on which you can call ReadIcon, the return value of that method is still a Maybe<Icon> object. You still need to reduce the Maybe<Icon> object to an Icon object. You can do this with a Maybe helper method:
public T GetValueOrDefault(T @default) { return Aggregate(@default, x => x); }
Given a User object named user, you can now use the composition and the GetValueOrDefault method to get an Icon object:
Icon icon = reader.ReadIcon(user).GetValueOrDefault(Icon.Default);
First you use the composed reader to produce a Maybe<Icon> object, and then you use the GetValueOrDefault method to reduce the Maybe<Icon> object to an Icon object.
The latter of these two steps, GetValueOrDefault, is already based on the Maybe catamorphism, but the first step is still too implicit to clearly show the nature of what's actually going on. The next step is to refactor the Coalescing Composite to a list of monoidal values.
First #
While not strictly necessary, you can introduce a First<T> wrapper:
public sealed class First<T> { public First(T item) { if (item == null) throw new ArgumentNullException(nameof(item)); Item = item; } public T Item { get; } public override bool Equals(object obj) { if (!(obj is First<T> other)) return false; return Equals(Item, other.Item); } public override int GetHashCode() { return Item.GetHashCode(); } }
In this particular example, the First<T> class adds no new capabilities, so it's technically redundant. You could add to it methods to combine two First<T> objects into one (since First forms a semigroup), and perhaps a method or two to accumulate multiple values, but in this article, none of those are required.
While the class as shown above doesn't add any behaviour, I like that it signals intent, so I'll use it in that role.
Lazy I/O in C# #
Like in the above Haskell code, you'll need to be able to combine two First<T> objects in a lazy fashion, in such a way that if the first object is populated, the I/O associated with producing the second value never happens. In Haskell I addressed that concern with a newtype that, among other abstractions, is a monoid. You can do the same in C# with an extension method:
public static Lazy<Maybe<First<T>>> FindFirst<T>( this Lazy<Maybe<First<T>>> m, Lazy<Maybe<First<T>>> other) { if (m.Value.IsPopulated()) return m; return other; } private static bool IsPopulated<T>(this Maybe<T> m) { return m.Aggregate(false, _ => true); }
The FindFirst method returns the first (leftmost) non-empty object of two options. It's a lazy version of the First monoid, and that's still a monoid. It's truly lazy because it never accesses the Value property on other. While it has to force evaluation of the first lazy computation, m, it doesn't have to evaluate other. Thus, whenever m is populated, other can remain non-evaluated.
Since monoids accumulate, you can also write an extension method to implement that functionality:
public static Lazy<Maybe<First<T>>> FindFirst<T>(this IEnumerable<Lazy<Maybe<First<T>>>> source) { var identity = new Lazy<Maybe<First<T>>>(() => new Maybe<First<T>>()); return source.Aggregate(identity, (acc, x) => acc.FindFirst(x)); }
This overload just uses the earlier FindFirst extension method to fold an arbitrary number of lazy First<T> objects into one. Notice that Aggregate is the C# name for the list catamorphisms.
You can now compose the desired functionality using the basic building blocks of monoids, functors, and catamorphisms.
Composition from universal abstractions #
The goal is still a function that takes a User object as input and produces an Icon object as output. While you could compose that functionality directly in-line where you need it, I think it may be helpful to package the composition in a Facade object.
public class IconReaderFacade { private readonly IReadOnlyCollection<IIconReader> readers; public IconReaderFacade(IUserRepository repository) { readers = new IIconReader[] { new GravatarReader(), new IdenticonReader(), new DBIconReader(repository) }; } public Icon ReadIcon(User user) { IEnumerable<Lazy<Maybe<First<Icon>>>> lazyIcons = readers .Select(r => new Lazy<Maybe<First<Icon>>>(() => r.ReadIcon(user).Select(i => new First<Icon>(i)))); Lazy<Maybe<First<Icon>>> m = lazyIcons.FindFirst(); return m.Value.Aggregate(Icon.Default, fi => fi.Item); } }
When you initialise an IconReaderFacade object, it creates an array of the desired readers. Whenever ReadIcon is invoked, it first transforms all those readers to a sequence of potential icons. All the values in the sequence are lazily evaluated, so in this step, nothing actually happens, even though it looks as though all readers' ReadIcon method gets called. The Select method is a structure-preserving map, so all readers are still potential producers of Icon objects.
You now have an IEnumerable<Lazy<Maybe<First<Icon>>>>, which must be a good candidate for the prize for the most nested generic .NET type of 2019. It fits, though, the input type for the above FindFirst overload, so you can call that. The result is a single potential value m. That's the list catamorphism applied.
Finally, you force evaluation of the lazy computation and apply the Maybe catamorphism (Aggregate). The @default value is Icon.Default, which gets returned if m turns out to be empty. When m is populated, you pull the Item out of the First object. In either case, you now have an Icon object to return.
This composition has exactly the same behaviour as the initial Chain of Responsibility implementation, but is now composed from universal abstractions.
Summary #
The Chain of Responsibility design pattern describes a flexible way to implement conditional logic. Instead of relying on keywords like if or switch, you can compose the conditional logic from polymorphic objects. This gives you several advantages. One is that you get better separations of concerns, which will tend to make it easier to refactor the code. Another is that it's possible to change the behaviour at run time, by moving the objects around.
You can achieve a similar design, with equivalent advantages, by composing polymorphically similar functions in a list, map the functions to a list of potential values, and then use the list catamorphism to reduce many potential values to one. Finally, you apply the Maybe catamorphism to produce a value, even if the potential value is empty.
