Flattening arrow code using a stack of monads by Mark Seemann
Flatten arrow code with a stack of monads. A horrible example in C#.
In the previous article, you saw how to refactor an injected dependency to a Visitor that implements a free monad. One remaining problem is that some of the code tends towards the Arrow anti-pattern. In this article, you'll see how elegantly you can deal with this in Haskell, how it translates to slightly more verbose F# code, but how, even though it does translate all the way to C#, it stops being nice along the way.
All code for this article is available on GitHub.
Arrow code #
This is the problematic code:
public IReservationsProgram<int?> TryAccept(Reservation reservation) { return ReservationsProgram .IsReservationInFuture(reservation) .SelectMany(isInFuture => { if (!isInFuture) return new Pure<int?>(null); return ReservationsProgram .ReadReservations(reservation.Date) .SelectMany(reservations => { var reservedSeats = reservations.Sum(r => r.Quantity); if (Capacity < reservedSeats + reservation.Quantity) return new Pure<int?>(null); reservation.IsAccepted = true; return ReservationsProgram .Create(reservation) .Select(x => new int?(x)); }); }); }
Perhaps it doesn't look that bad, but I think that that's mostly a result of the original example being as simple as it is. After all, the original example code started out like this:
public int? TryAccept(Reservation reservation) { if (!ReservationsRepository.IsReservationInFuture(reservation)) return null; var reservedSeats = ReservationsRepository .ReadReservations(reservation.Date) .Sum(r => r.Quantity); if (Capacity < reservedSeats + reservation.Quantity) return null; reservation.IsAccepted = true; return ReservationsRepository.Create(reservation); }
The cyclomatic complexity of this method could be as low as 3, so if this was real production code, there'd be no reason to refactor it. As with most of my articles, however, you have to think of this example problem as a stand-in for something more complicated.
If you take a second look at the top version (which is actually the later version), I hope you'll agree that the change has harmed the code. In general, it's more noisy, and it shows a clear tendency towards the dreaded Arrow anti-pattern. Again, it may not look that bad here, but if you imagine that we're looking at a stand-in for a much worse problem, I hope you can see how this could quickly become unsustainable.
Part of the problem is that while C# has some syntactic sugar for monads, you can't branch inside a query expression, so instead it seems as though you're stuck with such nested closures.
First F# attempt #
F#, on the other hand, doesn't have that limitation. In F#, you can branch inside of computation expressions, so would that address the problem? Unfortunately, that's not the whole story. Here's an attempt at writing equivalent code in F#, using a custom reservations computation expression:
// int -> Reservation -> ReservationsProgram<int option> let tryAccept capacity reservation = reservations { let! isInFuture = isReservationInFuture reservation if not isInFuture then return None else let! reservations = readReservations reservation.Date let reservedSeats = List.sumBy (fun r -> r.Quantity) reservations if (capacity < reservedSeats + reservation.Quantity) then return None else let! reservationId = create { reservation with IsAccepted = true } return Some reservationId }
While this is, in my opinion, more readable than the C# code, it doesn't successfully address the Arrow anti-pattern. While it's perfectly possible to branch (that is: use if, then, and else) inside a computation expression, we run into another problem. In statement-based languages like C# and Java, you can use Guard Clauses to return early, as the original, pretty C# example demonstrates. In expression-based languages like F# and Haskell, on the other hand, any if branch must have a corresponding else branch, and both branches must return a value of the same type. This restriction forces the above F# code into the same Arrow shape as the problematic C# code.
Languages like F# and Haskell would be poor languages, though, if they didn't have ways to address problems like this one.
Flattening with MaybeT #
While it already feels unpleasant to write F# code like the above, writing similar code in Haskell would be figuratively painful. In Haskell, however, you essentially just change the return type of your function, pull in some standard library functions, and before you know it, you have nice flat code, with nary an Arrow in sight:
tryAccept :: Int -> Reservation -> MaybeT ReservationsProgram Int tryAccept capacity reservation = do guard =<< isReservationInFuture reservation reservations <- readReservations $ reservationDate reservation let reservedSeats = sum $ reservationQuantity <$> reservations guard $ reservedSeats + reservationQuantity reservation <= capacity create $ reservation { reservationIsAccepted = True }
One of the notable traits of Haskell is that, because of its high-level abstractions, changing the type of an expression can change its behaviour. In this case, I decided to add a MaybeT to the ReservationsProgram Int return type. This means that not only does the following code take place inside the ReservationsProgram free monad, it takes place inside a stack of monads. In this case, the stack consists of Maybe and ReservationsProgram.
What this means is that you can use the built-in guard function to short-circuit the program if the guards fail. Yes, these are literally guard clauses!
Not only does this address the Arrow anti-pattern, it completely flattens the code so that the happy path is emphasised.
Stacking monads in F# #
While Haskell comes with built-in monad transformers that enable you to declaratively stack monads, you'll have to do it manually in F#. It's still possible, though. All it takes to stack ReservationsProgram and option is something like this:
// ('a -> ReservationsProgram<'b option>) -> ReservationsProgram<'a option> -> // ReservationsProgram<'b option> let bind f x = reservations { let! x' = x match x' with | Some x'' -> return! f x'' | None -> return None } type ReservationsOptionBuilder () = member this.Bind (x, f) = bind f x member this.Return x = Pure (Some x) member this.ReturnFrom x = x member this.Zero () = Pure (Some ()) let reservationsOption = ReservationsOptionBuilder ()
This stack of monads specifically handles the combination where a ReservationsProgram contains an option value. It considers the continuation value x' produced by the previous step in a ReservationsProgram, and only continues with f if the value is a Some value. Just like option normally works, it short-circuits further processing if the value is a None value.
While F# doesn't have a general-purpose guard function, you can easily write one for this particular stack of monads:
// bool -> ReservationsProgram<unit option> let guard = function | true -> Pure (Some ()) | false -> Pure None
This function takes a Boolean value as input, and returns Pure (Some ()) when the value is true, and Pure None otherwise. While this seems weird at first glance, this is essentially what Haskell's guard does in the above code listing. The point is that Pure None short-circuits further processing, while Pure (Some ()) allows the program to continue, as per the above bind function.
You can now write a flattened version of tryAccept
// int -> Reservation -> ReservationsProgram<int option> let tryAccept capacity reservation = reservationsOption { do! ReservationsOption.bind guard <| isReservationInFuture reservation let! reservations = readReservations reservation.Date let reservedSeats = List.sumBy (fun r -> r.Quantity) reservations do! guard (reservedSeats + reservation.Quantity <= capacity) return! create { reservation with IsAccepted = true } }
Notice that the type of the function doesn't change. It still returns a ReservationsProgram<int option>, but the implementation is different. Instead of explicitly dealing with branching in a reservations computation expression, it implicitly deals with it in the composed reservationsOption computation expression.
Using the specialised guard function doesn't look as pretty as in Haskell, but it gets the job done.
Maybe as a Visitor #
Can you do the same in C#? Yes, sort of, but it'll be ugly.
As a first step, you'll need a Maybe monad, as this isn't a built-in type in C#. While I'd typically prefer a simpler implementation, since we're already looking at Church-encoded sum types, let's take the Church-encoded Maybe implementation, and refactor it to a Visitor. The IMaybe<T> interface is simply this:
public interface IMaybe<T> { TResult Accept<TResult>(IMaybeVisitor<T, TResult> visitor); }
The Visitor is defined like this:
public interface IMaybeVisitor<T, TResult> { TResult VisitNothing { get; } TResult VisitJust(T just); }
This is, hopefully, not terribly surprising. There's two cases: just and nothing, and only the just case has a value associated. While I'm not going to walk you through all the details, this version of IMaybe<T> is still a monad:
public static IMaybe<TResult> SelectMany<T, TResult>( this IMaybe<T> source, Func<T, IMaybe<TResult>> selector) { return source.Accept(new SelectManyMaybeVisitor<T, TResult>(selector)); }
If you want to see how SelectManyMaybeVisitor<T, TResult> is implemented, you can see it in the code repository, but otherwise, it's also a good exercise to see if you can puzzle it out yourself.
Stacking Reservations and Maybe #
You already have the IReservationsProgram<T> and IMaybe<T> monads. Now you just need to stack them, just like the above F# code:
public static IReservationsProgram<IMaybe<TResult>> SelectMany<T, TResult>( this IReservationsProgram<IMaybe<T>> source, Func<T, IReservationsProgram<IMaybe<TResult>>> selector) { return source.SelectMany(x => x.Accept(new SelectManyMaybeVisitor<T, TResult>(selector))); } private class SelectManyMaybeVisitor<T, TResult> : IMaybeVisitor<T, IReservationsProgram<IMaybe<TResult>>> { private readonly Func<T, IReservationsProgram<IMaybe<TResult>>> selector; public SelectManyMaybeVisitor(Func<T, IReservationsProgram<IMaybe<TResult>>> selector) { this.selector = selector; } public IReservationsProgram<IMaybe<TResult>> VisitNothing { get { return new Pure<IMaybe<TResult>>(new Nothing<TResult>()); } } public IReservationsProgram<IMaybe<TResult>> VisitJust(T just) { return this.selector(just); } }
Just like in the F# code, you can write the code inside of the IReservationsProgram<T> monad. To do that, you call SelectMany on source. The x in that lambda expression is a IMaybe<T> value, so in order to be able to proceed, you'll have to call its Accept method and pass it a Visitor.
The overall signature of the outer SelectMany method is fixed. This is, after all, the monadic bind function, so you know that the return type must be IReservationsProgram<IMaybe<TResult>>. Therefore, this must be the second type argument of the Visitor that you pass to Accept, so the Visitor must have the type IMaybeVisitor<T, IReservationsProgram<IMaybe<TResult>>>. From there, it's 'just' a matter of figuring out how to implement VisitNothing and VisitJust.
In the VisitNothing case, you simply return a new Nothing<TResult>(), but wrapped in a Pure value, so that it becomes an IReservationsProgram<IMaybe<TResult>>, rather than just an IMaybe<TResult>.
In the VisitJust case, you'll need the injected selector, which you can simply call with the input argument and return the result.
In order to support query expressions, you'll also need this special SelectMany overload:
public static IReservationsProgram<IMaybe<TResult>> SelectMany<T, U, TResult>( this IReservationsProgram<IMaybe<T>> source, Func<T, IReservationsProgram<IMaybe<U>>> k, Func<T, U, TResult> s) { return source .SelectMany(x => k(x) .SelectMany(y => new Pure<IMaybe<TResult>>(new Just<TResult>(s(x, y))))); }
This is merely a weird C# technical detail, so I'm not going to tire you with this. It's not interesting.
Guard #
Like the above F# code, you can define a specialised Guard method:
public static IReservationsProgram<IMaybe<Unit>> Guard(bool b) { if (b) return new Pure<IMaybe<Unit>>(new Just<Unit>(Unit.Instance)); else return new Pure<IMaybe<Unit>>(new Nothing<Unit>()); }
It does the same as its F# counterpart, only is it more verbose, and it required me to define a unit type, because C# doesn't have one:
public class Unit { public readonly static Unit Instance = new Unit(); private Unit() { } }
This is simply a Singleton that carries no data. It's like void, but can act as a generic return type, which is what we need here.
Do #
Finally, in order to be able to set IsAccepted to true and make it look like a function, you can add a Do method:
public static IReservationsProgram<IMaybe<Unit>> Do(Action action) { action(); return new Pure<IMaybe<Unit>>(new Just<Unit>(Unit.Instance)); }
This is a nasty piece of impure code, but it'll get the job done. It'd also be possible to refactor to a make the Reservation class immutable, but for this proof of concept code, that's not necessary. It'll be ugly regardless.
The point of the method is to enable method chaining in the Fluent style, even while you're mutating state. In general, I'd like to warn against doing something like this, because the entire point of functional programming is to avoid mutating state. It does allow us, however, to reproduce the original behaviour in the top of the article, which also mutates the reservation argument.
Method chaining #
You can now write TryAccept as an IReservationsProgram<IMaybe<int>> method, instead of IReservationsProgram<int?>. In other words, you replace the int? (Nullable<int>) with IMaybe<int>. This enables you write the entire program as a 'flat' composition, by chaining calls to SelectMany and Select:
public IReservationsProgram<IMaybe<int>> TryAccept(Reservation reservation) { return ReservationsProgram.IsReservationInFuture(reservation) .SelectMany(isInFuture => ReservationsProgram.Guard(isInFuture)) .SelectMany((Unit _) => ReservationsProgram.ReadReservations(reservation.Date)) .Select(reservations => reservations.Sum(r => r.Quantity)) .SelectMany(reservedSeats => ReservationsProgram.Guard(reservedSeats + reservation.Quantity <= Capacity)) .SelectMany((Unit _) => ReservationsProgram.Do(() => { reservation.IsAccepted = true; })) .SelectMany((Unit _) => ReservationsProgram.Create(reservation)); }
You start with ReservationsProgram.IsReservationInFuture and continue with SelectMany off of its return value. Inside SelectMany, you then call ReservationsProgram.Guard in order to short-circuit if isInFuture is false. In fact, that step can be reduced to SelectMany(ReservationsProgram.Guard), using method group syntax.
While Guard returns a program containing Unit, you can still continue with SelectMany to call ReservationsProgram.ReadReservations.
I'm not going to walk you through the rest of this code, but it works.
Query syntax #
If you can write an entire program by chaining SelectMany and Select, chances are you can write it using C# query syntax as well. This turns out to be the case:
public IReservationsProgram<IMaybe<int>> TryAccept(Reservation reservation) { return from isInFuture in ReservationsProgram.IsReservationInFuture(reservation) from _ in ReservationsProgram.Guard(isInFuture) from reservations in ReservationsProgram.ReadReservations(reservation.Date) let reservedSeats = reservations.Sum(r => r.Quantity) from __ in ReservationsProgram.Guard(reservedSeats + reservation.Quantity <= Capacity) from ___ in ReservationsProgram.Do(() => { reservation.IsAccepted = true; }) from id in ReservationsProgram.Create(reservation) select id; }
This is simply the 'sugared' version of the previous code. It's a little more succinct, but whether it's better is subjective at best. I think you'd be challenged to find anyone who'd consider this idiomatic C# code.
It gets the job done, though. It actually works!
To be clear, I'm not particularly impressed with the readability of this. I love the Haskell version, but the C# translation isn't my cup of tea.
Conclusion #
When I go to meetups and conferences, I often get the chance to talk to people who have read my articles or seen my talks on functional programming. I often get the question whether it's possible to use some of the wonderful F# and Haskell concepts in C#. This article answers such questions. Yes, it's possible, but what's the point?
Such code is brittle, because you're dancing on the edge of what C# can do. I had to accept some compromises just to get this proof-of-concept code to work. To add spite to injury, the code is not as readable as idiomatic C#, and it taps into concepts that most C# developers wouldn't be familiar with.
I'd expect most C# programmers to consider a code base like this unreadable. In the amount of time it takes to understand and learn the underlying concepts of monads and their syntactic sugar, one can learn a proper functional programming language like F#. Don't try to make C# do something it wasn't designed to do; just use a functional programming language; you can learn that sooner than you'll be able to make sense of this Frankenstein's monster shown here.
