ploeh blog danish software design
Dependency Injection revisited
Replace Dependency Injection with a Visitor
In a previous article, you saw how you can model any sum type as a Visitor. Does that mean, then, that you can model a free monad as a Visitor?
Yes, it does.
In the F# free monad recipe, you saw how to refactor any injected, interface-based dependency to a free monad. Since a free monad is nothing but a recursive sum type, this means that you now have the tools at your disposal to refactor your injected dependencies to a Visitor.
To be clear, this is an article exploring the boundaries of what's possible with a language like C#. It's not intended to be an endorsement of a particular way to organise code. A conference talk recording that covers the same example also exists.
Dependency Injection example #
I'll walk you through how to do this. We'll start with an example, which, as usual, is about developing an online restaurant reservations system. The code base you'll see here implements the business logic that decides whether or not to accept a reservation request. All code from this article is available on GitHub.
In order to make the example illustrative, but still manageable, we'll look at a single dependency, defined like this:
public interface IReservationsRepository { // This method doesn't belong on a Repository interface. It ought to be // on some sort of ITimeProvider interface, or an extension method // thereof, but in order to keep the example refactorings as simple as // possible, it'll go here for demo purposes. bool IsReservationInFuture(Reservation reservation); IReadOnlyCollection<Reservation> ReadReservations(DateTimeOffset date); int Create(Reservation reservation); }
As the code comment explains, the IsReservationInFuture method doesn't belong on this IReservationsRepository interface. A dedicated 'time provider' dependency would be more appropriate, but as you'll see when you read on, refactoring just one interface to a free monad Visitor is already complicated. Doing it twice would just repeat the process while adding little additional clarity.
Apart from IsReservationInFuture, the IReservationsRepository declares ReadReservations for querying the Repository for existing reservations, and Create for adding a new reservation to the Repository. Notice that the Create method violates the Command Query Separation principle. While better alternatives exist, I decided to design the present example like this because it better illustrates how data could flow through a system.
The only consumer of the interface that we're going to consider is this MaîtreD class:
public class MaîtreD { public MaîtreD(int capacity, IReservationsRepository reservationsRepository) { Capacity = capacity; ReservationsRepository = reservationsRepository; } 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); } public int Capacity { get; } public IReservationsRepository ReservationsRepository { get; } }
This is straightforward example code. First, it queries whether the reservation is in the past, because it makes no sense accepting a reservation in the past.
If it gets past that hurdle, the TryAccept method then queries the injected ReservationsRepository for the reservations already recorded on that date, and calculates the sum of the quantities. This produces reservedSeats - the number of already reserved seats. If the restaurant's Capacity (a Primitive Dependency) is less than the already reserved seats, plus the requested quantity, the method again rejects the reservation. This time, the reason is that there's insufficient remaining capacity to accept it.
Finally, if the reservation makes it past all the guards, IsAccepted is set to true, and the reservation is added to the Repository. Recall that Create returns the ID of the new reservation (presumably a database ID), so that ID is returned from the method. In all other cases, the method returns null. The return type of TryAccept is int? (Nullable<int>), so the int value returned from Create is implicitly converted to int?; the compiler does that.
Testability #
My original motivation for learning about Dependency Injection was that I did Test-Driven Development. Dependency Injection enables you to make automated tests deterministic by replacing common sources of non-determinism with Test Doubles. This is, predictably, also the case here:
[Theory, BookingApiTestConventions] public void TryAcceptReturnsReservationIdInHappyPathScenario( [Frozen]Mock<IReservationsRepository> td, Reservation reservation, IReadOnlyCollection<Reservation> reservations, MaîtreD sut, int excessCapacity, int expected) { td.Setup(r => r.IsReservationInFuture(reservation)).Returns(true); td .Setup(r => r.ReadReservations(reservation.Date)) .Returns(reservations); td.Setup(r => r.Create(reservation)).Returns(expected); var reservedSeats = reservations.Sum(r => r.Quantity); reservation.IsAccepted = false; sut = sut.WithCapacity( reservedSeats + reservation.Quantity + excessCapacity); var actual = sut.TryAccept(reservation); Assert.Equal(expected, actual); Assert.True(reservation.IsAccepted); }
This tests exercises the happy path scenario where the reservation is in the future, and there is enough remaining capacity to accept the request. It uses xUnit.net and Moq with AutoFixture gluing it all together.
Database implementation #
It's nice to be able to test the business logic, but ultimately, you'll need your application to be able to store reservations in some sort of persistent storage like a relational database. That's easy, too. Just implement IReservationsRepository:
public class SqlReservationsRepository : IReservationsRepository { public SqlReservationsRepository(string connectionString) { this.ConnectionString = connectionString; } public string ConnectionString { get; } public bool IsReservationInFuture(Reservation reservation) { return DateTimeOffset.Now < reservation.Date; } public IReadOnlyCollection<Reservation> ReadReservations( DateTimeOffset date) { return this.ReadReservations( date.Date, date.Date.AddDays(1).AddTicks(-1)); } private IReadOnlyCollection<Reservation> ReadReservations( DateTimeOffset min, DateTimeOffset max) { var result = new List<Reservation>(); using (var conn = new SqlConnection(this.ConnectionString)) using (var cmd = new SqlCommand(readByRangeSql, conn)) { cmd.Parameters.Add(new SqlParameter("@MinDate", min)); cmd.Parameters.Add(new SqlParameter("@MaxDate", max)); conn.Open(); using (var rdr = cmd.ExecuteReader()) { while (rdr.Read()) result.Add( new Reservation { Date = (DateTimeOffset)rdr["Date"], Name = (string)rdr["Name"], Email = (string)rdr["Email"], Quantity = (int)rdr["Quantity"] }); } } return result; } private const string readByRangeSql = @" SELECT [Date], [Name], [Email], [Quantity] FROM [dbo].[Reservations] WHERE YEAR(@MinDate) <= YEAR([Date]) AND MONTH(@MinDate) <= MONTH([Date]) AND DAY(@MinDate) <= DAY([Date]) AND YEAR([Date]) <= YEAR(@MaxDate) AND MONTH([Date]) <= MONTH(@MaxDate) AND DAY([Date]) <= DAY(@MaxDate)"; public int Create(Reservation reservation) { using (var conn = new SqlConnection(ConnectionString)) using (var cmd = new SqlCommand(createReservationSql, conn)) { cmd.Parameters.Add( new SqlParameter("@Date", reservation.Date)); cmd.Parameters.Add( new SqlParameter("@Name", reservation.Name)); cmd.Parameters.Add( new SqlParameter("@Email", reservation.Email)); cmd.Parameters.Add( new SqlParameter("@Quantity", reservation.Quantity)); conn.Open(); return cmd.ExecuteNonQuery(); } } private const string createReservationSql = @" INSERT INTO [dbo].[Reservations] ([Date], [Name], [Email], [Quantity]) VALUES (@Date, @Name, @Email, @Quantity)"; }
As has been my position for years, I find it easier to write database implementations using .NET's original ADO.NET API than fighting with an ORM.
Free monad in F# #
In order to refactor IReservationsRepository to a free monad, it's illustrative to first see how it would look in F#. This step is by no means required, but it offers another perspective of the translation that you have to perform. According to the F# free monad recipe, you can represent the IReservationsRepository interface with a sum type that describes the instruction set of the API:
type ReservationsInstruction<'a> = | IsReservationInFuture of (Reservation * (bool -> 'a)) | ReadReservations of (DateTimeOffset * (Reservation list -> 'a)) | Create of (Reservation * (int -> 'a))
Each case corresponds to a method from the original interface, and each contains a tuple. The first element of the tuple should contain the input to the method, so the first element of IsReservationInFuture is a Reservation value, the first element of ReadReservations is a DateTimeOffset, and the first element of Create is a Reservation, just like IsReservationInFuture.
The second tuple element is a continuation. This is a function an interpreter must call once it's produced the value required to continue. This corresponds to the output value from the interface methods, so the input to the continuation associated with IsReservationInFuture is a Boolean value, and so on.
The rest of the F# code example follows the recipe to the letter, so it's not important to list it here. You're welcome to look in the Git repository, if you'd like to see the details.
Church-encoded instruction set #
From Church encodings we know that we can represent a sum type as an interface with a single Match method. The instruction set is a functor, so it has a generic type argument:
public interface IReservationsInstruction<T>
The Match method must take an argument for each case in the sum type. In the above F# code, you can see that there's three cases, corresponding to the three methods in the original IReservationsRepository interface.
Furthermore, we know from the previous articles on Church encodings that the Match method must be generic, and return a value of its generic type argument:
TResult Match<TResult>(
Third, each argument (i.e. each case from the sum type you're encoding) must have this form:
Func<something, TResult> name,
where something is the type of the data associated with the case, and name is the name of the case.
The names are easy: they're isReservationInFuture, readReservations, and create, but what are the types associated with each case?
The F# free monad recipe gives the answer, which is why I chose to include the above F# code. For instance, the type associated with the IsReservationInFuture case is Reservation * (bool -> 'a). That's a tuple, where the first element is a Reservation 'object', and the second element is a function.
Take it slow for the first case, then. A tuple where the first element is a Reservation has the type:
Tuple<Reservation, function-type>
where function-type is the type of the continuation function. In F#, that type was bool -> 'a, which means a function that takes a bool as input, and returns a value of the generic type 'a as output. In our Church-encoded C# code, we call that type T, so you need a function from bool to T; that is: Func<bool, T>. If you plug that into the above tuple type, you get:
Tuple<Reservation, Func<bool, T>>
Again, you can plug that type into the something place-holder further up, to find the type of the input argument that corresponds to the isReservationInFuture case:
Func<Tuple<Reservation, Func<bool, T>>, TResult> isReservationInFuture
Doing this for the two other cases finally reveals the entire Match method:
public interface IReservationsInstruction<T> { TResult Match<TResult>( Func<Tuple<Reservation, Func<bool, T>>, TResult> isReservationInFuture, Func<Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, T>>, TResult> readReservations, Func<Tuple<Reservation, Func<int, T>>, TResult> create); }
That's a worthy candidate for the Ugliest C# method signature of 2018 award, I admit, but it's just an intermediate step. This is how the sausage is made.
Implementations of the instruction set #
The IReservationsInstruction<T> interface defines an API. You'll need classes that implement the interface in order to do something useful. As you've seen multiple times in the articles series about Church encodings, you must add an implementation per case. Starting from the top:
public class IsReservationInFuture<T> : IReservationsInstruction<T> { private readonly Tuple<Reservation, Func<bool, T>> t; public IsReservationInFuture(Tuple<Reservation, Func<bool, T>> t) { this.t = t; } public TResult Match<TResult>( Func<Tuple<Reservation, Func<bool, T>>, TResult> isReservationInFuture, Func<Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, T>>, TResult> readReservations, Func<Tuple<Reservation, Func<int, T>>, TResult> create) { return isReservationInFuture(this.t); } }
This class simply adapts an 'object' of the type Tuple<Reservation, Func<bool, T>> to the IReservationsInstruction<T> interface. Importantly, it unconditionally calls the Match method's isReservationInFuture argument, while ignoring readReservations and create. This is consistent with the previous incarnations of Church-encodings you've seen. It's an automatable process. You implement the two other cases in the same way:
public class ReadReservations<T> : IReservationsInstruction<T> { private readonly Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, T>> t; public ReadReservations(Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, T>> t) { this.t = t; } public TResult Match<TResult>( Func<Tuple<Reservation, Func<bool, T>>, TResult> isReservationInFuture, Func<Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, T>>, TResult> readReservations, Func<Tuple<Reservation, Func<int, T>>, TResult> create) { return readReservations(this.t); } }
and
public class Create<T> : IReservationsInstruction<T> { private readonly Tuple<Reservation, Func<int, T>> t; public Create(Tuple<Reservation, Func<int, T>> t) { this.t = t; } public TResult Match<TResult>( Func<Tuple<Reservation, Func<bool, T>>, TResult> isReservationInFuture, Func<Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, T>>, TResult> readReservations, Func<Tuple<Reservation, Func<int, T>>, TResult> create) { return create(this.t); } }
If you find the class names odd, then that's a fair criticism. I agree that Create isn't the most object-oriented class name. At this point, though, the design is hardly object-oriented, even though the code in use is C#. You can deal with the names later.
Functor #
The IReservationsInstruction<T> interface is generic, and as expected, it's a functor:
public static IReservationsInstruction<TResult> Select<T, TResult>( this IReservationsInstruction<T> source, Func<T, TResult> selector) { return source.Match<IReservationsInstruction<TResult>>( isReservationInFuture: t => new IsReservationInFuture<TResult>( new Tuple<Reservation, Func<bool, TResult>>( t.Item1, b => selector(t.Item2(b)))), readReservations: t => new ReadReservations<TResult>( new Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, TResult>>( t.Item1, d => selector(t.Item2(d)))), create: t => new Create<TResult>( new Tuple<Reservation, Func<int, TResult>>( t.Item1, r => selector(t.Item2(r))))); }
Yes, this is horrendous. The F# code is neater:
let private mapI f = function | IsReservationInFuture (x, next) -> IsReservationInFuture (x, next >> f) | ReadReservations (x, next) -> ReadReservations (x, next >> f) | Create (x, next) -> Create (x, next >> f)
Again, this is an intermediary step. Things will get better.
Church-encoded free monad #
Since IReservationsInstruction<T> is a functor, you can package it as a free monad. This entails creating a wrapper 'program' type for it. This is another sum type, in F# written like this:
type ReservationsProgram<'a> = | Free of ReservationsInstruction<ReservationsProgram<'a>> | Pure of 'a
The direct translation to Church-encoded C#, then, is to a Match method with two arguments:
public interface IReservationsProgram<T> { TResult Match<TResult>( Func<IReservationsInstruction<IReservationsProgram<T>> ,TResult> free, Func<T, TResult> pure); }
While the free case looks intimidating, you arrive at it through the same automatic process as already described.
The pure case is implemented by this trivial class:
public class Pure<T> : IReservationsProgram<T> { private readonly T x; public Pure(T x) { this.x = x; } public TResult Match<TResult>( Func<IReservationsInstruction<IReservationsProgram<T>>, TResult> free, Func<T, TResult> pure) { return pure(this.x); } }
The free case is slightly, but not much, more complex:
public class Free<T> : IReservationsProgram<T> { private readonly IReservationsInstruction<IReservationsProgram<T>> i; public Free(IReservationsInstruction<IReservationsProgram<T>> i) { this.i = i; } public TResult Match<TResult>( Func<IReservationsInstruction<IReservationsProgram<T>>, TResult> free, Func<T, TResult> pure) { return free(this.i); } }
Both of them, true to the plan we're following, call their respective method arguments with the objects that they adapt.
Monad #
In C#, the typical monadic bind function is idiomatically called SelectMany, and for various reasons, you need two overloads:
public static IReservationsProgram<TResult> SelectMany<T, TResult>( this IReservationsProgram<T> source, Func<T, IReservationsProgram<TResult>> selector) { return source.Match( free: i => new Free<TResult>(i.Select(p => p.SelectMany(selector))), pure: x => selector(x)); } public static IReservationsProgram<TResult> SelectMany<T, U, TResult>( this IReservationsProgram<T> source, Func<T, IReservationsProgram<U>> k, Func<T, U, TResult> s) { return source .SelectMany(x => k(x) .SelectMany(y => new Pure<TResult>(s(x, y)))); }
The bottom of the two overloads is required by C# if you want to be able to support various query syntax language constructs. The top overload utilises Match to dispatch between pure and free. Again, the pure case is easy, because you simply call selector with x, and return its result.
The free case is more complicated. While i.Select is the Select method defined for IReservationsInstruction<T>, p.SelectMany is a recursive call to the method itself.
That's a fly in the ointment, as C# doesn't handle recursion as well as F# or Haskell. It'll work fine as long as you don't blow the stack by producing huge programs that have to be interpreted.
Lifts #
Following the free monad recipe, you'll need to lift each of the instruction set cases to the 'program' type. The following are plain helper methods:
public static IReservationsProgram<bool> IsReservationInFuture(Reservation reservation) { return new Free<bool>( new IsReservationInFuture<IReservationsProgram<bool>>( new Tuple<Reservation, Func<bool, IReservationsProgram<bool>>>( reservation, x => new Pure<bool>(x)))); } public static IReservationsProgram<IReadOnlyCollection<Reservation>> ReadReservations( DateTimeOffset date) { return new Free<IReadOnlyCollection<Reservation>>( new ReadReservations<IReservationsProgram<IReadOnlyCollection<Reservation>>>( new Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, IReservationsProgram<IReadOnlyCollection<Reservation>>>>( date, x => new Pure<IReadOnlyCollection<Reservation>>(x)))); } public static IReservationsProgram<int> Create(Reservation reservation) { return new Free<int>( new Create<IReservationsProgram<int>>( new Tuple<Reservation, Func<int, IReservationsProgram<int>>>( reservation, x => new Pure<int>(x)))); }
Again, the (unfortunately required) type information makes this unreadable, but in fact, not much happens. In F#, the same lift functions are three one-liners:
let isReservationInFuture r = Free (IsReservationInFuture (r, Pure)) let readReservations d = Free (ReadReservations (d, Pure)) let create r = Free (Create (r, Pure))
These helper methods serve the sole purpose of making it easier to write client code that produces IReservationsProgram<T> 'objects' (they're actually abstract syntax trees).
MaîtreD #
You now have all the building blocks that enable you to refactor MaîtreD.TryAccept to return an IReservationsProgram<int?>:
public class MaîtreD : IMaîtreD { public MaîtreD(int capacity) { Capacity = capacity; } 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)); }); }); } public int Capacity { get; } }
This is hardly as pretty as the original version that used Dependency Injection, but you should notice an interesting effect: by returning a free monad, you get rid of the injected dependency. While the code still depends on Capacity, that's just a read-only number.
Through the so-called query syntax, C# offers some syntactic sugar for monadic composition, similar to F#'s computation expressions or Haskell's do notation. Where its utility ends, though, is exactly where you need it. Unfortunately, it doesn't support branching (the use of if statements and such) inside of from x in xs expressions, so while we've supplied the requisite SelectMany methods for IReservationsProgram<T>, you can't use them.
Instead, you have to resort to branching inside of each continuation, which, unfortunately, pulls you towards arrow code.
The TryAccept method starts by calling the IsReservationInFuture helper method (defined above), which returns an IReservationsProgram<bool> object. You can't easily pull the bool value out of the container, but you can use SelectMany to define what happens next.
If the reservations is in the future, an interpreter should call the continuation with true, and otherwise, with false. Thus, you can branch on that Boolean value for the next step. If the reservations turned out to be in the past, the return value ought to be null, but you have to package that in an IReservationsProgram<int?>. The correct way to do that is to wrap it in a Pure object.
If the reservation, on the other hand, turned out to be in the future, the program can continue. It proceeds to call the ReadReservations helper method, and again uses SelectMany to define what happens next. An interpreter will supply reservations (presumably read from an actual database), and the code inside the continuation decides what to do next. In the case of insufficient remaining capacity, you return another null wrapped in Pure, but if you decide to accept the reservation, you can finally call the Create helper method and return its return value. Here, however, C#'s implicit conversion no longer works, so you have to explicitly use Select to turn the int into an int?.
Interpreters #
You can still unit test the code by supplying a test-specific interpreter, but in the interest of keeping this article to essentials, I'll refer you to the code repository if you want to see how the tests look at this point.
You're probably more interested in seeing how an interpreter actually interacts with a real database, like the above SqlReservationsRepository class did. The scenario is still the same, only the specifics have changed. Instead of implementing an interface, you'll now have to interpret an IReservationsProgram<int?>. How do you do that?
You do it like you'd traverse any other Church-encoded sum type: use the Match method and supply a handler for each of the cases:
public static T Interpret<T>( this IReservationsProgram<T> program, string connectionString) { return program.Match( pure: x => x, free: i => i.Match( isReservationInFuture: t => t.Item2(IsReservationInFuture(t.Item1)) .Interpret(connectionString), readReservations: t => t.Item2(ReadReservations(t.Item1, connectionString)) .Interpret(connectionString), create: t => t.Item2(Create(t.Item1, connectionString)) .Interpret(connectionString))); }
Since a free monad is a nested, recursive sum type, you'll first have to supply handlers for the pure and free cases. The pure case is, as always, trivial. This is where you finally encounter a leaf node in the abstract syntax tree you're traversing. This is where you get to return the final value of the program.
In the free case, on the other hand, you'll need to handle an IReservationsInstruction<IReservationsProgram<T>> value, which is another Church-encoded sum type. It looks daunting, but is an entirely automatic refactoring: just call Match on that object as well, and supply a handler for each of the cases.
Recall that each of the cases of IReservationsInstruction<T> contains a tuple. The first element (t.Item1) is a value to be used as an input argument for the interpreter. The second element (t.Item2) is a function. Notice that in all three cases, this interpreter calls a helper method with t.Item1 and then calls the continuation t.Item2 with the return value from the helper method; e.g. t.Item2(IsReservationInFuture(t.Item1)). All three continuation functions return a new IReservationsProgram<T>, representing the next step in the program, so you'll have to recursively call Interpret again.
The IsReservationInFuture helper method is simple:
public static bool IsReservationInFuture(Reservation reservation) { return DateTimeOffset.Now < reservation.Date; }
Notice that this is an entirely normal static helper method that every C# programmer should know how to write. You're now back on familiar territory. The same goes for the two other helper methods ReadReservations and Create. They're slightly refactored versions of the above SqlReservationsRepository methods, so I'm not going to repeat them here. Again, you're welcome to look at the details in the code repository.
Refactor instruction arguments to Parameter Object #
As you know from another article, you can refactor any Church-encoded sum type to a Visitor. If you want to do it step-wise, you start by introducing a Parameter Object, as suggested by Refactoring. There's two sum types in play in this code base, but you can arbitrarily choose to start with the instruction set. Instead of taking three method arguments, change the Match method so that it takes only a single argument:
public interface IReservationsInstruction<T> { TResult Match<TResult>( ReservationsInstructionParameters<T, TResult> parameters); }
The new Parameter Object looks like this:
public class ReservationsInstructionParameters<T, TResult> { public ReservationsInstructionParameters( Func<Tuple<Reservation, Func<bool, T>>, TResult> isReservationInFuture, Func<Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, T>>, TResult> readReservations, Func<Tuple<Reservation, Func<int, T>>, TResult> create) { this.IsReservationInFuture = isReservationInFuture; this.ReadReservations = readReservations; this.Create = create; } public Func<Tuple<Reservation, Func<bool, T>>, TResult> IsReservationInFuture { get; } public Func<Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, T>>, TResult> ReadReservations { get; } public Func<Tuple<Reservation, Func<int, T>>, TResult> Create { get; } }
This change clearly just moves things around, so nothing much is yet gained. You'll need to adjust other parts of the code in order to pass an instance of this Parameter Object to the Match method, but that's trivial and automatable work, so I'll skip showing it.
If you've noticed that the ReservationsInstructionParameters<T, TResult> Parameter Object is nothing but a container of three functions, you may not be impressed, but from Object isomorphisms we know that a tuple (or record) of functions is isomorphic to an object, thereby nicely putting everything in place for the next change.
Refactor instruction set Parameter Object to an interface #
Instead of a record of three functions, refactor the Parameter Object to an interface with three members:
public interface IReservationsInstructionParameters<T, TResult> { TResult IsReservationInFuture(Tuple<Reservation, Func<bool, T>> t); TResult ReadReservations(Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, T>> t); TResult Create(Tuple<Reservation, Func<int, T>> t); }
Each function is now a method on the interface. Still not perfect, but better. Again, you have to make all sort of adjustments to code that interacts with the Match method. This is the most laborious refactoring, because in every place where before you could simply pass lambda expressions, you now have to introduce explicit classes that implement the interface.
For example, the database interpreter now has to look like this:
public static T Interpret<T>( this IReservationsProgram<T> program, string connectionString) { return program.Match( pure: x => x, free: i => i.Match( new InterpretReservationsInstructionParameters<T>( connectionString))); }
So far, we've only started refactoring the instruction set, so you still need to handle IReservationsProgram<T> values by supplying two lambda expressions to its Match method. When handling the instruction i, however, you must now supply an implementation of the new IReservationsInstructionParameters<T, TResult> interface.
You can do that by creating a new private, nested class:
private class InterpretReservationsInstructionParameters<T> : IReservationsInstructionParameters<IReservationsProgram<T>, T>
As an example, this class implements the ReadReservations method like this:
public T ReadReservations( Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, IReservationsProgram<T>>> t) { var reservations = ReadReservations( t.Item1.Date, t.Item1.Date.AddDays(1).AddTicks(-1)); return t.Item2(reservations).Interpret(connectionString); } private IReadOnlyCollection<Reservation> ReadReservations( DateTimeOffset min, DateTimeOffset max)
The method first calls a helper method also called ReadReservations to read the reservations from the database. That helper method is a perfectly normal C# method that queries a database. Its implementation is equivalent to the above SqlReservationsRepository.ReadReservations implementation, so while I've included its signature in the above code listing, there's no need to repeat the method body here.
Keep in mind that t is the horribly typed tuple declared as the method argument, so t.Item1 is just a DateTimeOffset value that you can pass as argument(s) to the ReadReservations helper method.
The helper method returns reservations, which is an IReadOnlyCollection<Reservation>. You can now (as before) call the continuation function t.Item2 with that object. The continuation returns a new IReservationsProgram<T> that you'll then have to recursively handle by calling Interpret again. This is just like before the refactoring.
Rename instruction set API #
You're simply following the refactoring steps outlined in Visitor as a sum type, so now you can rename the types involved with the instruction set to follow the naming conventions of the Visitor design pattern:
public interface IReservationsInstructionVisitor<T, TResult> { TResult VisitIsReservationInFuture(Tuple<Reservation, Func<bool, T>> t); TResult VisitReadReservations(Tuple<DateTimeOffset, Func<IReadOnlyCollection<Reservation>, T>> t); TResult VisitCreate(Tuple<Reservation, Func<int, T>> t); }
This is the interface previously named IReservationsInstructionParameters<T, TResult> renamed, and with the word Visit affixed. Likewise, you can also make similar changes to the IReservationsInstruction<T> interface:
public interface IReservationsInstruction<T> { TResult Accept<TResult>(IReservationsInstructionVisitor<T, TResult> visitor); }
These changes are simple rename refactorings, so while they affect much other code, I'm not going to list it all.
Make program API a Visitor #
Following the same refactoring steps, you can also turn IReservationsProgram<T> into an application of the Visitor design pattern:
public interface IReservationsProgram<T> { TResult Accept<TResult>(IReservationsProgramVisitor<T, TResult> visitor); }
You simply rename the Match method to Accept, and call the object passed to it visitor. The Visitor itself is defined like this:
public interface IReservationsProgramVisitor<T, TResult> { TResult VisitFree(IReservationsInstruction<IReservationsProgram<T>> i); TResult VisitPure(T x); }
While these steps conclude the refactoring steps outlined in the previously mentioned article on how to turn a Church-encoded sum type into a Visitor, the resulting code can still benefit from further clean-up.
Refactor tuple argument to argument list #
If you consider the current definition of IReservationsInstructionVisitor<T, TResult> (see above), you'll notice that each method takes a single argument in the shape of a tuple. From Argument list isomorphisms you know that you can refactor such a method into a method that takes a normal argument list:
public interface IReservationsInstructionVisitor<T, TResult> { TResult VisitIsReservationInFuture( Reservation reservation, Func<bool, T> continuation); TResult VisitReadReservations( DateTimeOffset date, Func<IReadOnlyCollection<Reservation>, T> continuation); TResult VisitCreate( Reservation reservation, Func<int, T> continuation); }
Each of these methods now take an input argument (e.g. a Reservation or a DateTimeOffset) and a continuation function. This already improves the API.
SQL Visitor #
In an attempt to make things look proper object-oriented, then, the journey is complete. Instead of a SqlReservationsRepository, you instead need a SqlReservationsProgramVisitor<T>:
public class SqlReservationsProgramVisitor<T> : IReservationsProgramVisitor<T, T>, IReservationsInstructionVisitor<IReservationsProgram<T>, T> { private readonly string connectionString; public SqlReservationsProgramVisitor(string connectionString) { this.connectionString = connectionString; } public T VisitPure(T x) { return x; } public T VisitFree(IReservationsInstruction<IReservationsProgram<T>> i) { return i.Accept(this); } public T VisitIsReservationInFuture( Reservation reservation, Func<bool, IReservationsProgram<T>> continuation) { var isInFuture = DateTimeOffset.Now < reservation.Date; return continuation(isInFuture).Accept(this); } public T VisitReadReservations( DateTimeOffset date, Func<IReadOnlyCollection<Reservation>, IReservationsProgram<T>> continuation) { var reservations = ReadReservations( date.Date, date.Date.AddDays(1).AddTicks(-1)); return continuation(reservations).Accept(this); } private IReadOnlyCollection<Reservation> ReadReservations( DateTimeOffset min, DateTimeOffset max) { var result = new List<Reservation>(); using (var conn = new SqlConnection(connectionString)) using (var cmd = new SqlCommand(readByRangeSql, conn)) { cmd.Parameters.Add(new SqlParameter("@MinDate", min)); cmd.Parameters.Add(new SqlParameter("@MaxDate", max)); conn.Open(); using (var rdr = cmd.ExecuteReader()) { while (rdr.Read()) result.Add( new Reservation { Date = (DateTimeOffset)rdr["Date"], Name = (string)rdr["Name"], Email = (string)rdr["Email"], Quantity = (int)rdr["Quantity"] }); } } return result; } private const string readByRangeSql = @" SELECT [Date], [Name], [Email], [Quantity] FROM [dbo].[Reservations] WHERE YEAR(@MinDate) <= YEAR([Date]) AND MONTH(@MinDate) <= MONTH([Date]) AND DAY(@MinDate) <= DAY([Date]) AND YEAR([Date]) <= YEAR(@MaxDate) AND MONTH([Date]) <= MONTH(@MaxDate) AND DAY([Date]) <= DAY(@MaxDate)"; public T VisitCreate( Reservation reservation, Func<int, IReservationsProgram<T>> continuation) { return continuation(Create(reservation)).Accept(this); } private int Create(Reservation reservation) { using (var conn = new SqlConnection(connectionString)) using (var cmd = new SqlCommand(createReservationSql, conn)) { cmd.Parameters.Add( new SqlParameter("@Date", reservation.Date)); cmd.Parameters.Add( new SqlParameter("@Name", reservation.Name)); cmd.Parameters.Add( new SqlParameter("@Email", reservation.Email)); cmd.Parameters.Add( new SqlParameter("@Quantity", reservation.Quantity)); conn.Open(); return cmd.ExecuteNonQuery(); } } private const string createReservationSql = @" INSERT INTO [dbo].[Reservations] ([Date], [Name], [Email], [Quantity]) VALUES (@Date, @Name, @Email, @Quantity)"; }
Most of this code is similar to the SqlReservationsRepository from the beginning of the article. The IReservationsRepository interface no longer exists; instead this Visitor implements two interfaces: IReservationsProgramVisitor<T, T> and IReservationsInstructionVisitor<IReservationsProgram<T>, T>. A free monad recursively interacts with itself by going back and forth between an 'instruction' and the overall 'program'. Implementing both interfaces in a single class makes it much easier to transition between these two views, as you no longer have to pass e.g. the connectionString around between various objects.
This also means that instead of having to rely on an extension method in order to be able to continue, notice that each method can now continue by calling Accept(this).
Instead of injecting IReservationsRepository into objects, you can call methods that return IReservationsProgram<T> objects and then interpret them using the above SqlReservationsProgramVisitor<T>. For example, you could call TryAccept with a Reservation object:
var p = maîtreD.TryAccept(reservation);
The p variable is an IReservationsProgram<int?> object, where the int? represents a potential reservation ID. At this point, p is a 'program', and you can 'run' it by asking it to accept a Visitor:
var id = p.Accept(new SqlReservationsProgramVisitor<int?>(connectionString));
When Accept returns, id (an int?) has a value, or is null, according to the exact details of reservation and the state of the database.
Testability #
Is this design still testable? Yes, indeed, the overall free monad design is pure, and thereby inherently testable. Instead of using a dynamic mock library like Moq, you can add a test-specific implementation of the free monad Visitor to your unit testing code base:
public class StubReservationsVisitor<T> : IReservationsProgramVisitor<T, T>, IReservationsInstructionVisitor<IReservationsProgram<T>, T> { private readonly bool isInFuture; private readonly IReadOnlyCollection<Reservation> reservations; private readonly int id; public StubReservationsVisitor( bool isInFuture, IReadOnlyCollection<Reservation> reservations, int id) { this.isInFuture = isInFuture; this.reservations = reservations; this.id = id; } public T VisitPure(T x) { return x; } public T VisitFree(IReservationsInstruction<IReservationsProgram<T>> i) { return i.Accept(this); } public T VisitIsReservationInFuture( Reservation reservation, Func<bool, IReservationsProgram<T>> continuation) { return continuation(isInFuture).Accept(this); } public T VisitReadReservations( DateTimeOffset date, Func<IReadOnlyCollection<Reservation>, IReservationsProgram<T>> continuation) { return continuation(reservations).Accept(this); } public T VisitCreate( Reservation reservation, Func<int, IReservationsProgram<T>> continuation) { return continuation(id).Accept(this); } }
As a true Stub, this implementation ignores the input values and returns pre-configured values. When VisitIsReservationInFuture is called, for example, the implementation ignores the reservation argument and instead 'returns' the isInFuture class field by calling continuation(isInFuture).
You can exercise the happy-path test case from the beginning of this article as a unit test using this Stub Visitor:
[Theory, BookingApiTestConventions] public void TryAcceptReturnsReservationIdInHappyPathScenario( Reservation reservation, IReadOnlyCollection<Reservation> reservations, MaîtreD sut, int excessCapacity, int expected) { var reservedSeats = reservations.Sum(r => r.Quantity); reservation.IsAccepted = false; sut = sut.WithCapacity( reservedSeats + reservation.Quantity + excessCapacity); var actual = sut.TryAccept(reservation); Assert.Equal( expected, actual.Accept(new StubReservationsVisitor<int?>(true, reservations, expected))); Assert.True(reservation.IsAccepted); }
This test still uses AutoFixture to create objects such as reservation, reservations, and so on, but instead of relying on dynamic mocks injected into the sut, it uses the StubReservationsVisitor<T> class to interpret the return value from TryAccept.
Arrow code #
From an external perspective, as a user of MaîtreD.TryAccept, the API looks exotic, but to a degree, fairly object-oriented, with its implementation of the Visitor design pattern. Looking at the above internal implementation of the method, however, reveals the most problematic part of this entire exercise. The code doesn't look nice.
Not only do we have nested closures, but it also looks like the dreaded Arrow Code anti-pattern. Partially, the problem is that while C# has some support for monadic syntactic sugar, in the form of query expressions, you can't branch inside a query expression. That's not the whole problem, though. Even in F#, with a computation expression, the equivalent code would look like this:
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 looks smoother, the code still exhibits the arrow shape. There are ways to address that problem, but that's a topic for the next article.
Conclusion #
Even in C#, you can refactor from Dependency Injection to a free monad, implemented as a Visitor. Should you, though?
As a rule of thumb, no, I don't think it's a good idea. Free monads are worth considering in Haskell where they are much closer to being 'free', in the sense that there's little programming overhead involved with defining and using them. Already when you translate a free monad to F# do you discover how much boilerplate programming is involved. Still, due to F#'s computation expressions, a free monad may occasionally be worth considering. Both in implementation and at call sites, you can make the API easy to use.
In C#, you run into its lack of support for branching inside monadic composition. Not only does a free monad look non-idiomatic in C#, but writing the 'programs' without good syntactic sugar for monads make this alternative even less compelling. To make matters worse, the boilerplate code you have to write in C# is positively ugly. As this article is a result of an experiment, I admit that I have no production experience with free monads as Visitors in C#. Still, due to the lack of type inference in crucial parts, I'd venture the guess that the implementation would also prove to be frustratingly refactor-resistant.
Perhaps, one day, you'll run into an edge case where you have a dependency that could benefit from being refactored to a Visitor, but in general, I'd presume that Dependency Injection in C# is the lesser of two evils. Still, I think it's interesting, and illustrative, that it's possible to refactor an injected dependency to a free monad - even in C#!
Angular addition monoid
Geometric angles can be added together. Angular addition forms a monoid.
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).
In geometry, an angle is a measure of how two crossing lines relate to each other. In mathematics, angles are usually represented in radians, but in daily use, they're mostly measured in degrees between 0 and 360.
Angular addition #
You can always draw an angle within a circle. Here's a 45° angle:
If you add another 90° angle to that, you get a 135° angle:
What do you get if you add 90° to 315°?
Well, you get 45°, of course!
There's only 360° in a circle, so overflow is handled, in this case, by subtracting 360°. In general, however, angular addition is nothing but modulo 360 addition.
Angle struct #
You can model a geometric angle as a struct. Here's a simple example:
public struct Angle { private readonly decimal degrees; private Angle(decimal degrees) { this.degrees = degrees % 360m; if (this.degrees < 0) this.degrees += 360m; } public static Angle FromDegrees(decimal degrees) { return new Angle(degrees); } public static Angle FromRadians(double radians) { return new Angle((decimal)((180D / Math.PI) * radians)); } public Angle Add(Angle other) { return new Angle(this.degrees + other.degrees); } public readonly static Angle Identity = new Angle(0); public override bool Equals(object obj) { if (obj is Angle) return ((Angle)obj).degrees == this.degrees; return base.Equals(obj); } public override int GetHashCode() { return this.degrees.GetHashCode(); } public static bool operator ==(Angle x, Angle y) { return x.Equals(y); } public static bool operator !=(Angle x, Angle y) { return !x.Equals(y); } }
Notice the Add method, which is a binary operation; it's an instance method on Angle, takes another Angle as input, and returns an Angle value.
Associativity #
Not only is Add a binary operation; it's also associative. Here's an example:
var x = Angle.FromDegrees(135); var y = Angle.FromDegrees(180); var z = Angle.FromDegrees(300); var left = x.Add(y).Add(z); var right = x.Add(y.Add(z));
Notice that left first evaluates x.Add(y), which is 315°; then it adds 300°, which is 615°, but normalises to 255°. On the other hand, right first evaluates y.Add(z), which is 480°, but normalises to 120°. It then adds those 120° to x, for a final result of 255°. Since left and right are both 255°, this illustrates that Add is associative.
Obviously, this is only a single example, so it's no proof. While still not a proof, you can demonstrate the associativity property with more confidence by writing a property-based test. Here's one using FsCheck and xUnit.net:
[Property(QuietOnSuccess = true)] public void AddIsAssociative(Angle x, Angle y, Angle z) { Assert.Equal( x.Add(y).Add(z), x.Add(y.Add(z))); }
By default, FsCheck generates 100 test cases, but even when I experimentally change the configuration to run 100,000 test cases, they all pass. For full disclosure, however, I'll admit that I defined the data generators to only use NormalFloat for the radian values, and only decimal values with up to 10 decimal places. If you try to use entirely unconstrained floating points, you'll see test failures caused by rounding errors.
Changing the data generator is one way to address rounding errors. Another way is to add a bit of fuzzy tolerance to the assertion. In any case, though, the Add operation is associative. That rounding errors occur is an implementation detail of floating point arithmetic.
Identity #
The above code listing defines a value called Identity:
public readonly static Angle Identity = new Angle(0);
As an Angle, I want my Add and Identity members to obey the monoid laws so that I can be a monoid.
As an example, both left and right should be true in the following:
var x = Angle.FromDegrees(370); var left = x == Angle.Identity.Add(x); var right = x == x.Add(Angle.Identity);
That does, indeed, turn out to be the case.
Again, you can generalise using FsCheck:
[Property(QuietOnSuccess = true)] public void AddHasIdentity(Angle x) { Assert.Equal(x, Angle.Identity.Add(x)); Assert.Equal(x, x.Add(Angle.Identity)); }
Once more, a reservation identical to the one given above must be given when it comes to floating point arithmetic.
Conclusion #
The Add method is an associative, binary operation with identity; it's a monoid.
As far as I can tell, any modulo-based addition is a monoid, but while, say, modulo 37 addition probably doesn't have any practical application, modulo 360 addition does, because it's how you do angular addition.
Typing and testing problem 23
Yet another reflection on the relationship between types and tests, this time with a simple example.
The debate about dynamic typing versus static typing still goes on. If it ever gets resolved, I suppose it'll be in the far future. Until then, one's position is bound to be determined mostly by experience and belief. I openly admit that I prefer statically typed languages like F# and Haskell.
As I've previously touched on, I can't help seeing types as a slider. The more to the right you pull it, the stronger the type system. The more to the left you pull it, the more you'll need automated tests to give you a sense of confidence in your code.
In this article, I'll share an small revelation recently given to me.
Problem 23 #
Somewhere, a Stack Overflow user was going through Ninety-Nine Haskell Problems, and asked how to unit test problem 23.
The problem is elementary:
"Extract a given number of randomly selected elements from a list."Here's an example of the intended use:
λ> rndSelect "abcdefgh" 3 "fag"
The first argument to rndSelect is the candidates from which to pick elements; in this case the letters a to h. The second argument is the number of values to select; in this case the number 3.
Test plan #
How does one test a function like that? Clearly, when randomness is involved, you'll need some way to regulate the randomness in order to make tests deterministic. With my blinders on, I assumed that this was the main problem, so I answered with the following plan for a few properties:
- The length of the returned list should be equal to the input length.
- All elements in the returned list should be elements of the list of candidates.
In response to this plan, the user chi commented on my second suggestion:
"I think this it is a consequence of the free theorem. If so, no need to test for that!"Sometimes, I find it difficult to shake my object-oriented TDD-influenced way of thinking, but chi is right. Here's why:
Parametric polymorphism #
.NET, including C# and F#, has a platform feature called generics. Haskell has generics as well, although normally, that language feature is called parametric polymorphism. What I had in mind was a set of parametrically polymorphic functions with these types:
rndGenSelect :: (RandomGen g, Integral i) => g -> [a] -> i -> [a] rndSelect :: Integral i => [a] -> i -> IO [a]
Notice that both functions return lists of a values, where a is a type variable (in C#, you'd call it a generic type argument). It could be Integer, String, Day, or a custom domain type you'd added to the code base two minutes earlier.
Given a completely unrestricted type variable, Haskell has no way of creating values. How could it, logically?
In C#, you can write default(T), which tends to mostly produce null references. Haskell doesn't have null, so with that option cut off, how would it be able to produce values of arbitrary types? It can't.
When returning a list of a values, the only option open to a parametric polymorphic function is to pick values from its input arguments. For both rndGenSelect and rndSelect, there's only a single source of a values, so there's no reason to test that the functions return values from those lists of candidates. It's the only thing it can do. That's the free theorem for that function.
It'd been an entirely different story if the function had had concrete types. If, for example, the function had had the type RandomGen g => g -> String -> Int -> String, I could have written a function like this one:
rndGenSelect' :: RandomGen g => g -> String -> Int -> String rndGenSelect' _ _ count = replicate count 's'
Because the type of elements is known at compile-time, we can pick an arbitrary Char value ('s'). This is possible because we know the type, and therefore can come up with a strategy to hard-code known values of that type. When the type argument is unknown, this is no longer possible. To paraphrase Robert C. Martin, as the types get more generic, the tests become more redundant.
Taming randomness #
Before we look at automated testing, let's consider how to turn randomness into deterministic behaviour. This is (seemingly) always a problem with unit testing when the desired behaviour contains randomness, because tests should be deterministic. Once again, however, it turns out that functional design is intrinsically testable. Since Haskell design favours pure functions, the core of System.Random is deterministic.
This is, in fact, not much different from C#, where the Random class encapsulates an algorithm that computes a series of random-looking values based on an initial seed value. If you give it the same seed, it'll produce the same sequence of random-looking numbers. Haskell works the same way.
This led me to a design with a 'core' function that does all the work, and a 'wrapper' function that only adds one extra feature: randomness.
Starting my design with types, I wanted a function with this type:
rndGenSelect :: (RandomGen g, Integral i) => g -> [a] -> i -> [a]
This is the type that I've already discussed above. Because of the free theorem, we already know that the returned list can only contain values selected from the input list. In other words, there's no need to test for that.
This function takes a RandomGen argument, which is a type class of pure functions. RandomGen itself is pure; the source of randomness comes from how it's produced. More on that later. This, however, should enable me to write deterministic tests.
Properties #
Before we start adding deterministic tests, let's see how far we can get with property-based testing. First, designing with types, I need to implement the function so that it compiles. This is the simplest implementation I could think of:
rndGenSelect :: (RandomGen g, Integral i) => g -> [a] -> i -> [a] rndGenSelect _ xs _ = [head xs]
This implementation is both incorrect and unsafe, but it compiles. In TDD fashion, then, I found it appropriate to add a test - in this case a QuickCheck property:
lenProp :: Integral i => Int -> [a] -> NonNegative i -> Bool lenProp seed xs (NonNegative i) = i == genericLength (rndGenSelect (mkStdGen seed) xs i)
This little piece of test code is the only surviving property from my original test plan. It states that for any non-negative count, the list returned from rndGenSelect should have the requested length.
Writing this property, however, quickly forced me to deal with the case where the count is negative. It's easy to forget about edge cases when your function is nothing but a pie in the sky, but QuickCheck (and property-based testing in general) is really effective at grounding you in reality. Even with a language like Haskell, I still find the fast feedback loop from tests helpful.
The original exercise specification doesn't mention what should happen if the count is negative, so after short deliberation, I decide to write another property:
negLenProp :: Integral i => Int -> [a] -> Positive i -> Bool negLenProp seed xs (Positive i) = 0 == genericLength (rndGenSelect (mkStdGen seed) xs (-i))
This property simply states that for all negative counts, the returned list should be empty.
Both of these properties obviously fail, because of the incorrect implementation.
The simplest implementation I could think of that passes both properties is this:
rndGenSelect :: (RandomGen g, Integral i) => g -> [a] -> i -> [a] rndGenSelect _ xs count = genericReplicate count (head xs)
At this point, I don't see how TDD or property-based testing can help me move forward. The remaining work required is to add randomness to the mix. In this case, I'll need to use the RandomGen argument to produce random values, but since I don't know how its algorithm works, then even if I had a seed value known at compile-time, I wouldn't be able to predict which values it'd produce.
Selecting random indices #
I admit that I don't know how to write the next test a priori. I do know, however, that if I implement what's missing, I have a deterministic function, and I can use it to write regression test. In other words, I'll reverse direction and write the code first, and then the test. What a novel idea.
rndGenSelect :: (RandomGen g, Integral i) => g -> [a] -> i -> [a] rndGenSelect rnd xs count = let indices = genericTake count $ randomRs (0, length xs - 1) rnd in fmap (xs !!) indices
This function first uses randomRs to produce an infinite list of values. These values are indices because they all fall between 0 and length xs - 1. In other words, they are indices into xs.
While the list is infinite, it's lazily evaluated, so infinity itself isn't a problem. We only need count elements, though, so we can simply take the first count elements.
Finally, the function maps over the list of indices, and for each index value, selects the element at that position.
I could inline indices in the return expression, like this:
rndGenSelect :: (RandomGen g, Integral i) => g -> [a] -> i -> [a] rndGenSelect rnd xs count = fmap (xs !!) $ genericTake count $ randomRs (0, length xs - 1) rnd
I find that more obscure than the first alternative, though, but both versions pass the properties and do what they're supposed to do.
Regression testing #
How do I know that my code works? Well, that's always difficult with code that contains randomness, but you can load the function into GHCi and perform some sanity testing:
λ> rndGenSelect (mkStdGen 42) "foo" 3 "ofo" λ> rndGenSelect (mkStdGen 1337) "bar" 10 "rabbaarrra" λ> rndGenSelect (mkStdGen (-197221)) ['a'..'z'] 5 "ntfnc"
That looks, I suppose, random enough... What's more important is that this is completely repeatable. This means that I can write parametrised tests that protect against regressions:
"rndGenSelect of chars returns correct result" ~: do (seed, xs, count, expected) <- [ ( 42, "foo", 3, "ofo"), ( 1337, "bar", 10, "rabbaarrra"), (-197221, ['a'..'z'], 5, "ntfnc") ] let rnd = mkStdGen seed let actual = rndGenSelect rnd xs count return $ expected ~=? actual
These tests don't drive the design, but they prevent regressions. If, at a later time, I, or someone else, inadvertently revert rndGenSelect to genericReplicate count (head xs), these tests will fail.
Humble function #
The original problem statement is to write a function without an explicit RandomGen argument. In the spirit of xUnit Test Patterns' Humble Object pattern, we can now click all our pieces together to a function that does what is required:
rndSelect :: Integral i => [a] -> i -> IO [a] rndSelect xs count = do rnd <- newStdGen return $ rndGenSelect rnd xs count
The only thing of interest here is that the function is impure, because it uses newStdGen to produce a random RandomGen value. It then delegates all work to rndGenSelect, which is covered by tests.
As you can see, this function does not exhibit repeatable behaviour:
λ> rndSelect "abcdefgh" 3 "add" λ> rndSelect "abcdefgh" 3 "daf"
This should, I think, address the original problem statement.
All source code for this article is available on GitHub.
Summary #
The first time I encountered parametric polymorphism was when C# got generics in 2005. Back then it was mostly explained as a mechanism to avoid boxing, although it also seriously reduced the amount of boilerplate code you'd have to write in order to have type-safe collections. In many years, I mostly understood C# generics as a language feature aimed at efficiency and programmer productivity.
It wasn't until I started to program in F#, with its stronger type inference, that it began to dawn on me that parametric polymorphism could also be a design tool. Making a function more generic tightens its contract, so to speak. The more generic a function becomes, the less wriggle room does it have. This may sound like a disadvantage to a programmer, but it's a boon to a code reader. When you, as a reader, encounter a parametrically polymorphic function, you already know that there are things that function can't do. Such functions come with invariants, or 'theorems', for free.
Terse operators make business code more readable
Sometimes, terse operators can make code more readable. An article for all, even people who don't read Haskell code.
The Haskell programming language has a reputation for being terse to the point of being unreadable. That reputation isn't undeserved, but to counter, other languages exist that are verbose to the point of being unreadable.
Particularly, idiomatic Haskell code involves abstruse operators like ., $, <$>, >>=, <*>, <>, and so on. Not only do such operators look scary, but when I started writing Haskell code, it also bothered me that I didn't know how to pronounce these operators. I don't know how you read code, but my brain often tries to 'talk' about the code, silently, inside my head, and when it encounters something like =<<, it tends to stumble.
At least, it used to. These days, my brain has accepted that in many cases, Haskell operators are a little like punctuation marks. When I read a piece of prose, my brain doesn't insist on 'saying' comma, semicolon, question mark, period, etcetera. Such symbols assist reading, and often adjust the meaning of a text, but aren't to be read explicitly as themselves.
I'm beginning to realise that Haskell operators work like that; sometimes, they fade into the background and assist reading.
As a word of caution, don't take this analogy literally. Each Haskell operator means something specific, and they aren't interchangeable. Additionally, Haskell enables you to add your own custom operators, and I'm not sure that e.g. lens operators like .~ or %~ make code more readable.
A simple business code example #
Forgetting about the lens operators, though, consider a piece of business code like this:
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 }
Please read on, even if you don't read Haskell code. I'm not going to walk you through the details of how the operators work. That's not the point of this article. The point is how the operators enable you to focus on the overall picture of what's going on. The full source code is available on GitHub.
To establish a bit of context, this function determines whether or not to accept a restaurant reservation. Even if you've never read Haskell code before, see if you can get a sense of what's going on.
First, there's a guard which seems to involve whether or not the reservation is in the future. Second, there seems to be some calculations involving reservations, reserved seats, culminating in another guard. Third, the function seems to create a reservation by setting reservationIsAccepted to True.
Granted, it probably helps if you know that both = and <- bind the left-hand symbol to the expression on the right side. Additionally, after all this talk about special Haskell operators, it may not be immediately apparent that + is the perfectly normal addition operator, and <= is the well-known less-than-or-equal relational operator. What if we keep those operators, and mask the rest with a white rectangle symbol (▯)?
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 }
Finally, you also ought to know that while Haskell code is read from top to bottom, you tend to read each expression from right to left. Armed with this knowledge, and by masking the operators, the business logic begins to stand out.
First, it examines whether the reservation is in the future, and it does a guard of that. Again, I don't wish to make any claims that the code is magically self-documenting, because if you don't know what guard does, you don't know if this expression guards against the reservation being in the future, or if, conversely, it ensures that the reservation is in the future. It does the latter.
Second, it conjures up some reservations from somewhere, by first getting the reservationDate from reservation, and then passing that value to readReservations (expressions are read from right to left).
Moving on, it then calculates reservedSeats by starting with reservations, somehow extracting the reservationQuantity from those, and taking the sum. Since we've masked the operators, you can't tell exactly what's going on, but the gist is, hopefully, clear.
The middle block of code concludes with another guard, this time ensuring that the reservedSeats plus the reservationQuantity is less than or equal to the capacity.
Finally, the function sets reservationIsAccepted to True and calls create.
What I find compelling about this is that the terseness of the Haskell operators enables you, a code reader, to scan the code to first understand the big picture.
Guards #
Additionally, some common motifs begin to stand out. For example, there are two guard expressions. Because the operators are terse, the similarities stand out better. Let's juxtapose them:
guard ▯ isReservationInFuture reservation guard ▯ reservedSeats + reservationQuantity reservation <= capacity
It seems clear that the same sort of thing is going on in both cases. There's a guard ensuring that a Boolean condition is satisfied. If you, however, reconsider the actual code, you'll see that the white rectangle hides two different operators:
guard =<< isReservationInFuture reservation guard $ reservedSeats + reservationQuantity reservation <= capacity
The reason for this is that it has to, because otherwise it wouldn't compile. isReservationInFuture reservation has the type MaybeT ReservationsProgram Bool. There's a Boolean value hidden in there, but it's buried inside a container. Using =<< enables you to pull out the Boolean value and pass it to guard.
In the second guard expression, reservedSeats + reservationQuantity reservation <= capacity is a 'naked' Boolean expression, so in this case you can use the $ operator to pass it to guard.
Haskellers may wonder why I chose =<< instead of the more common >>= operator in the first of the two guard expressions. I could have, but then the expression would have been this:
isReservationInFuture reservation >>= guard
The resulting behaviour is the same, but I think this obscures how the two guard expressions are variations on the same motif.
The use of operators enables you to express code in such a way that motifs stand out. In contrast, I tried writing the same business functionality in F#, but it didn't come out as readable (in my opinion):
// 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 } }
While you can also define custom operators in F#, it's rarely a good idea, for various reasons that, at its core, are related to how F# isn't Haskell. The lack of 'glue' operators in F#, though, obliged me to instead use the more verbose ReservationsOption.bind. This adds noise to the degree that the guard function disappears in the middle of the expression. The motif is fainter.
Piping #
Another motif in Haskell code is piping. This is known from F# as well, where piping is normally done from left to right using the |> operator. You can, as the above example shows, also use the right-to-left pipe operator <|. In Haskell, expressions are idiomatically composed from right to left, often with the $ operator, or, when using point-free style, with the . operator.
Once you realise that expressions compose from right to left, a masked expression like sum ▯ reservationQuantity ▯ reservations begins to look like a pipeline: start with reservations, somehow pipe them to reservationQuantity, and finally pipe the result of doing that to sum. That's actually not quite what happens, but I think that this compellingly communicates the overall idea: start with some reservations, consider their quantities, and calculate the sum of those.
Another way to write that expression would be:
let reservedSeats = sum (fmap reservationQuantity reservations)
This implements the same behaviour as sum $ reservationQuantity <$> reservations, but once you get used to it, I like the operator-based alternative better. The operators fade into the background, enabling the flow of data to stand out better.
Conclusion #
Haskell operators constitute the glue that enables you to compose expressions together. Often, you need to vary how expressions are composed together, because the types are slightly different. Picking an appropriate operator that composes particular expressions enables you to perform the composition with a high signal-to-noise ratio.
Once you get used to reading Haskell code, the operators can fade into the background in well-factored code, just like punctuation marks assist you when you read prose. As always, this is no silver bullet. I've seen plenty of examples of obscure Haskell code as well, and copious use of operators is a fast way to obfuscate code.
Use; punctuation? marks with. taste!
Visitor as a sum type
The Visitor design pattern is isomorphic to sum types.
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 Visitor design pattern is equivalent to a sum type.
Sum types #
I think that the most important advantage of a statically typed programming language is that it gives you immediate feedback on your design and implementation work. Granted, that your code compiles may not be enough to instil confidence that you've done the right thing, but it's obvious that when your code doesn't compile, you still have work to do.
A static type system enables you to catch some programming errors at compile time. It prevents you from making obvious mistakes like trying to divide a GUID by a date. Some type systems don't offer much more help than that, while others are more articulate; I think that type systems inhabit a continuous spectrum of capabilities, although that, too, is a simplification.
An often-touted advantage of programming languages like F#, OCaml, and Haskell is that they, in the words of Yaron Minsky, enable you to make illegal states unrepresentable. The way these languages differ from languages like C# and Java is that they have algebraic data types.
In short, algebraic data types distinguish between product types and sum types. All statically typed language I've seen have product types, which you can think of as combinations of data. Objects with more than a single class fields would be product types.
Sum types (also known as discriminated unions), on the other hand, are types that express mutually exclusive alternatives. Object-oriented programmers might mistake such a statement for sub-classing, but the difference is that object-oriented sub-classing creates a potentially infinite hierarchy of subtypes, while a sum type is statically constrained to a finite number of mutually exclusive cases. This is often useful.
In this article, you'll see that a sum type is isomorphic to a corresponding Visitor.
Church-encoded payment types #
In a previous article, you saw how to Church-encode a domain-specific sum type. That article, again, demonstrated how to rewrite a domain-specific F# discriminated union as a C# API. The F# type was this PaymentType sum type:
type PaymentType = | Individual of PaymentService | Parent of PaymentService | Child of originalTransactionKey : string * paymentService : PaymentService
Using Church-encoding in C#, you can arrive at this interface that models the same business problem:
public interface IPaymentType { T Match<T>( Func<PaymentService, T> individual, Func<PaymentService, T> parent, Func<ChildPaymentService, T> child); }
In order to use the API, the compiler obligates you to handle all three mutually exclusive cases defined by the three arguments to the Match method. Refer to the previous article for more details and code examples. All the C# code is also available on GitHub.
While the C# code works, I think it'd be a fair criticism to say that it doesn't feel object-oriented. Particularly the use of function delegates (Func<PaymentService, T>, etcetera) seems off. These days, C# is a multi-paradigmatic language, and function delegates have been around since 2007, so it's a perfectly fine C# design. Still, if we're trying to understand how object-oriented programming relates to fundamental programming abstractions, it behoves us to consider a more classic form of object-orientation.
Introduce Parameter Object #
Through a series of refactorings you can transform the Church-encoded IPaymentType interface to a Visitor. The first step is to use Refactoring's Introduce Parameter Object to turn the three method arguments of Match into a single object:
public class PaymentTypeParameters<T> { public PaymentTypeParameters( Func<PaymentService, T> individual, Func<PaymentService, T> parent, Func<ChildPaymentService, T> child) { Individual = individual; Parent = parent; Child = child; } public Func<PaymentService, T> Individual { get; } public Func<PaymentService, T> Parent { get; } public Func<ChildPaymentService, T> Child { get; } }
The modified IPaymentType interface then looks like this:
public interface IPaymentType { T Match<T>(PaymentTypeParameters<T> parameters); }
Clearly, this change means that you must also adjust each implementation of IPaymentType accordingly. Here's the Match method of Individual:
public T Match<T>(PaymentTypeParameters<T> parameters) { return parameters.Individual(paymentService); }
The two other implementations (Parent and Child) change in the same way; the modifications are trivial, so I'm not going to show them here, but all the code is available as a single commit.
Likewise, client code that uses the API needs adjustment, like the ToJson method:
public static PaymentJsonModel ToJson(this IPaymentType payment) { return payment.Match( new PaymentTypeParameters<PaymentJsonModel>( individual : ps => new PaymentJsonModel { Name = ps.Name, Action = ps.Action, StartRecurrent = new ChurchFalse(), TransactionKey = new Nothing<string>() }, parent : ps => new PaymentJsonModel { Name = ps.Name, Action = ps.Action, StartRecurrent = new ChurchTrue(), TransactionKey = new Nothing<string>() }, child : cps => new PaymentJsonModel { Name = cps.PaymentService.Name, Action = cps.PaymentService.Action, StartRecurrent = new ChurchFalse(), TransactionKey = new Just<string>(cps.OriginalTransactionKey) })); }
From argument list isomorphisms we know that an argument list is isomorphic to a Parameter Object, so this step should come as no surprise. We also know that the reverse translation (from Parameter Object to argument list) is possible.
Add Run prefix #
I think it looks a little strange that the functions comprising PaymentTypeParameters<T> are named Individual, Parent, and Child. Functions do something, so they ought to be named with verbs. This turns out only to be an intermediary step, but I'll add the prefix Run to all three:
public class PaymentTypeParameters<T> { public PaymentTypeParameters( Func<PaymentService, T> individual, Func<PaymentService, T> parent, Func<ChildPaymentService, T> child) { RunIndividual = individual; RunParent = parent; RunChild = child; } public Func<PaymentService, T> RunIndividual { get; } public Func<PaymentService, T> RunParent { get; } public Func<ChildPaymentService, T> RunChild { get; } }
This doesn't change the structure of the code in any way, but sets it up for the next step.
Refactor to interface #
The definition of PaymentTypeParameters<T> still doesn't look object-oriented. While it's formally an object, it's an object that composes three function delegates. We've managed to move the function delegates around, but we haven't managed to get rid of them. From object isomorphisms, however, we know that tuples of functions are isomorphic to objects, and that's essentially what we have here. In this particular case, there's no implementation code in PaymentTypeParameters<T> itself - it's nothing but a group of three functions. You can refactor that class to an interface:
public interface IPaymentTypeParameters<T> { T RunIndividual(PaymentService individual); T RunParent(PaymentService parent); T RunChild(ChildPaymentService child); }
The implementations of Individual, Parent, and Child don't change; only the signature of Match changes slightly:
public interface IPaymentType { T Match<T>(IPaymentTypeParameters<T> parameters); }
Since this change removes the function delegates, it requires client code to change:
public static PaymentJsonModel ToJson(this IPaymentType payment) { return payment.Match(new PaymentTypeToJsonParameters()); } private class PaymentTypeToJsonParameters : IPaymentTypeParameters<PaymentJsonModel> { public PaymentJsonModel RunIndividual(PaymentService individual) { return new PaymentJsonModel { Name = individual.Name, Action = individual.Action, StartRecurrent = new ChurchFalse(), TransactionKey = new Nothing<string>() }; } public PaymentJsonModel RunParent(PaymentService parent) { return new PaymentJsonModel { Name = parent.Name, Action = parent.Action, StartRecurrent = new ChurchTrue(), TransactionKey = new Nothing<string>() }; } public PaymentJsonModel RunChild(ChildPaymentService child) { return new PaymentJsonModel { Name = child.PaymentService.Name, Action = child.PaymentService.Action, StartRecurrent = new ChurchFalse(), TransactionKey = new Just<string>(child.OriginalTransactionKey) }; } }
The ToJson method now has to delegate to a private class that implements IPaymentTypeParameters<PaymentJsonModel>. In Java and F# you'd be able to pass an object expression, but in C# you have to create an explicit class for the purpose. The implementations of the three methods of the interface still correspond to the three functions the previous incarnations of the code used.
Rename to Visitor #
At this point, the Visitor pattern's structure is already in place. The only remaining step is to rename the various parts of the API so that this becomes clear. You can start by renaming the IPaymentTypeParameters<T> interface to IPaymentTypeVisitor<T>:
public interface IPaymentTypeVisitor<T> { T VisitIndividual(PaymentService individual); T VisitParent(PaymentService parent); T VisitChild(ChildPaymentService child); }
Notice that I've also renamed the methods from RunIndividual, RunParent, and RunChild to VisitIndividual, VisitParent, and VisitChild.
Likewise, you can rename the Match method to Accept:
public interface IPaymentType { T Accept<T>(IPaymentTypeVisitor<T> visitor); }
In Design Patterns, the Visitor design pattern is only described in such a way that both Accept and Visit methods have void return types, but from unit isomorphisms we know that this is equivalent to returning unit. Thus, setting T in the above API to a suitable unit type (like the one defined in F#), you arrive at the canonical Visitor pattern. The generic version here is simply a generalisation.
For the sake of completeness, client code now looks like this:
public static PaymentJsonModel ToJson(this IPaymentType payment) { return payment.Accept(new PaymentTypeToJsonVisitor()); } private class PaymentTypeToJsonVisitor : IPaymentTypeVisitor<PaymentJsonModel> { public PaymentJsonModel VisitIndividual(PaymentService individual) { return new PaymentJsonModel { Name = individual.Name, Action = individual.Action, StartRecurrent = new ChurchFalse(), TransactionKey = new Nothing<string>() }; } public PaymentJsonModel VisitParent(PaymentService parent) { return new PaymentJsonModel { Name = parent.Name, Action = parent.Action, StartRecurrent = new ChurchTrue(), TransactionKey = new Nothing<string>() }; } public PaymentJsonModel VisitChild(ChildPaymentService child) { return new PaymentJsonModel { Name = child.PaymentService.Name, Action = child.PaymentService.Action, StartRecurrent = new ChurchFalse(), TransactionKey = new Just<string>(child.OriginalTransactionKey) }; } }
You can refactor all the other Church encoding examples I've shown you to Visitor implementations. It doesn't always make the code more readable, but it's possible.
From Visitor to sum types #
In this article, I've shown how to refactor from a Church-encoded sum type to a Visitor, using the following refactoring steps:
- Introduce Parameter Object
- (Rename Method (by adding a
Runprefix)) - Refactor to interface
- Rename to Visitor terminology
- Refactor the Visitor interface to a Parameter Object that composes functions
- Refactor the Parameter Object to an argument list
- Rename types and members as desired
Summary #
Algebraic data types enable you to make illegal states unrepresentable. Most programming languages have product types, so it's the lack of sum types that seems to make the difference between languages like C# and Java on the one side, and languages like F#, OCaml, or Haskell on the other side.
You can, however, achieve the same objective with object-oriented design. The Visitor design pattern is equivalent to sum types, so everything you can express with a sum type in, say, F#, you can express with a Visitor in C#.
That's not to say that these two representations are equal in readability or maintainability. F# and Haskell sum types are declarative types that usually only take up a few lines of code. Visitor, on the other hand, is a small object hierarchy; it's a more verbose way to express the idea that a type is defined by mutually exclusive and heterogeneous cases. I know which of these alternatives I prefer, but if I were caught in an object-oriented code base, it's nice to know that it's still possible to model a domain with algebraic data types.
Comments
I think that it's important to remember the type of abstractions you highlight by showing that the Vistor design pattern is the same as sum types. I appreciate this post.
When I read up on Entity component system, I found it interesting how the pattern arrived from the need to be able to control memory. Perhaps the somewhat odd form of the Visitor pattern has arrived from the same limitations in some common languages? Perhaps there are other constructs that can be expressed more clearly using more modern patterns?
Oskar, thank you for writing. I didn't know about entity component system.
This very article series tries to identify various design patterns and how they relate to more fundamental constructs. Most likely you're already aware of that, so perhaps you meant something else by your questions. If you did, however, I can't glean what.
I was not aware of that article series. The answer I'm looking for seems to be the identified subset.
Church-encoded payment types
How to translate a domain-specific sum type into a Church-encoded C# API. An article for object-oriented developers.
This article is part of a series of articles about Church encoding. In the previous articles, you've seen how to implement Boolean logic without Boolean primitives, as well as how to model natural numbers, how to implement a Maybe container, and how to implement an Either container. Common to all four examples is that they're based on sum types with exactly two mutually exclusive cases.
You may already have noticed that all three translate to Match methods that take two arguments. The translation is so mechanical that you could automate it. Each case in a sum type becomes an argument in a Match method. In this article, you'll see an example of a domain-specific sum type with three cases, translated to Church-encoding.
A payment type model in F# #
In a previous article I described a particular business problem that was elegantly addressed with a discriminated union (sum type) in F#:
type PaymentService = { Name : string; Action : string } type PaymentType = | Individual of PaymentService | Parent of PaymentService | Child of originalTransactionKey : string * paymentService : PaymentService
In short, this model enables you to model various payments against a third-party payment service. An individual payment is, as the name implies, a single payment. A parent payment can be used to authorise a series of recurring, automated payments, for example to pay for a subscription. A child payment is one of those recurring payments; it must have a parent payment to authorise it, as automation means that no user interaction takes place.
One task that is easily addressed with the above PaymentType discriminated union is that you can translate the data to JSON in a type-safe manner. The compiler will tell you whether or not you've handled all three cases.
Auxiliary C# classes #
You can Church-encode PaymentType just like Boolean values, natural numbers, Maybe, and Either. Before you do that, however, you need to define the input types involved in each case. These are normal classes, although I prefer to make them immutable:
public class PaymentService { public PaymentService(string name, string action) { this.Name = name; this.Action = action; } public string Name { get; } public string Action { get; } } public class ChildPaymentService { public ChildPaymentService( string originalTransactionKey, PaymentService paymentService) { this.OriginalTransactionKey = originalTransactionKey; this.PaymentService = paymentService; } public string OriginalTransactionKey { get; } public PaymentService PaymentService { get; } }
These are straightforward translations of the F# PaymentService record type, and the tuple associated with the Child case. In a real code base, I'd override Equals for both classes in order to turn them into proper Value Objects, but in order to keep the size of the code down, I omitted doing that here.
Church-encoded payment type #
You can now translate the PaymentType F# discriminated union to a Church-encoded API in C#, starting with the interface:
public interface IPaymentType { T Match<T>( Func<PaymentService, T> individual, Func<PaymentService, T> parent, Func<ChildPaymentService, T> child); }
Since there's three cases in the sum type, that turns into a Match method with three arguments, each corresponding to one of the cases. As was also the case for the previous articles' INaturalNumber, IMaybe<T>, and IEither<L, R> interfaces, the data associated with each case is modelled as a function from the data to the generic return type T.
Again, following the recipe implied by the previous examples, you should now add a concrete implementation of the IPaymentType interface for each case. It's natural to start with the first argument to the Match method, individual:
public class Individual : IPaymentType { private readonly PaymentService paymentService; public Individual(PaymentService paymentService) { this.paymentService = paymentService; } public T Match<T>( Func<PaymentService, T> individual, Func<PaymentService, T> parent, Func<ChildPaymentService, T> child) { return individual(paymentService); } }
The Individual class adapts a PaymentService value, which it passes as the argument to the individual function argument when Match is called. As you've seen in the previous articles, a particular implementation uses only one of the method arguments, so the two other arguments, parent and child, are simply ignored.
The parent implementation is almost identical:
public class Parent : IPaymentType { private readonly PaymentService paymentService; public Parent(PaymentService paymentService) { this.paymentService = paymentService; } public T Match<T>( Func<PaymentService, T> individual, Func<PaymentService, T> parent, Func<ChildPaymentService, T> child) { return parent(paymentService); } }
The Parent class also adapts a PaymentService value that it passes to a function when Match is called. The only difference is that it calls the parent function instead of the individual function argument.
The third case is handled by the following Child class:
public class Child : IPaymentType { private readonly ChildPaymentService childPaymentService; public Child(ChildPaymentService childPaymentService) { this.childPaymentService = childPaymentService; } public T Match<T>( Func<PaymentService, T> individual, Func<PaymentService, T> parent, Func<ChildPaymentService, T> child) { return child(childPaymentService); } }
While the two other classes both adapt a PaymentService value, a Child object instead composes a ChildPaymentService value. When Match is called, it calls the child function argument with the composed value.
Using the IPaymentType API #
One important feature that I originally had to implement was to translate a payment type value into a JSON document. For the purposes of this example, imagine that you can model the desired JSON document using this Data Transfer Object:
public class PaymentJsonModel { public string Name { get; set; } public string Action { get; set; } public IChurchBoolean StartRecurrent { get; set; } public IMaybe<string> TransactionKey { get; set; } }
This is a mutable object because most .NET serialisation APIs require that the class in question has a parameterless constructor and writeable properties. Notice, however, that in order to demonstrate that all this code still doesn't rely on any primitive Boolean operators and such, the class' properties are defined as IChurchBoolean and IMaybe<string> values, as well as regular string values.
Writing a method that translates any IPaymentType object into a PaymentJsonModel object is now straightforward:
public static PaymentJsonModel ToJson(this IPaymentType payment) { return payment.Match( individual : ps => new PaymentJsonModel { Name = ps.Name, Action = ps.Action, StartRecurrent = new ChurchFalse(), TransactionKey = new Nothing<string>() }, parent : ps => new PaymentJsonModel { Name = ps.Name, Action = ps.Action, StartRecurrent = new ChurchTrue(), TransactionKey = new Nothing<string>() }, child : cps => new PaymentJsonModel { Name = cps.PaymentService.Name, Action = cps.PaymentService.Action, StartRecurrent = new ChurchFalse(), TransactionKey = new Just<string>(cps.OriginalTransactionKey) }); }
Because the Match method takes three arguments, you have to supply a 'handler' function for each of them, and they all have to have the same return type. In this case they all return a new PaymentJsonModel object, so that requirement is fulfilled. All three lambda expressions simply copy over Name and Action, but they differ in the values they assign to StartRecurrent and TransactionKey.
Tests #
In order to show you that it all works, here's a few examples I wrote as xUnit.net tests:
[Fact] public void IndividualToJsonReturnsCorrectResult() { var sut = new Individual(new PaymentService("MasterCard", "Pay")); var actual = sut.ToJson(); Assert.Equal("MasterCard", actual.Name); Assert.Equal("Pay", actual.Action); Assert.False(actual.StartRecurrent.ToBool()); Assert.True(actual.TransactionKey.IsNothing().ToBool()); } [Fact] public void ParentToJsonReturnsCorrectResult() { var sut = new Parent(new PaymentService("MasterCard", "Pay")); var actual = sut.ToJson(); Assert.Equal("MasterCard", actual.Name); Assert.Equal("Pay", actual.Action); Assert.True(actual.StartRecurrent.ToBool()); Assert.True(actual.TransactionKey.IsNothing().ToBool()); } [Fact] public void ChildToJsonReturnsCorrectResult() { var sut = new Child( new ChildPaymentService( "12345", new PaymentService("MasterCard", "Pay"))); var actual = sut.ToJson(); Assert.Equal("MasterCard", actual.Name); Assert.Equal("Pay", actual.Action); Assert.False(actual.StartRecurrent.ToBool()); Assert.Equal("12345", actual.TransactionKey.Match("", x => x)); }
All three tests pass.
Summary #
The major advantage of sum types in statically typed languages is that you can make illegal states unrepresentable (a maxim attributed to Yaron Minsky). Specifically, in the business example of payment types shown here, I need to be able to express that only three out of four combinations of start recurrent and original transaction key is legal. Specifically, I needed to express that the combination of start recurrent = true and the presence of a transaction key is illegal. Making such an illegal state unrepresentable is easy with a sum type, but as this article has shown, you can achieve the same goal in C#.
With the API shown here, there's only three possible states (Individual, Child, and Parent). Notice that all three classes hide their data as private class fields, so the only way to extract that data is to call Match. The compiler will make sure that you handle all three cases, because you must supply a function for all three method arguments.
The code shown in this article is available on GitHub.
This article concludes the little series on how to use Church-encoding in C# to create sum types. You may, however, think that it doesn't really feel object-oriented, with its heavy reliance on function arguments (e.g. Func<PaymentService, T>). It turns out, though, that with only a few refactorings, you'll come to the realisation that what you've seen here is isomorphic to a classic design pattern. Read on!
Next: Church-encoded rose tree.
Church-encoded Either
Programming languages don't have to have a built-in notion of error handling. You can implement sane error handling from first principles. An introduction for object-oriented programmers.
This article is part of a series of articles about Church encoding. In this series, you'll learn how to re-create various programming language features from first principles. In previous articles, you learned how to implement Boolean logic without Boolean primitives, how to model natural numbers, as well as how to implement Maybe (a type-safe alternative to null). Through these examples, you'll learn how to model sum types without explicit language support.
Error handling without exceptions #
In a previous article, I've discussed how a language doesn't need to have built-in exceptions in order to support composable and type-safe error handling. In fact, exceptions are noting but glorified GOTO statements. A better approach is to use the Either abstraction, which enables you to model values that are either one or another thing.
In F#, this type is known as Result<'T, 'TError>, while in Haskell it's called Either. It enables you to model an outcome that is either something (like a success) or something else (such as an error).
Scott Wlaschin has already brilliantly described how this works in F#, but the Either type can be used for error handling in Haskell in exactly the same way. When we use the terminology related to either, we distinguish between left and right. Typically, right is used to indicate success, via the pun that 'right' is 'correct'.
Lambda calculus Either #
Church encoding is based on the lambda calculus, which defines a universal model of computation based entirely on functions (lambda expressions) and recursion. As far as I can tell, you can define Either in lambda calculus as an expression that takes two arguments, and where there's two fundamental 'implementations' of the contract:
left = λa.λl.λr.l a right = λb.λl.λr.r b
(I admit that I'm going out on a limb here, since I haven't found any source that puts either in the above form, so I'd appreciate feedback if I did it incorrectly.)
The contract is that, similar to Maybe, the l function argument represents the left case, whereas the r argument represents the right case. Contrary to Maybe, both l and r are used as functions. (Everything in lambda calculus is a function, but we don't always use the arguments as the function that they are.)
The left function is a function that takes three arguments (a, l, and r) and always returns l a. Recall that in lambda calculus, everything is a function, which includes l (and r). In other words, left unconditionally calls l with a, and that's the return value.
The right function works like the left function, with the only difference that it always returns r b.
The idea, as usual, is that you can partially apply left and right, by, for instance calling left three (where three is the lambda calculus representation of the number 3, as described in the article on Church-encoded natural numbers). Such a partially applied function is a function that still takes the two arguments l and r.
The same is true if you partially apply right with a value, like right one.
In both cases, you have a function of the form λl.λr.[...]. If you've been given such a function by an external source, you may not know if it's a left or a right expression, and that's the point. You must supply handlers (l and r) that cover all possible cases.
In the lambda calculus, expressions are always curried, so instead of viewing left and right as functions with three arguments, you can view them as functions that take a single element (a or b) and return functions that takes two arguments. This agrees with Haskell's Left and Right data constructors:
Prelude> :t Left Left :: a -> Either a b Prelude> :t Right Right :: b -> Either a b
Haskell tells us that Left is a function that takes an a value and returns an Either a b value. Similarly, Right is a function that takes a b value as input, and returns an Either a b
Church-encoded Either in C# #
Both lambda calculus and Haskell relies on currying and partial application to make the contract fit. In C#, as you've previously seen, you can instead define an interface and rely on class fields for the 'extra' function arguments. Since Church-encoded Either is represented by a function that takes two arguments, we'll once again define an interface with a single method that takes two arguments:
public interface IEither<L, R> { T Match<T>(Func<L, T> onLeft, Func<R, T> onRight); }
The Match method takes two functions as arguments, one that handles the left case, and one that handles the right case. They correspond to the l and r variables in the above lambda expressions. The intent, as with other Church-encoded discriminated unions, is that when client code is given an IEither<L, R> object, it can only interact with that object by telling the Match method how to deal with both cases. Only one of the functions will be called, but at compile-time, you don't know which one. Both functions, however, must return a value of the generic type T, and that's how you can translate an IEither<L, R> object to a T value.
Following the normal procedure for Church encoding, you must also supply two implementations of the IEither<L, R> interface: one for each case.
public class Left<L, R> : IEither<L, R> { private readonly L left; public Left(L left) { this.left = left; } public T Match<T>(Func<L, T> onLeft, Func<R, T> onRight) { return onLeft(left); } }
The Left<L, R> class is an Adapter of a value of the generic type L , making it appear as an IEither<L, R> object.
It always calls the onLeft method argument with the adapted value left, while it ignores the onRight method argument. Since onLeft returns a T value, you can return the value produced by the function call.
The right case is implemented in a similar fashion:
public class Right<L, R> : IEither<L, R> { private readonly R right; public Right(R right) { this.right = right; } public T Match<T>(Func<L, T> onLeft, Func<R, T> onRight) { return onRight(right); } }
The Right<L, R> class is the mirror image of Left<L, R>. Instead of adapting an L value, it adapts an R value. It implements Match by always calling onRight with the right value, which, again, produces a T value that can be immediately returned.
Notice that for both implementations, the adapted values left and right are private class fields not exposed as public members. The only way you, as a caller, can potentially extract these values is by calling Match, and that forces you to explicitly deal with both cases.
Here's an example of using the API:
> IEither<string, int> e = new Right<string, int>(42); > e.Match(s => s.Length % 2 == 0, i => i % 2 == 0) true
I've deliberately declared e as a an IEither<string, int> in order to highlight the scenario where, as a client developer, you're often given a value of such a type, and you don't know if it's a left or a right value. Had I, instead, used the var keyword, the compiler would have detected that e is, really, a Right<string, int> variable. You may consider this choice artificial, but the point I'm trying to get across is that, when writing client code, you're often given a polymorphic value, and you don't know the concrete type of the value. According to the Liskov Substitution Principle, your client code must be able to deal with any subtype without changing the correctness of the system. In the case of an Either value, the way you deal with all subtypes is by supplying handlers for both cases to the Match method.
In the above example, the return value is true because 42 is an even number. If, instead, the e object is a left case containing the string "foo", the return value is false because the length of "foo" is 3 - an odd number:
> IEither<string, int> e = new Left<string, int>("foo"); > e.Match(s => s.Length % 2 == 0, i => i % 2 == 0) false
Notice that the e.Match method call is the same in both examples; the onLeft and onRight functions are the same in both cases. The results differ because the input values represent different cases.
If you've been following the overall series on Church encoding, you may think that it's cheating to use C#'s built-in string and int data types, but nothing prevents us from sticking to the data types we've built from scratch:
> IEither<IChurchBoolean, INaturalNumber> e; > e = new Right<IChurchBoolean, INaturalNumber>(NaturalNumber.Seven); > e.Match(b => new ChurchNot(b), n => n.IsEven()) ChurchFalse { } > e = new Left<IChurchBoolean, INaturalNumber>(new ChurchFalse()); > e.Match(b => new ChurchNot(b), n => n.IsEven()) ChurchNot(ChurchFalse)
For both the left and the right case, the Match inverts the Boolean expression if it's a left case, and evaluates if the number is even if it's a right case. In the first example, the return value is a ChurchFalse object because 7 is odd. In the second example, the return value is a ChurchNot object containing a ChurchFalse object (in other words, true), because the negation of false is true.
Either instead of exceptions #
You can use Either to signal the success or failure of an operation. By convention, the right case is used to signal success, so, by elimination, left means failure. You can signal errors in numerous ways, e.g. by using enum values, but another common strategy is to simply use string values.
Consider the following example. You receive a collection of values, where each element represents a vote for that element. For example, the list Sandra, Zoey, Sandra indicates two votes for Sandra, and one for Zoey. You need to write a method that returns the winner of a vote, but at least two distinct errors are possible: the input collection is empty, or there's a tie.
You can model the error cases with an enum:
public enum VoteError { Empty = 0, Tie }
This enables you to write a method to find the winners, with an explicit Either return type:
public static IEither<VoteError, T> FindWinner<T>(IReadOnlyCollection<T> votes) { var countedVotes = from v in votes group v by v into g let count = g.Count() orderby count descending select new { Vote = g.Key, Count = count }; var c = countedVotes.Take(2).Count(); if (c == 0) return new Left<VoteError, T>(VoteError.Empty); var x0 = countedVotes.ElementAt(0); if (c == 1) return new Right<VoteError, T>(x0.Vote); var x1 = countedVotes.ElementAt(1); if (Equals(x0.Count, x1.Count)) return new Left<VoteError, T>(VoteError.Tie); return new Right<VoteError, T>(x0.Vote); }
Notice that the return type of the FindWinner method is IEither<VoteError, T>; either you get a VoteError value, or you get a T value, but any client code doesn't know which it'll be, so it must handle both cases.
The method uses a C# query expression to group, count, and order the votes. If there's no elements, the return value is a left value containing VoteError.Empty. If there's only a single vote group (e.g. if the votes where all for Sandra), that value is returned in a right case. Otherwise, if the two highest ranked votes have the same count, a left value is returned containing VoteError.Tie. Finally, in all other cases, the highest voted element is returned in a right case.
Here's some examples in C# Interactive:
> FindWinner<int>() Left<VoteError, int>(Empty) > FindWinner(1, 2, 3, 1, 4, 2) Left<VoteError, int>(Tie) > FindWinner("Sandra", "Zoey", "Sandra") Right<VoteError, string>("Sandra")
Instead of throwing two different types of exceptions on invalid input, the FindWinner method handles invalid input as left cases, and valid input as the right case. You can do that consistently, and thereby eliminate the need for exceptions. Errors are, instead, reported as left values.
Summary #
In this article, you saw how it's possible to define the Either container from first principles, using nothing but functions (and, for the C# examples, interfaces and classes in order to make the code easier to understand for object-oriented developers).
The code shown in this article is available on GitHub.
Like Maybe, you can also make Either a functor. This'll enable you to compose various error-producing functions in a sane manner.
Church-encoding enables you to model sum types as functions. So far in this article series, you've seen how to model Boolean values, natural numbers, Maybe, and Either. Common to all four examples is that the data type in question consists of two mutually exclusive cases. This is the reason they're all modelled as methods that take two arguments. What happens if, instead of two, you have three mutually exclusive cases? Read on.
Next: Church-encoded payment types.
Comments
All sources in which I've come accross Either seem to describe it as you did, having two type parameters: left and right.
But since it is simply a discriminated/tagged union, why are Eithers limited to two parameters?
Say, in F#, it would make perfect sense to have a discriminated union called PaymentType = CreditCard | DebitCard | Cash.
Is there any convention in place that suggests against having something like that, but instead using
public sealed class PaymentType : IEither<CreditCard, DebitCard, Cash> ?
Yes, you could theoretically nest Eithers and get the same result, but that would be awkward both in definition and usage in C# or other languages that don't define such constructs naturally.
public sealed class PaymentType : IEither<CreditCard, IEither<DebitCard, Cash>>
Ciprian, thank you for writing. Either is a particular discriminated union; by definition it has two type parameters. In F# it's called Result<'T,'TError> and defined as:
type Result<'T,'TError> = | Ok of ResultValue:'T | Error of ErrorValue:'TError
Notice that in this defintion, the 'right' result is to the left, and the error is to the right, which is opposite of the way of the either convention.
If you need another type with three mutually exclusive cases, then Either is a poor fit for that (although one can nest them, as you suggest). You can, however, still Church-encode such a type. The next article in this article series contains an example of a Church-encoding of a discriminated union with three, instead of two, cases. By coincidence, this type is also called payment type. The cases are, however, not the same as those you suggest, since it models a different scenario.
The IEither<L, R> interface shown in this article is not meant to be implemented by any other classes than Left and Right. The only reason these types are public is because this article shows you how the sausage is made, so to speak. If one ever were to put such a type into a reusable library, I think an alternative implementation like the following would be more appropriate:
public sealed class Either<L, R> { private readonly IEither imp; private Either(IEither imp) { this.imp = imp; } internal static Either<L, R> CreateLeft(L value) { return new Either<L, R>(new Left(value)); } internal static Either<L, R> CreateRight(R value) { return new Either<L, R>(new Right(value)); } public T Match<T>(Func<L, T> onLeft, Func<R, T> onRight) { return imp.Match(onLeft, onRight); } public override bool Equals(object obj) { if (!(obj is Either<L, R> other)) return false; return Equals(imp, other.imp); } public override int GetHashCode() { return imp.GetHashCode(); } private interface IEither { T Match<T>(Func<L, T> onLeft, Func<R, T> onRight); } private sealed class Left : IEither { private readonly L left; public Left(L left) { this.left = left; } public T Match<T>(Func<L, T> onLeft, Func<R, T> onRight) { return onLeft(left); } public override bool Equals(object obj) { if (!(obj is Left other)) return false; return Equals(left, other.left); } public override int GetHashCode() { return left.GetHashCode(); } } private sealed class Right : IEither { private readonly R right; public Right(R right) { this.right = right; } public T Match<T>(Func<L, T> onLeft, Func<R, T> onRight) { return onRight(right); } public override bool Equals(object obj) { if (!(obj is Right other)) return false; return Equals(right, other.right); } public override int GetHashCode() { return right.GetHashCode(); } } }
Apart from the object type itself, you're also going to need some static methods:
public static Either<L, R> Left<L, R>(L value) { return Either<L, R>.CreateLeft(value); } public static Either<L, R> Right<L, R>(R value) { return Either<L, R>.CreateRight(value); }
Additional extension methods like the SelectBoth method described in Either bifunctor can be still implemented based on Match.
This API is much more locked down, so should leave little doubt about how it's supposed to be used. Apart from the methods inherited from System.Object, this Either<L, R> class only exposes one public method: Match. It's also sealed, and its constructor is marked private, so not only can't you inherit from it, you also can't derive classes from Left or Right.
Usage is similar to before; for example, here's the above FindWinner method, changed to consume the encapsulated Either class:
public static Either<VoteError, T> FindWinner<T>(IReadOnlyCollection<T> votes) { var countedVotes = from v in votes group v by v into g let count = g.Count() orderby count descending select new { Vote = g.Key, Count = count }; var c = countedVotes.Take(2).Count(); if (c == 0) return Either.Left<VoteError, T>(VoteError.Empty); var x0 = countedVotes.ElementAt(0); if (c == 1) return Either.Right<VoteError, T>(x0.Vote); var x1 = countedVotes.ElementAt(1); if (Equals(x0.Count, x1.Count)) return Either.Left<VoteError, T>(VoteError.Tie); return Either.Right<VoteError, T>(x0.Vote); }
The only difference is that it no longer explicitly creates new instances of Left or Right, but instead uses the static factories.
If I were to publish a reusable C# library with Maybe, Either, and similar types, I'd design them like this so as to leave absolutely no doubt about the intended usage.
Church-encoded Maybe
Programming languages don't have to have a built-in notion of null values. Missing or optional values can be created from first principles. An introduction for object-oriented programmers.
This article is part of a series of articles about Church encoding. In this series, you'll learn how to re-create various programming language features from first principles. In previous articles, you learned how to implement Boolean logic without Boolean primitives, as well as how to model natural numbers. Through these examples, you'll learn how to model sum types without explicit language support.
The billion-dollar mistake #
All mainstream programming languages have a built-in notion of null: a value that isn't there. There's nothing wrong with the concept; you often run into situations where you need to return a value, but in certain cases, you'll have nothing to return. Division by zero would be one example. Attempting to retrieve the first element from an empty collection would be another.
Unfortunately, for fifty years, we've been immersed in environments where null references have been the dominant way to model the absence of data. This, despite the fact that even Sir Antony Hoare, the inventor of null references, has publicly called it his billion-dollar mistake.
You can, however, model the potential absence of data in saner ways. Haskell, for example, has no built-in null support, but it does include a built-in Maybe type. In Haskell (as well as in F#, where it's called option), Maybe is defined as a sum type:
data Maybe a = Nothing | Just a deriving (Eq, Ord)
If you're not familiar with Haskell syntax, this is a type declaration that states that the parametrically polymorphic (AKA generic) data type Maybe is inhabited by Just values that contain other values, plus the constant Nothing.
This article series, however, examines how to implement sum types with Church encoding.
Lambda calculus maybe #
Church encoding is based on the lambda calculus, which defines a universal model of computation based entirely on functions (lambda expressions) and recursion. In lambda calculus, the contract of Maybe is defined as an expression that takes two arguments. There's two fundamental 'implementations' of the contract:
nothing = λn.λj.n just = λx.λn.λj.j x
The contract is that the first function argument (n) represents the nothing case, whereas the second argument (j) represents the just case.
The nothing function is a lambda expression that takes two arguments (n and j), and always returns the first, left-most argument (n).
The just function is a lambda expression that takes three arguments (x, n, and j), and always returns j x. Recall that in the lambda calculus, everything is a function, including j, so j x means that the function j is called with the argument x.
A few paragraphs above, I wrote that the contract of maybe is modelled as an expression that takes two arguments, yet just takes three arguments. How does that fit?
In the lambda calculus, expressions are always curried, so instead of viewing just as a function with three arguments, you can view it as a function that takes a single element (x) and returns a function that takes two arguments. This agrees with Haskell's Just data constructor:
Prelude> :t Just Just :: a -> Maybe a
Haskell tells us that Just is a function that takes an a value (corresponding to x in the above just lambda expression) and returns a Maybe a value.
Church-encoded Maybe in C# #
Both lambda calculus and Haskell rely on currying and partial application to make the contract fit. In C#, as you've previously seen, you can instead define an interface and rely on class fields for the 'extra' function arguments. Since Church-encoded Maybe is represented by a function that takes two arguments, we'll once again define an interface with a single method that takes two arguments:
public interface IMaybe<T> { TResult Match<TResult>(TResult nothing, Func<T, TResult> just); }
In the first article, about Church-encoded Boolean values, you saw how two mutually exclusive values could be modelled as a method that takes two arguments. Boolean values are simply constants (true and false), where the next example (natural numbers) included a case where one case (successor) contained data. In that example, however, the data was statically typed as another INaturalNumber value. In the current IMaybe<T> example, the data contained in the just case is generic (it's of the type T).
Notice that there's two levels of generics in play. IMaybe<T> itself is a container of the generic type T, whereas Match enables you to convert the container into the rank-2 polymorphic type TResult.
Once more, the contract of IMaybe<T> is that the first, left-hand argument represents the nothing case, whereas the second, right-hand argument represents the just case. The nothing implementation, then, is similar to the previous ChurchTrue and Zero classes:
public class Nothing<T> : IMaybe<T> { public TResult Match<TResult>(TResult nothing, Func<T, TResult> just) { return nothing; } }
Again, the implementation unconditionally returns nothing while ignoring just. You may, though, have noticed that, as is appropriate for Maybe, Nothing<T> has a distinct type. In other words, Nothing<string> doesn't have the same type as Nothing<int>. This is not only 'by design', but is a fundamental result of how we define Maybe. The code simply wouldn't compile if you tried to remove the type argument from the class. This is in contrast to C# null, which has no type.
You implement the just case like this:
public class Just<T> : IMaybe<T> { private readonly T value; public Just(T value) { this.value = value; } public TResult Match<TResult>(TResult nothing, Func<T, TResult> just) { return just(value); } }
According to the contract, Just<T> ignores nothing and works exclusively with the just function argument. Notice that the value class field is private and not exposed as a public member. The only way you, as a caller, can potentially extract the value is by calling Match.
Here are some examples of using the API:
> new Nothing<Guid>().Match(nothing: "empty", just: g => g.ToString()) "empty" > new Just<int>(42).Match(nothing: "empty", just: i => i.ToString()) "42" > new Just<int>(1337).Match(nothing: 0, just: i => i) 1337
Notice that the third example shows how to extract the value contained in a Nothing<int> object without changing the output type. All you have to do is to supply a 'fall-back' value that can be used in case the value is nothing.
Maybe predicates #
You can easily implement the standard Maybe predicates IsNothing and IsJust:
public static IChurchBoolean IsNothing<T>(this IMaybe<T> m) { return m.Match<IChurchBoolean>( nothing : new ChurchTrue(), just : _ => new ChurchFalse()); } public static IChurchBoolean IsJust<T>(this IMaybe<T> m) { return m.Match<IChurchBoolean>( nothing : new ChurchFalse(), just : _ => new ChurchTrue()); }
Here, I arbitrarily chose to implement IsJust 'from scratch', but I could also have implemented it by negating the result of calling IsNothing. Once again, notice that the predicates are expressed in terms of Church-encoded Boolean values, instead of the built-in bool primitives.
Functor #
From Haskell (and F#) we know that Maybe is a functor. In C#, you turn a container into a functor by implementing an appropriate Select method. You can do this with IMaybe<T> as well:
public static IMaybe<TResult> Select<T, TResult>( this IMaybe<T> source, Func<T, TResult> selector) { return source.Match<IMaybe<TResult>>( nothing: new Nothing<TResult>(), just: x => new Just<TResult>(selector(x))); }
Notice that this method turns an IMaybe<T> object into an IMaybe<TResult> object, using nothing but the Match method. This is possible because Match has a generic return type; thus, among other types of values, you can make it return IMaybe<TResult>.
When source is a Nothing<T> object, Match returns the object in the nothing case, which here becomes a new Nothing<TResult> object.
When source is a Just<T> object, Match invokes selector with the value contained in the just object, packages the result in a new Just<TResult> object, and returns it.
Because the Select method has the correct signature, you can use it with query syntax, as well as with normal method call syntax:
IMaybe<int> m = new Just<int>(42); IMaybe<string> actual = from i in m select i.ToString();
This example simply creates a just value containing the number 42, and then maps it to a string. Another way to write the same expression would be with method call syntax:
IMaybe<int> m = new Just<int>(42); IMaybe<string> actual = m.Select(i => i.ToString());
In both cases, the result is a just case containing the string "42".
Summary #
In this article, you saw how it's possible to define the Maybe container from first principles, using nothing but functions (and, for the C# examples, interfaces and classes in order to make the code easier to understand for object-oriented developers).
The code shown in this article is available on GitHub.
Church-encoding enables you to model sum types as functions. So far in this article series, you've seen how to model Boolean values, natural numbers, and Maybe. Common to all three examples is that the data type in question consists of two mutually exclusive cases. There's at least one more interesting variation on that pattern.
Next: Church-encoded Either.
Comments
Hey Mark, thanks so much for writing. Coming at this some 3 years later but it's been an insightful introduction to functional programming.
I've been trying Church encoding and algebraic data types in general out for a little while now, and had a question
about a potential alternate implementation of Select and friends. I had been reviewing
Church-encoded Booleans and really
appreciated the way the And/Or/Not Match implementations managed to
defer executing their operator's actual operation until needed. So I figured there might be a way to do something similar
with Select.
Here's what I came up with:
public class MaybeSelected<T, TSelectResult> : IMaybe<TSelectResult> { private readonly IMaybe<T> source; private readonly Func<T, TSelectResult> selector; public MaybeSelected( IMaybe<T> source, Func<T, TSelectResult> selector) { this.source = source; this.selector = selector; } public TResult Match<TResult>(TResult nothing, Func<TSelectResult, TResult> just) { return source.Match( nothing: nothing, just: x => just(selector(x))); } }
Which resulted in the following Select refactoring:
public static IMaybe<TResult> Select<T, TResult>( this IMaybe<T> source, Func<T, TResult> selector) { return new MaybeSelected<T, TResult>(source, selector); }
After ensuring the refactor passed unit tests, I went on to the monad:
public class MaybeFlattened<T> : IMaybe<T> { private readonly IMaybe<IMaybe<T>> source; public MaybeFlattened(IMaybe<IMaybe<T>> source) { this.source = source; } public TResult Match<TResult>(TResult nothing, Func<T, TResult> just) { return source.Match( nothing: nothing, just: x => x.Match( nothing: nothing, just: just)); } }
Which resulted in a similar refactoring of Flatten. I'm pretty happy with the results, especially in the
case of Select not needing to execute its selector until Match is called. This
seems to resemble the behavior of IEnumerable not actually enumerating until something like
ToList is called. The unit tests pass, so I have some demonstration of correct behavior, though I suppose
being new to this I may have failed to understand something more essential than the demonstrated behavior they exercise.
That said, I am more interested in the nature of the refactoring itself. It seems to be a kind of isomorphism similar to
that of argument lists, but extending beyond
the method's parameters to including its behavior as well. In general, the process involved taking, e.g., the
Select method's parameters and making corresponding fields in the new MaybeSelected class; and
then taking the method's implementation and shuffling it off to some method in the new class (Match) that
would eventually perform the original execution. I like seeing how the x => x "phrase" lines up between
the original Flatten and MaybeFlattened.Match. So going beyond "it works," would you mind
sharing your thoughts on what kind of animal we've got here?
Nathaniel, thank you for writing. If you're new to this, I tip my hat to you. As far as I can tell, you've arrived at the insight that lazy evaluation seems to be a 'toggle' you can turn on or off without affecting the lawfulness of the underlying concepts.
I admit that I haven't done a full, formal analysis of your approach, but it looks completely legit to me.
The reason I feel confident that this is still a lawful Maybe monad is that Haskell is lazy by default. I've learned much of what I know about functors and monads from Haskell. In Haskell, most of the monads are lazy, and you explicitly have to opt in if you want strict evaluation (in Haskell, the opposite of lazy is usually called strict, although it's a little more complicated than that.) In most other languages (C# included), expressions are usually eagerly evaluated, and you have to explicitly opt into laziness.
In those languages, you can use something like Lazy<T> to form an applicative functor (and monad, but I haven't written that article). You can also show that it obeys the functor laws. It also obeys the applicative functor and monad laws, but again, I haven't written those articles...
What you've done here is slightly different, since you haven't explicitly used Lazy<T>, but I'd expect your variation to be isomorphic to Lazy<Maybe<T>> (where Maybe<T> is an eagerly evaluated version of Maybe). If you're interested, you may consider this exercise:
Write two functions that convert back and forth between the two representations, and demonstrate that the two implementations behave in the same way.
In general, knowing how to enable lazy evaluation can be a useful tool to add to your toolkit, but as all Haskellers have learned, it comes with a disadvantage, too. Instead of evaluating values right away, you have to pass around expressions. Such expressions containing other expressions are called thunks, and they can grow quite large. In Haskell, which relies heavily on this mechanism, if you aren't careful, you can build up thunks that eat up all available memory.
In reality, I don't experience this to be a big problem as long as one stays aware of it, but the point is that you can't just forget about it. Laziness isn't a free ride to better performance. You trade more efficient computation for more inefficient memory use.
Church-encoded natural numbers
Natural numbers don't have to be built into programming languages. An introduction for object-oriented programmers.
This article is part of a series of articles about Church encoding. The previous article, about Church-encoding of Boolean values, concluded with the question: how do you determine whether an integer is even or odd?
That sounds easy, but turns out to be more complicated that you might think at first glance.
Built-in options #
How would you normally check whether a number is even? In some languages, like Haskell, it's built into the base library:
Prelude> even 1337 False Prelude> even 42 True
In C#, surprisingly, I don't think it's built-in, but it's easy to implement a method to answer the question:
public static bool IsEven(this int i) { return i % 2 == 0; }
You could implement an IsOdd method either by using the != operator instead of ==, but otherwise copy the implementation of IsEven; or, alternatively, call IsEven and negate the result.
This works fine in normal C# code, but in this article, the agenda is different. We're investigating how programming with the previous article's IChurchBoolean API would look. The above built-in options use Boolean language primitives, so that's not really instructive.
Boolean conversions #
It's easy to convert between Church-encoded Boolean values and built-in Boolean values. For reasons I'll explain shortly, I still don't think that's instructive in this particular context, but for good measure I'll cover how to do it.
A method like the above IsEven returns bool. If you, instead, want an IChurchBoolean, you can use this simple conversion method:
public static IChurchBoolean ToChurchBoolean(this bool b) { if (b) return new ChurchTrue(); else return new ChurchFalse(); }
Alternatively, you can also use the ternary operator, but an ugly cast is necessary to make the C# compiler happy:
public static IChurchBoolean ToChurchBoolean(this bool b) { return b ? (IChurchBoolean)new ChurchTrue() : new ChurchFalse(); }
Regardless of which implementation you choose, you'd be able to interact with the result as an IChurchBoolean values, as this small interactive session demonstrates:
> 42.IsEven().ToChurchBoolean().Match("Even", "Odd") "Even" > 1337.IsEven().ToChurchBoolean().Match("Even", "Odd") "Odd"
Still, converting from bool to IChurchBoolean doesn't address the underlying question: is it possible to write programs without built-in Boolean primitives?
The conversion function ToChurchBoolean uses built-in Boolean values and functions, so it doesn't show whether or not it would be possible to make do without those.
Before we abandon that line of inquiry, however, I think it's only fair to share a conversion method that goes the other way:
public static bool ToBool(this IChurchBoolean b) { return b.Match(true, false); }
This function enables you to convert an IChurchBoolean value into a primitive C# bool, because when b represents true, the first argument (i.e. true) is returned, and when b represents false, the second argument (i.e. false) is returned.
Peano numbers #
If we can't use built-in primitives or operators that return them (e.g. ==), we may not be able to move forward with built-in numbers, either. What we can do, however, is to follow the lambda calculus to implement natural numbers using Church encoding. This will enable us to determine if a natural number is even or odd.
Lambda calculus models natural numbers according to Peano's model. In short, a natural number is either zero (or one, depending on the specific interpretation), or a successor to another natural number. As an example, using the Successor class that I'll develop later in this article, the number three can be represented as new Successor(new Successor(new Successor(new Zero()))) - it's the number after the number after the number after zero.
Like Church-encoded Boolean values, a Church-encoded natural number is a function that takes two arguments, corresponding to zero, and a successor function:
zero = λf.λx.x one = λf.λx.f x two = λf.λx.f (f x) three = λf.λx.f (f (f x)) ...
Each of these functions takes an initial value x, as well as a function f. In the lambda calculus, neither x nor f have any implied interpretation; it's the number of applications of f that defines the number.
In most translations into programming languages that I've encountered, however, x is usually interpreted as zero, and f as the successor function. In Haskell, for example, a common way to model Peano numbers is to use a sum type:
data Peano = Zero | Succ Peano deriving (Eq, Show)
Basically, this means that a value of the Peano type can either be the atom Zero, or a Succ value. Notice that Succ contains another Peano value; the data type is recursive.
You can write Haskell values like these:
*Peano> zero = Zero *Peano> one = Succ Zero *Peano> two = Succ (Succ Zero) *Peano> three = Succ (Succ (Succ Zero))
Alternatively, you can also define the numbers based on previous definitions:
*Peano> zero = Zero *Peano> one = Succ zero *Peano> two = Succ one *Peano> three = Succ two
This variation of Peano numbers uses an explicit sum type, but as the lambda calculus representation suggests, you can also use Church encoding to represent the two cases.
Church-encoded natural numbers #
If you recall Church-encoded Boolean values, you may remember that they are functions that take two values: a value to be used in case of true, and a value to be used in the case of false. You can do something similar with natural numbers. Zero is like true and false, in the sense that it's nothing but a label without any associated data. Succ, on the other hand, contains another Peano value. The way to do that is to turn the successor case into a function. Doing that, you'll arrive at an interface like this:
public interface INaturalNumber { T Match<T>(T zero, Func<INaturalNumber, T> succ); }
The first argument, on the left-hand side, is the case to use when an object represents zero. The second argument, on the right-hand side, is a function that will ultimately produce the value associated with a successor. The implied contract here is that the INaturalNumber passed as input to succ is the predecessor to 'the current value'. This may seem counter-intuitive, but hopefully becomes clearer when you see the Successor class below. The crucial insight is that a successor value has no intrinsic value; it's entirely defined by how many predecessors it has.
The zero implementation is similar to how Church-encoding implements true:
public class Zero : INaturalNumber { public T Match<T>(T zero, Func<INaturalNumber, T> succ) { return zero; } }
Notice that the Zero class implements INaturalNumber by always returning zero, and consequently always ignoring succ.
Another class, Successor, handles the right-hand side of the Match method:
public class Successor : INaturalNumber { private readonly INaturalNumber predecessor; public Successor(INaturalNumber n) { this.predecessor = n; } public T Match<T>(T zero, Func<INaturalNumber, T> succ) { return succ(predecessor); } }
Notice that Successor composes its predecessor via Constructor Injection, and unconditionally calls succ with its predecessor when Match is invoked.
Working with natural numbers #
What can you do with this INaturalNumber API, then?
Initially, you can define some numbers, like the above Haskell examples:
public static class NaturalNumber { public static INaturalNumber Zero = new Zero(); public static INaturalNumber One = new Successor(Zero); public static INaturalNumber Two = new Successor(One); public static INaturalNumber Three = new Successor(Two); public static INaturalNumber Four = new Successor(Three); public static INaturalNumber Five = new Successor(Four); public static INaturalNumber Six = new Successor(Five); public static INaturalNumber Seven = new Successor(Six); public static INaturalNumber Eight = new Successor(Seven); public static INaturalNumber Nine = new Successor(Eight); // More memmbers go here... }
Here, I arbitrarily chose to define the numbers from zero to nine, but you could go on for as long as you care.
You can also convert these Church-encoded numbers to primitive int values, like this:
public static int Count(this INaturalNumber n) { return n.Match( 0, p => 1 + p.Count()); }
Here are some examples from a C# Interactive session:
> NaturalNumber.Zero.Count() 0 > NaturalNumber.One.Count() 1 > NaturalNumber.Seven.Count() 7
The implementation of Count is recursive. When n is a Zero instance, it'll return the first argument (0), but when it's a Successor, it'll invoke the lambda expression p => 1 + p.Count(). Notice that this lambda expression recursively calls Count on p, which is the Successor's predecessor. It'll keep doing that until it reaches a Zero instance.
Recursion is a central part of the lambda calculus; you can't do anything useful without it. If you're a C# or Java programmer, you may be concerned, because recursion tends to be problematic in such languages. Deeply recursive functions will sooner or later crash because of a stack overflow.
You shouldn't, however, be concerned. First, I'm not trying to convince you to write all your future C# or Java code using Church-encoded numbers and Boolean values. The point of this article series is to investigate the fundamentals of computations, and to gain a better understanding of sum types. As such, the code examples presented here are only demonstrations of the underlying principles. Lambda calculus itself serves the same purpose: it's a universal model of computation; it wasn't intended to be a practical programming language - in fact, there were no programmable computers in 1936.
Furthermore, the problem with recursion causing stack overflow isn't universal. Languages like F# and Haskell support tail recursion, thereby enabling recursive functions to run to arbitrary depths.
Pattern matching #
In the previous article, I hinted that there's a reason I decided to name the interface method Match. This is because it looks a lot like pattern matching. In F#, you could write count like this:
type Peano = Zero | Succ of Peano // Peano -> int let rec count n = match n with | Zero -> 0 | Succ p -> 1 + count p
This implementation, by the way, isn't tail-recursive, but you can easily refactor to a tail-recursive implementation like this:
// Peano -> int let count n = let rec countImp acc n = match n with | Zero -> acc | Succ p -> countImp (1 + acc) p countImp 0 n
Both variations use the match keyword to handle both the Zero and the Succ case for any Peano value n. That's already close to the above C# code, but using the optional C# language feature of named arguments, you can rewrite the implementation of Count to this:
public static int Count(this INaturalNumber n) { return n.Match( zero: 0, succ: p => 1 + p.Count()); }
This starts to look like pattern matching of sum types in F#. The argument names aren't required, but using them makes it clearer which cases the Match method handles.
Addition #
You can now start to add features and capabilities to the natural numbers API. An obvious next step is to implement addition:
public static INaturalNumber Add(this INaturalNumber x, INaturalNumber y) { return x.Match( zero: y, succ: p => new Successor(p.Add(y))); }
Again, the implementation is recursive. When x is zero, you simply return y, because zero + y is y. When x is a Successor, you recursively add y to its predecessor, and put the result in a new Successor. You can think of the predecessor p as one less than the successor. By recursively subtracting one from any Successor object, you'll eventually match the zero case, which will then return y. When the stack unrolls, each stack puts the previous result into a new Successor. This happens exactly the correct number of times corresponding to the value of x, because that's the size of the stack when Add hits zero.
Here are some examples:
> NaturalNumber.One.Add(NaturalNumber.Two).Count() 3 > NaturalNumber.Four.Add(NaturalNumber.Three).Count() 7 > NaturalNumber.Seven.Add(NaturalNumber.Six).Count() 13
You can also implement multiplication, but that's a bit more complicated, and not relevant to the topic of this article (which is how to determine if a number is even or odd).
Testing for zero #
In addition to basic arithmetic, you can also define functions that tell you something about a natural number. We'll start gently with a function that tells us whether or not a number is zero:
public static IChurchBoolean IsZero(this INaturalNumber n) { return n.Match<IChurchBoolean>( zero: new ChurchTrue(), succ: _ => new ChurchFalse()); }
The IsZero method simply returns a ChurchTrue object when n is a Zero instance, and a ChurchFalse object for all other numbers.
You can see that this works in this C# Interactive session:
> NaturalNumber.Two.IsZero() ChurchFalse { } > NaturalNumber.Zero.IsZero() ChurchTrue { } > NaturalNumber.Three.IsZero() ChurchFalse { }
You can also Match on the returned Boolean value to return e.g. a string:
> NaturalNumber.Nine.IsZero().Match(trueCase: "Zero", falseCase: "Not zero") "Not zero" > NaturalNumber.Zero.IsZero().Match(trueCase: "Zero", falseCase: "Not zero") "Zero"
This already demonstrates that you can implement predicates and branching logic from first principles, without resorting to built-in Boolean primitives or operators.
Detecting even numbers #
Testing whether a natural number is even or uneven requires a bit more work. It's probably easiest to understand if we first consider an F# implementation:
// Peano -> ChurchBoolean let rec isEven n = match n with | Zero -> ChurchTrue | Succ Zero -> ChurchFalse | Succ (Succ p) -> isEven p
Zero is even, so when n matches Zero, isEven returns ChurchTrue. Conversely, when the input is Succ Zero (i.e. one), the return value is ChurchFalse because one is odd.
The zero and one cases serve as exit cases for the recursive algorithm. Since we've handled Zero and Succ Zero (that is, zero and one), we know that any other case must be at least twice nested. This means that the Succ (Succ p) pattern matches all other cases. You can think of p as n - 2.
The algorithm proceeds to recursively call isEven with p (i.e. n - 2). Sooner or later, these recursive function calls will match either the Zero or the Succ Zero case, and exit with the appropriate return value.
C# doesn't have as sophisticated pattern matching features as F#, so we're going to have to figure out how implement this algorithm without relying on a nested pattern like Succ (Succ p). As an initial step, we can rewrite the function in F#, using two matches instead of one:
// Peano -> ChurchBoolean let rec isEven n = match n with | Zero -> ChurchTrue | Succ p1 -> match p1 with | Zero -> ChurchFalse | Succ p2 -> isEven p2
This isn't as elegant as the previous implementation, but on the other hand, it's straightforward to translate to C#:
public static IChurchBoolean IsEven(this INaturalNumber n) { return n.Match( zero: new ChurchTrue(), // 0 is even, so true succ: p1 => p1.Match( // Match previous zero: new ChurchFalse(), // If 0 then successor was 1 succ: p2 => p2.IsEven())); // Eval previous' previous }
Like in the F# example, when n is a Zero object, it'll return the value associated with the zero case. Since zero is even, it returns a ChurchTrue object.
In all other cases, a Match on the predecessor p1 is required. If that nested match is zero, then we know that n must have been one, since the predecessor turned out to be zero. In that case, then, return a ChurchFalse object, because one isn't even.
The nested Match considers the predecessor p1. In the succ case of the nested Match, then, we can consider p2; that is, the predecessor to the predecessor to n - in other words: n - 2. The function recursively calls itself with n - 2, and it'll keep doing so until it matches either the zero or the one case.
The implementation works:
> NaturalNumber.Two.IsEven() ChurchTrue { } > NaturalNumber.Three.IsEven() ChurchFalse { }
IsEven is implemented from first principles. The only language features we need are lambda expressions and recursion, although in order to make these examples slightly more idiomatic, I've also used interfaces and classes.
Detecting odd numbers #
You could implement a corresponding IsOdd method similarly to IsEven, but it's easier to use the Boolean operators already in place from the previous article:
public static IChurchBoolean IsOdd(this INaturalNumber n) { return new ChurchNot(n.IsEven()); }
IsOdd is simply the Boolean negation of IsEven. Like IsEven it also works correctly:
> NaturalNumber.Six.IsOdd().Match(trueCase: "Odd", falseCase: "Even") "Even" > NaturalNumber.Seven.IsOdd().Match(trueCase: "Odd", falseCase: "Even") "Odd"
You can implement other operators (like multiplication) and predicates from the building blocks shown here, but I'm not going to cover that here (see the accompanying GitHub repository for more code). I hope that this article gave you a sense of how a programming language can be designed from the low-level building blocks defined by the lambda calculus.
Summary #
Giuseppe Peano described natural numbers as an initial number (zero) and successors to that number. Church formulated Peano numbers in the lambda calculus. Using Church encoding, you can translate this representation to various programming languages, including, as you've seen in this article, C#.
In the previous article, you saw how to model Boolean values as a set of functions with two arguments. In this article, you saw how to model natural numbers with another set of functions that take two arguments. In the next article, you'll see another data type modelled as a set of functions with two arguments. It looks like a patterns is starting to appear.
Next: Church-encoded Maybe.
Church-encoded Boolean values
Boolean values, and logical branching, don't have to be built into programming languages. An introduction for object-oriented programmers.
This article is part of a series of articles about Church encoding.
Years ago, the so-called Anti-IF Campaign made the rounds on various social media (back then, IIRC, mostly known as 'the blogosphere'). The purpose of the campaign was never to eradicate every single use of if statements or expressions in source code, but rather to educate people about alternatives to the Arrow anti-pattern.
One easy way to deal with arrow code is to Replace Nested Conditionals with Guard Clauses, but that's not always possible. Another way is to encapsulate some if blocks in helper methods. Yet another way would be to use polymorphic dispatch, but how does that even work? Don't you, deep down, need at least a few if keywords here and there?
It turns out that the answer, surprisingly, is no.
Untyped Boolean functions #
if/then/else expressions are based on Boolean values (true and false): if some Boolean value is true, then something happens; otherwise, something else happens. Most programming languages, including C, C++, Java, C#, and JavaScript, have a ternary operator, which in C# looks like this:
isEven ? "Probably not a prime." : "Could be a prime.";
You can think of an expression like that as a function that takes a Boolean value and two potential return values: one for the true case, and one for the false case.
In lambda calculus, the only primitive building blocks are functions. There's no built-in Boolean values, but you can define them with functions. Boolean values are functions that take two arguments. By conventions, the first argument (the one to the left) represents the true case, whereas the second argument (to the right) signifies the false case - just like the ternary operator. In the lambda calculus, functions are curried, but we know from uncurry isomorphisms that we can also represent a two-argument function as a function that takes a two-tuple (a pair) as a single argument. Furthermore, we know from function isomorphisms that we can represent a function as an instance method. Therefore, we can declare a Boolean value in C# to be an object that implements this interface:
public interface IChurchBoolean { object Match(object trueCase, object falseCase); }
You'll notice that I've chosen to call the method Match, for reasons that should hopefully become clear as we go along.
The intent with such a Church-encoded Boolean is that any object that represents true should return the left argument (trueCase), whereas an object that represents false should return the right argument (falseCase).
In other words, true is an interface implementation:
public class ChurchTrue : IChurchBoolean { public object Match(object trueCase, object falseCase) { return trueCase; } }
Notice that this implementation always returns trueCase while ignoring falseCase. No explicit if statement is required.
Likewise, false is implemented the same way:
public class ChurchFalse : IChurchBoolean { public object Match(object trueCase, object falseCase) { return falseCase; } }
So far, this doesn't offer much capability, but it does already give you the ability to choose between two values, as this little C# Interactive session demonstrates:
> var b = new ChurchTrue();
> b.Match("foo", "bar")
"foo"
> var b = new ChurchFalse();
> b.Match("foo", "bar")
"bar"
When 'the Boolean value' is a ChurchTrue instance, then the left argument is returned; otherwise, when b is a ChurchFalse object, the return value is the right-hand value - just like the ternary operator.
Boolean And #
You can now define the standard Boolean operators and, or, and not. Starting with and:
public class ChurchAnd : IChurchBoolean { private readonly IChurchBoolean x; private readonly IChurchBoolean y; public ChurchAnd(IChurchBoolean x, IChurchBoolean y) { this.x = x; this.y = y; } public object Match(object trueCase, object falseCase) { return x.Match(y.Match(trueCase, falseCase), falseCase); } }
The ChurchAnd class is an implementation of IChurchBoolean that composes two other IChurchBoolean values, x and y. You can use it like this:
var b = new ChurchAnd(new ChurchTrue(), new ChurchFalse());
In this case, b represents false, because it'll always return the right-hand argument when Match is invoked.
Notice that the implementation of ChurchAnd.Match first matches on x. Only if x itself is true can the expression passed as the first argument be returned; otherwise, falseCase will be returned. Thus, if x is true, the expression y.Match(trueCase, falseCase) will be returned, and only if that as well evaluates to true is the final result true. The trueCase value is only returned if y represents true, as well as x.
In the lambda calculus, Boolean and is defined like this:
and = λx.λy.λt.λf.x (y t f) f
The way to read this is that Boolean and is a function that takes four arguments:
x, a Boolean valuey, another Boolean valuet, the value to return if the expression is true; thetrueCaseargument in the above C# implementation.f, the value to return if the expression is false; thefalseCaseargument in the above C# implementation.
x and y are functions. and calls x with two arguments. Since Boolean and requires both x and y to be true, it passes f as the second argument to x, because if x represents false, it'll return its right-hand argument. Only if x represents true does it make sense to investigate the Boolean value of y, which is also a function that takes two arguments. Only if y also represents true will t be returned.
This is exactly the same implementation as the above C# code.
Wait a minute, though, didn't I write that Boolean values are functions that take two arguments? And isn't and a function that takes four arguments?
Yes, indeed. That's how currying works. You can view and as a function that takes four arguments, but you can also view it as a function that takes two arguments (x and y) and returns another function that takes two arguments. This becomes clearer with partial application. When translating to C#, the 'contract' (that a Boolean value is a function that takes two arguments) is modelled as the interface IChurchBoolean, while the 'extra arguments' x and y become class fields, injected via the class' constructor.
Boolean Or #
In the lambda calculus, Boolean or is defined like this:
or = λx.λy.λt.λf.x t (y t f)
Translated to C#, this becomes:
public class ChurchOr : IChurchBoolean { private readonly IChurchBoolean x; private readonly IChurchBoolean y; public ChurchOr(IChurchBoolean x, IChurchBoolean y) { this.x = x; this.y = y; } public object Match(object trueCase, object falseCase) { return x.Match(trueCase, y.Match(trueCase, falseCase)); } }
You can see that this is another direct translation. Boolean or only requires (at least) one of the Boolean values to be true, so if x is true, you can immediately return trueCase. Otherwise, in the case where x is false, there's still a chance that the entire expression could be true, so you'll have to evaluate y as well. When y represents true, you can still return trueCase. Only when y is also false should you return falseCase.
You can use ChurchOr like this:
var b = new ChurchOr(new ChurchTrue(), new ChurchFalse());
Here, b is true because true or false is true.
Boolean Not #
Finally, you can also define Boolean negation. In lambda calculus it's:
not = λx.λt.λf.x f t
Notice how this simply swaps the arguments passed to x. In C#, this translates to:
public class ChurchNot : IChurchBoolean { private readonly IChurchBoolean b; public ChurchNot(IChurchBoolean b) { this.b = b; } public object Match(object trueCase, object falseCase) { return b.Match(falseCase, trueCase); } }
You can combine all the Boolean operators like this:
var b = new ChurchOr(new ChurchFalse(), new ChurchNot(new ChurchTrue()));
Here, b is false because false or (not true) is false.
Typed Boolean functions #
So far, the IChurchBoolean interface has been untyped, in the sense that it took object arguments and had an object return type. You can, however, easily make the interface strongly typed, using generics:
public interface IChurchBoolean { T Match<T>(T trueCase, T falseCase); }
This doesn't really change the rest of the code you've seen in this article. The method signatures chance, but the implementations remain as shown. You can see the change in this commit.
Semigroups and monoids #
The strongly typed signature accentuates that the Match method is a binary operation; it takes two values of the type T and returns a single T value. Is it a monoid, then?
It's not a single monoid, but rather a collection of semigroups, some of which are monoids as well. The implementation of ChurchTrue corresponds to the first semigroup, and ChurchFalse to the last semigroup. You can make this explict in Haskell:
import Data.Semigroup churchTrue :: a -> a -> a churchTrue t f = getFirst (First t <> First f)
If you compare this implementation of churchTrue to the Travis Whitaker's true function, his is much simpler. I'm not suggesting that using First is better; I'm only trying to illustrate the connection.
If you aren't familiar with how things are done in Haskell, <> is the 'generic semigroup binary operator'. What it does depends on the type of expressions surrounding it. By wrapping both t and f in First containers, the <> operator becomes the operator that always returns the first argument (i.e. First t). Since the result is a First value, you have to unwrap it again by applying getFirst.
Likewise, you can define false:
churchFalse :: a -> a -> a churchFalse t f = getLast (Last t <> Last f)
This still uses the <> operator, but now with the Last container, which gives it all the behaviour of the last semigroup.
The any and all monoids are implemented as compositions of these two fundamental semigroups. In the C# code in this article, they're implemented by ChurchAnd and ChurchOr, although in neither case have I defined an explicit identity value. This is, however, possible, so let's continue with the Haskell code to see what that would look like. First, you can define the 'naked' operations:
churchAnd x y t f = x (y t f) f churchOr x y t f = x t (y t f)
I have here omitted the type signatures on purpose, as I believe they might confuse rather than help. In both cases, the logic is the same as in the above ChurchAnd and ChurchOr classes, although, as you can see, Haskell code is much terser.
These two functions already work as desired, but we can easily turn both into their respective monoids. First, the all monoid:
newtype ChurchAll = ChurchAll { runAll :: forall a. a -> a -> a } instance Semigroup ChurchAll where ChurchAll x <> ChurchAll y = ChurchAll (churchAnd x y) instance Monoid ChurchAll where mempty = ChurchAll churchTrue mappend = (<>)
In order for this code to compile, you must enable the RankNTypes language extension, which I did by adding the {-# LANGUAGE RankNTypes #-} pragma to the top of my code file. The forall a declaration corresponds to the <T> type annotation on the C# Match method. You can think of this as that the type argument is scoped to the function instead of the type.
The Semigroup instance simply delegates its behaviour to churchAnd, and the Monoid instance returns churchTrue as the identity (mempty).
Similarly, you can implement the any monoid:
newtype ChurchAny = ChurchAny { runAny :: forall a. a -> a -> a } instance Semigroup ChurchAny where ChurchAny x <> ChurchAny y = ChurchAny (churchOr x y) instance Monoid ChurchAny where mempty = ChurchAny churchFalse mappend = (<>)
As is also the case with ChurchAll, the ChurchAny instance of Semigroup simply delegates to a 'naked' function (in this case churchOr), and the Monoid instance again delegates mappend to <> and returns churchFalse as the identity.
The following brief GHCi session demonstrates that it all works as intended:
λ> runAny (ChurchAny churchTrue <> ChurchAny churchFalse) "foo" "bar" "foo" λ> runAny (ChurchAny churchFalse <> ChurchAny churchFalse) "foo" "bar" "bar" λ> runAll (ChurchAll churchFalse <> ChurchAll churchTrue) "foo" "bar" "bar" λ> runAll (ChurchAll churchTrue <> ChurchAll churchTrue) "foo" "bar" "foo"
Recall that a Church-encoded Boolean is a function that takes two values - in all the four above examples "foo" and "bar". When the expression represents true it returns the left-hand value ("foo"); otherwise, it returns the right-hand value ("bar").
In summary, the Church-encoded Boolean values true and false correspond to the first and last semigroups. You can compose the well-known monoids over Boolean values using these two basic building blocks.
Summary #
You'd normally think of Boolean values as language primitives. True and false are built into most languages, as well as common operators like and, or, and not. While this is convenient, it doesn't have to be like this. Even in languages that already have built-in support for Boolean values, like Haskell or C#, you can define Church-encoded Boolean values from first principles.
In the lambda calculus, a Boolean value is function that takes two arguments and returns the left-hand argument when true, and the right-hand argument when false.
At this point, it may seem like you can't do much with the IChurchBoolean API. How could you, for instance, determine whether an integer is even or odd?
This innocuous-looking question is harder to answer than you may think, so that's worthy of its own article.
Comments
Roman, thank you for writing. For no particularly good reason. I tend to automatically disregard
undefined, since it's basically one kind of bottom in Haskell.But I admit that that's not a bulletproof reason, since the actual function, at that point in the article, is still partial.
So honestly, the best answer is that I wrote "the simplest implementation I could think of" because I didn't think of
undefined.