Church-encoded Either by Mark Seemann

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

type Result<'T,'TError> = | Ok of ResultValue:'T | Error of ErrorValue:'TError

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();
        }
    }
}

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);
}

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);
}

• ← Previous
• Archive
• Next →