A restaurant sandwich by Mark Seemann
An Impureim Sandwich example in C#.
When learning functional programming (FP) people often struggle with how to organize code. How do you discern and maintain purity? How do you do Dependency Injection in FP? What does a functional architecture look like?
A common FP design pattern is the Impureim Sandwich. The entry point of an application is always impure, so you push all impure actions to the boundary of the system. This is also known as Functional Core, Imperative Shell. If you have a micro-operation-based architecture, which includes all web-based systems, you can often get by with a 'sandwich'. Perform impure actions to collect all the data you need. Pass all data to a pure function. Finally, use impure actions to handle the referentially transparent return value from the pure function.
No design pattern applies universally, and neither does this one. In my experience, however, it's surprisingly often possible to apply this architecture. We're far past the Pareto principle's 80 percent.
Examples may help illustrate the pattern, as well as explore its boundaries. In this article you'll see how I refactored an entry point of a REST API, specifically the PUT handler in the sample code base that accompanies Code That Fits in Your Head.
Starting point #
As discussed in the book, the architecture of the sample code base is, in fact, Functional Core, Imperative Shell. This isn't, however, the main theme of the book, and the code doesn't explicitly apply the Impureim Sandwich. In spirit, that's actually what's going on, but it isn't clear from looking at the code. This was a deliberate choice I made, because I wanted to highlight other software engineering practices. This does have the effect, though, that the Impureim Sandwich is invisible.
For example, the book follows the 80/24 rule closely. This was a didactic choice on my part. Most code bases I've seen in the wild have far too big methods, so I wanted to hammer home the message that it's possible to develop and maintain a non-trivial code base with small code blocks. This meant, however, that I had to split up HTTP request handlers (in ASP.NET known as action methods on Controllers).
The most complex HTTP handler is the one that handles PUT requests for reservations. Clients use this action when they want to make changes to a restaurant reservation.
The action method actually invoked by an HTTP request is this Put method:
[HttpPut("restaurants/{restaurantId}/reservations/{id}")] public async Task<ActionResult> Put( int restaurantId, string id, ReservationDto dto) { if (dto is null) throw new ArgumentNullException(nameof(dto)); if (!Guid.TryParse(id, out var rid)) return new NotFoundResult(); Reservation? reservation = dto.Validate(rid); if (reservation is null) return new BadRequestResult(); var restaurant = await RestaurantDatabase .GetRestaurant(restaurantId).ConfigureAwait(false); if (restaurant is null) return new NotFoundResult(); return await TryUpdate(restaurant, reservation).ConfigureAwait(false); }
Since I, for pedagogical reasons, wanted to fit each method inside an 80x24 box, I made a few somewhat unnatural design choices. The above code is one of them. While I don't consider it completely indefensible, this method does a bit of up-front input validation and verification, and then delegates execution to the TryUpdate method.
This may seem all fine and dandy until you realize that the only caller of TryUpdate is that Put method. A similar thing happens in TryUpdate: It calls a method that has only that one caller. We may try to inline those two methods to see if we can spot the Impureim Sandwich.
Inlined Transaction Script #
Inlining those two methods leave us with a larger, Transaction Script-like entry point:
[HttpPut("restaurants/{restaurantId}/reservations/{id}")] public async Task<ActionResult> Put( int restaurantId, string id, ReservationDto dto) { if (dto is null) throw new ArgumentNullException(nameof(dto)); if (!Guid.TryParse(id, out var rid)) return new NotFoundResult(); Reservation? reservation = dto.Validate(rid); if (reservation is null) return new BadRequestResult(); var restaurant = await RestaurantDatabase .GetRestaurant(restaurantId).ConfigureAwait(false); if (restaurant is null) return new NotFoundResult(); using var scope = new TransactionScope( TransactionScopeAsyncFlowOption.Enabled); var existing = await Repository .ReadReservation(restaurant.Id, reservation.Id) .ConfigureAwait(false); if (existing is null) return new NotFoundResult(); var reservations = await Repository .ReadReservations(restaurant.Id, reservation.At) .ConfigureAwait(false); reservations = reservations.Where(r => r.Id != reservation.Id).ToList(); var now = Clock.GetCurrentDateTime(); var ok = restaurant.MaitreD.WillAccept( now, reservations, reservation); if (!ok) return NoTables500InternalServerError(); await Repository.Update(restaurant.Id, reservation) .ConfigureAwait(false); scope.Complete(); return new OkObjectResult(reservation.ToDto()); }
While I've definitely seen longer methods in the wild, this variation is already so big that it no longer fits on my laptop screen. I have to scroll up and down to read the whole thing. When looking at the bottom of the method, I have to remember what was at the top, because I can no longer see it.
A major point of Code That Fits in Your Head is that what limits programmer productivity is human cognition. If you have to scroll your screen because you can't see the whole method at once, does that fit in your brain? Chances are, it doesn't.
Can you spot the Impureim Sandwich now?
If you can't, that's understandable. It's not really clear because there's quite a few small decisions being made in this code. You could argue, for example, that this decision is referentially transparent:
if (existing is null) return new NotFoundResult();
These two lines of code are deterministic and have no side effects. The branch only returns a NotFoundResult when existing is null. Additionally, these two lines of code are surrounded by impure actions both before and after. Is this the Sandwich, then?
No, it's not. This is how idiomatic imperative code looks. To borrow a diagram from another article, pure and impure code is interleaved without discipline:
Even so, the above Put method implements the Functional Core, Imperative Shell architecture. The Put method is the Imperative Shell, but where's the Functional Core?
Shell perspective #
One thing to be aware of is that when looking at the Imperative Shell code, the Functional Core is close to invisible. This is because it's typically only a single function call.
In the above Put method, this is the Functional Core:
var ok = restaurant.MaitreD.WillAccept( now, reservations, reservation); if (!ok) return NoTables500InternalServerError();
It's only a few lines of code, and had I not given myself the constraint of staying within an 80 character line width, I could have instead laid it out like this and inlined the ok flag:
if (!restaurant.MaitreD.WillAccept(now, reservations, reservation)) return NoTables500InternalServerError();
Now that I try this, in fact, it turns out that this actually still stays within 80 characters. To be honest, I don't know exactly why I had that former code instead of this, but perhaps I found the latter alternative too dense. Or perhaps I simply didn't think of it. Code is rarely perfect. Usually when I revisit a piece of code after having been away from it for some time, I find some thing that I want to change.
In any case, that's beside the point. What matters here is that when you're looking through the Imperative Shell code, the Functional Core looks insignificant. Blink and you'll miss it. Even if we ignore all the other small pure decisions (the if statements) and pretend that we already have an Impureim Sandwich, from this viewpoint, the architecture looks like this:
It's tempting to ask, then: What's all the fuss about? Why even bother?
This is a natural experience for a code reader. After all, if you don't know a code base well, you often start at the entry point to try to understand how the application handles a certain stimulus. Such as an HTTP PUT request. When you do that, you see all of the Imperative Shell code before you see the Functional Core code. This could give you the wrong impression about the balance of responsibility.
After all, code like the above Put method has inlined most of the impure code so that it's right in your face. Granted, there's still some code hiding behind, say, Repository.ReadReservations, but a substantial fraction of the imperative code is visible in the method.
On the other hand, the Functional Core is just a single function call. If we inlined all of that code, too, the picture might rather look like this:
This obviously depends on the de-facto ratio of pure to imperative code. In any case, inlining the pure code is a thought experiment only, because the whole point of functional architecture is that a referentially transparent function fits in your head. Regardless of the complexity and amount of code hiding behind that MaitreD.WillAccept function, the return value is equal to the function call. It's the ultimate abstraction.
Standard combinators #
As I've already suggested, the inlined Put method looks like a Transaction Script. The cyclomatic complexity fortunately hovers on the magical number seven, and branching is exclusively organized around Guard Clauses. Apart from that, there are no nested if statements or for loops.
Apart from the Guard Clauses, this mostly looks like a procedure that runs in a straight line from top to bottom. The exception is all those small conditionals that may cause the procedure to exit prematurely. Conditions like this:
if (!Guid.TryParse(id, out var rid)) return new NotFoundResult();
or
if (reservation is null) return new BadRequestResult();
Such checks occur throughout the method. Each of them are actually small pure islands amidst all the imperative code, but each is ad hoc. Each checks if it's possible for the procedure to continue, and returns a kind of error value if it decides that it's not.
Is there a way to model such 'derailments' from the main flow?
If you've ever encountered Scott Wlaschin's Railway Oriented Programming you may already see where this is going. Railway-oriented programming is a fantastic metaphor, because it gives you a way to visualize that you have, indeed, a main track, but then you have a side track that you may shuffle some trains too. And once the train is on the side track, it can't go back to the main track.
That's how the Either monad works. Instead of all those ad-hoc if statements, we should be able to replace them with what we may call standard combinators. The most important of these combinators is monadic bind. Composing a Transaction Script like Put with standard combinators will 'hide away' those small decisions, and make the Sandwich nature more apparent.
If we had had pure code, we could just have composed Either-valued functions. Unfortunately, most of what's going on in the Put method happens in a Task-based context. Thankfully, Either is one of those monads that nest well, implying that we can turn the combination into a composed TaskEither monad. The linked article shows the core TaskEither SelectMany implementations.
The way to encode all those small decisions between 'main track' or 'side track', then, is to wrap 'naked' values in the desired Task<Either<L, R>> container:
Task.FromResult(id.TryParseGuid().OnNull((ActionResult)new NotFoundResult()))
This little code snippet makes use of a few small building blocks that we also need to introduce. First, .NET's standard TryParse APIs don't, compose, but since they're isomorphic to Maybe-valued functions, you can write an adapter like this:
public static Guid? TryParseGuid(this string candidate) { if (Guid.TryParse(candidate, out var guid)) return guid; else return null; }
In this code base, I treat nullable reference types as equivalent to the Maybe monad, but if your language doesn't have that feature, you can use Maybe instead.
To implement the Put method, however, we don't want nullable (or Maybe) values. We need Either values, so we may introduce a natural transformation:
public static Either<L, R> OnNull<L, R>(this R? candidate, L left) where R : struct { if (candidate.HasValue) return Right<L, R>(candidate.Value); return Left<L, R>(left); }
In Haskell one might just make use of the built-in Maybe catamorphism:
ghci> maybe (Left "boo!") Right $ Just 123 Right 123 ghci> maybe (Left "boo!") Right $ Nothing Left "boo!"
Such conversions from Maybe to Either hover just around the Fairbairn threshold, but since we are going to need it more than once, it makes sense to add a specialized OnNull transformation to the C# code base. The one shown here handles nullable value types, but the code base also includes an overload that handles nullable reference types. It's almost identical.
Support for query syntax #
There's more than one way to consume monadic values in C#. While many C# developers like LINQ, most seem to prefer the familiar method call syntax; that is, just call the Select, SelectMany, and Where methods as the normal extension methods they are. Another option, however, is to use query syntax. This is what I'm aiming for here, since it'll make it easier to spot the Impureim Sandwich.
You'll see the entire sandwich later in the article. Before that, I'll highlight details and explain how to implement them. You can always scroll down to see the end result, and then scroll back here, if that's more to your liking.
The sandwich starts by parsing the id into a GUID using the above building blocks:
var sandwich = from rid in Task.FromResult(id.TryParseGuid().OnNull((ActionResult)new NotFoundResult()))
It then immediately proceeds to Validate (parse, really) the dto into a proper Domain Model:
from reservation in dto.Validate(rid).OnNull((ActionResult)new BadRequestResult())
Notice that the second from expression doesn't wrap the result with Task.FromResult. How does that work? Is the return value of dto.Validate already a Task? No, this works because I added 'degenerate' SelectMany overloads:
public static Task<Either<L, R1>> SelectMany<L, R, R1>( this Task<Either<L, R>> source, Func<R, Either<L, R1>> selector) { return source.SelectMany(x => Task.FromResult(selector(x))); } public static Task<Either<L, R1>> SelectMany<L, U, R, R1>( this Task<Either<L, R>> source, Func<R, Either<L, U>> k, Func<R, U, R1> s) { return source.SelectMany(x => k(x).Select(y => s(x, y))); }
Notice that the selector only produces an Either<L, R1> value, rather than Task<Either<L, R1>>. This allows query syntax to 'pick up' the previous value (rid, which is 'really' a Task<Either<ActionResult, Guid>>) and continue with a function that doesn't produce a Task, but rather just an Either value. The first of these two overloads then wraps that Either value and wraps it with Task.FromResult. The second overload is just the usual ceremony that enables query syntax.
Why, then, doesn't the sandwich use the same trick for rid? Why does it explicitly call Task.FromResult?
As far as I can tell, this is because of type inference. It looks as though the C# compiler infers the monad's type from the first expression. If I change the first expression to
from rid in id.TryParseGuid().OnNull((ActionResult)new NotFoundResult())
the compiler thinks that the query expression is based on Either<L, R>, rather than Task<Either<L, R>>. This means that once we run into the first Task value, the entire expression no longer works.
By explicitly wrapping the first expression in a Task, the compiler correctly infers the monad we'd like it to. If there's a more elegant way to do this, I'm not aware of it.
Values that don't fail #
The sandwich proceeds to query various databases, using the now-familiar OnNull combinators to transform nullable values to Either values.
from restaurant in RestaurantDatabase .GetRestaurant(restaurantId) .OnNull((ActionResult)new NotFoundResult()) from existing in Repository .ReadReservation(restaurant.Id, reservation.Id) .OnNull((ActionResult)new NotFoundResult())
This works like before because both GetRestaurant and ReadReservation are queries that may fail to return a value. Here's the interface definition of ReadReservation:
Task<Reservation?> ReadReservation(int restaurantId, Guid id);
Notice the question mark that indicates that the result may be null.
The GetRestaurant method is similar.
The next query that the sandwich has to perform, however, is different. The return type of the ReadReservations method is Task<IReadOnlyCollection<Reservation>>. Notice that the type contained in the Task is not nullable. Barring database connection errors, this query can't fail. If it finds no data, it returns an empty collection.
Since the value isn't nullable, we can't use OnNull to turn it into a Task<Either<L, R>> value. We could try to use the Right creation function for that.
public static Either<L, R> Right<L, R>(R right) { return Either<L, R>.Right(right); }
This works, but is awkward:
from reservations in Repository .ReadReservations(restaurant.Id, reservation.At) .Traverse(rs => Either.Right<ActionResult, IReadOnlyCollection<Reservation>>(rs))
The problem with calling Either.Right is that while the compiler can infer which type to use for R, it doesn't know what the L type is. Thus, we have to tell it, and we can't tell it what L is without also telling it what R is. Even though it already knows that.
In such scenarios, the F# compiler can usually figure it out, and GHC always can (unless you add some exotic language extensions to your code). C# doesn't have any syntax that enables you to tell the compiler about only the type that it doesn't know about, and let it infer the rest.
All is not lost, though, because there's a little trick you can use in cases such as this. You can let the C# compiler infer the R type so that you only have to tell it what L is. It's a two-stage process. First, define an extension method on R:
public static RightBuilder<R> ToRight<R>(this R right) { return new RightBuilder<R>(right); }
The only type argument on this ToRight method is R, and since the right parameter is of the type R, the C# compiler can always infer the type of R from the type of right.
What's RightBuilder<R>? It's this little auxiliary class:
public sealed class RightBuilder<R> { private readonly R right; public RightBuilder(R right) { this.right = right; } public Either<L, R> WithLeft<L>() { return Either.Right<L, R>(right); } }
The code base for Code That Fits in Your Head was written on .NET 3.1, but today you could have made this a record instead. The only purpose of this class is to break the type inference into two steps so that the R type can be automatically inferred. In this way, you only need to tell the compiler what the L type is.
from reservations in Repository .ReadReservations(restaurant.Id, reservation.At) .Traverse(rs => rs.ToRight().WithLeft<ActionResult>())
As indicated, this style of programming isn't language-neutral. Even if you find this little trick neat, I'd much rather have the compiler just figure it out for me. The entire sandwich query expression is already defined as working with Task<Either<ActionResult, R>>, and the L type can't change like the R type can. Functional compilers can figure this out, and while I intend this article to show object-oriented programmers how functional programming sometimes work, I don't wish to pretend that it's a good idea to write code like this in C#. I've covered that ground already.
Not surprisingly, there's a mirror-image ToLeft/WithRight combo, too.
Working with Commands #
The ultimate goal with the Put method is to modify a row in the database. The method to do that has this interface definition:
Task Update(int restaurantId, Reservation reservation);
I usually call that non-generic Task class for 'asynchronous void' when explaining it to non-C# programmers. The Update method is an asynchronous Command.
Task and void aren't legal values for use with LINQ query syntax, so you have to find a way to work around that limitation. In this case I defined a local helper method to make it look like a Query:
async Task<Reservation> RunUpdate(int restaurantId, Reservation reservation, TransactionScope scope) { await Repository.Update(restaurantId, reservation).ConfigureAwait(false); scope.Complete(); return reservation; }
It just echoes back the reservation parameter once the Update has completed. This makes it composable in the larger query expression.
You'll probably not be surprised when I tell you that both F# and Haskell handle this scenario gracefully, without requiring any hoop-jumping.
Full sandwich #
Those are all the building block. Here's the full sandwich definition, colour-coded like the examples in Impureim sandwich.
Task<Either<ActionResult, OkObjectResult>> sandwich = from rid in Task.FromResult( id.TryParseGuid().OnNull((ActionResult)new NotFoundResult())) from reservation in dto.Validate(rid).OnNull( (ActionResult)new BadRequestResult()) from restaurant in RestaurantDatabase .GetRestaurant(restaurantId) .OnNull((ActionResult)new NotFoundResult()) from existing in Repository .ReadReservation(restaurant.Id, reservation.Id) .OnNull((ActionResult)new NotFoundResult()) from reservations in Repository .ReadReservations(restaurant.Id, reservation.At) .Traverse(rs => rs.ToRight().WithLeft<ActionResult>()) let now = Clock.GetCurrentDateTime() let reservations2 = reservations.Where(r => r.Id != reservation.Id) let ok = restaurant.MaitreD.WillAccept( now, reservations2, reservation) from reservation2 in ok ? reservation.ToRight().WithLeft<ActionResult>() : NoTables500InternalServerError().ToLeft().WithRight<Reservation>() from reservation3 in RunUpdate(restaurant.Id, reservation2, scope) .Traverse(r => r.ToRight().WithLeft<ActionResult>()) select new OkObjectResult(reservation3.ToDto());
As is evident from the colour-coding, this isn't quite a sandwich. The structure is honestly more accurately depicted like this:
As I've previously argued, while the metaphor becomes strained, this still works well as a functional-programming architecture.
As defined here, the sandwich value is a Task that must be awaited.
Either<ActionResult, OkObjectResult> either = await sandwich.ConfigureAwait(false); return either.Match(x => x, x => x);
By awaiting the task, we get an Either value. The Put method, on the other hand, must return an ActionResult. How do you turn an Either object into a single object?
By pattern matching on it, as the code snippet shows. The L type is already an ActionResult, so we return it without changing it. If C# had had a built-in identity function, I'd used that, but idiomatically, we instead use the x => x lambda expression.
The same is the case for the R type, because OkObjectResult inherits from ActionResult. The identity expression automatically performs the type conversion for us.
This, by the way, is a recurring pattern with Either values that I run into in all languages. You've essentially computed an Either<T, T>, with the same type on both sides, and now you just want to return whichever T value is contained in the Either value. You'd think this is such a common pattern that Haskell has a nice abstraction for it, but even Hoogle fails to suggest a commonly-accepted function that does this. Apparently, either id id is considered below the Fairbairn threshold, too.
Conclusion #
This article presents an example of a non-trivial Impureim Sandwich. When I introduced the pattern, I gave a few examples. I'd deliberately chosen these examples to be simple so that they highlighted the structure of the idea. The downside of that didactic choice is that some commenters found the examples too simplistic. Therefore, I think that there's value in going through more complex examples.
The code base that accompanies Code That Fits in Your Head is complex enough that it borders on the realistic. It was deliberately written that way, and since I assume that the code base is familiar to readers of the book, I thought it'd be a good resource to show how an Impureim Sandwich might look. I explicitly chose to refactor the Put method, since it's easily the most complicated process in the code base.
The benefit of that code base is that it's written in a programming language that reach a large audience. Thus, for the reader curious about functional programming I thought that this could also be a useful introduction to some intermediate concepts.
As I've commented along the way, however, I wouldn't expect anyone to write production C# code like this. If you're able to do this, you're also able to do it in a language better suited for this programming paradigm.
