Programming should be enjoyable

A software blog by Joseph Junker

The Church and Scott Encodings of Algebraic Data Types

Recursive data as pure functions

02 Jan 2022

Previously I wrote about the Church encoding of non-recursive algebraic data types. In this post I’ll cover the Church encoding of recursive data types, as well as the related Scott encoding.

This post uses TypeScript, and will use the abbreviation “ADT” to mean “algebraic data type”, not “abstract data type”.

This post is longer than I’d prefer, but I’ve chosen to err on the side of comprehensiveness rather than concision. I’ve included a table of contents to assist readers who wish to jump to specific topics.

Contents #

Linked lists as an algebraic data type #

Linked lists are the bread and butter of functional programming. Here is an ADT-style representation of them in TypeScript:

type List<A> = Cons<A> | Nil;

type Nil = {
    tag: "nil"
};

type Cons<A> = {
    tag: "cons",
    head: A,
    tail: List<A>
};

const nil: Nil = { tag: "nil" };

function cons<A>(head: A, tail: List<A>): List<A> {
    return { tag: "cons", head, tail };
}

We can use these to create linked lists:

const oneTwoThree: List<number> = cons(1, cons(2, cons(3, nil)));

We can also consume data from the lists we’ve created:

if (oneTwoThree.tag === "cons") {
    console.log(`First item: ${oneTwoThree.head}`)
}

function listLength<A>(list: List<A>): number {
    let i = 0;
    let l = list;
    
    while(l.tag !== "nil") {
      i++;
      l = l.tail;
    }

    return i;
}

Note that consuming our ADT requires that we use conditional logic to perform type narrowing. We check the tag field of each object, which tells us which variant we are dealing with, and then we can access the fields corresponding to that variant. In other words, algebraic data types are represented as discriminated unions in TypeScript.

We will use this List type as the basis for the encodings shown in this post.

The Church encoding of linked lists #

In my last post I gave two rules for Church encoding non-recursive ADTs. Here is a restated1 version of them, along with an additional third rule which covers recursive cases:

  1. To Church-encode an algebraic data type with multiple variants, create a higher-order function which accepts one argument per variant. Each argument must be a function. When invoked, the encoding must invoke and return the result of the function corresponding to the variant which the encoding represents.
  2. To Church-encode a product type, create a higher-order function which takes a second function, f, as an argument. This f should accept multiple arguments, one for each field in the product type. When the encoding is invoked, it must pass the fields from the product type as arguments to f and return the result.
  3. In the type signature of a recursive type, recursive references must be replaced with the same type parameter used as the encoding’s return type.

Let’s see this in action by Church-encoding our list ADT.

First, working out the non-recursive parts of the type:

type ChurchList<A> = <B>(choices: {
    cons: (head: A, tail: ___) => B,
    nil: () => B
}) => B;

This is the result of applying rules 1 and 2.

In the List ADT, Cons.tail has type List, meaning that it is the recursive case. Our ChurchList is a polymorphic function whose return type is B, so we use B as the type of tail:

type ChurchList<A> = <B>(choices: {
    cons: (head: A, tail: B) => B,
    nil: () => B
}) => B;

And there we have it! We have Church-encoded our List type.

We can create functions for building ChurchList values:

// Convenience type, to reduce duplication below
type ChurchListArgs<A, B> = {
    cons: (a: A, b: B) => B,
    nil: () => B
};

const churchNil: ChurchList<never> =
    <B>({ nil }: ChurchListArgs<never, B>): B => nil();

function churchCons<A>(head: A, tail: ChurchList<A>): ChurchList<A> {
    return function encodedCons<B>({ cons, nil }: ChurchListArgs<A, B>): B {
        return cons(head, tail({ nil, cons }));
    }
}

const fourFiveSix = churchCons(4, churchCons(5, churchCons(6, churchNil)));

There’s a lot going on in this sample, much of which is accidental complexity:

At its essence, the above sample shows that our version of nil, churchNil, is a function that takes two functions, cons and nil, and invokes nil.

This version of cons, churchCons, takes a head value and a tail list and returns the function encodedCons. encodedCons takes two functions, cons and nil, and invokes cons. This follows from the non-recursive rules for Church encodings.

I want to go over the reasoning behind churchCons in detail because it’s a great case of types guiding implementation. encodedCons has access to a cons function with type (A, B) => B, and the value head of type A. Because it represents a cons cell, we know that encodedCons ought to use the cons function to determine its return value. But encodedCons requires an argument of type B, and there’s no value of type B in scope. encodedCons needs to produce a B. It can get a B from one of three places:

So this is the trick. We call cons, because we know we’re supposed to. cons needs an A, so we pass it the A that we have. We know it needs a B, so we pass the B that we get out of invoking tail. And tail needs nil and cons, which we receive as the arguments to encodedCons. There’s no real decisions to make; we just follow the rules and thread the types where they fit.

While the definitions of the types and functions involved are certainly more complex in the Church-encoded version, note that the code to construct lists is structurally equivalent in both approaches. The definition of fourFiveSix is no more complex than that of oneTwoThree.

Consuming lists #

As an example of what it looks like to consume our two kinds of lists, here’s code that takes a list and computes its sum:

function adtSum(list: List<number>): number {
    if (list.tag === "nil") {
        return 0;
    }
    return list.head + adtSum(list.tail);
}

function churchSum(list: ChurchList<number>): number {
    return list({
        cons: (x, y) => x + y,
        nil: () => 0
    })
}

When dealing with algebraic data types in TypeScript we have to use tags and conditional logic to differentiate the cases. To perform a recursive algorithm we make an explicit recursive call (or we convert the algorithm to an iterative form.)

When dealing with Church-encoded data the encoding differentiates the cases for us. We provide the encoding with the logic for each case and the encoding chooses which case to invoke. The encoding handles the recursive calls for us, too: we did not need to explicitly call churchSum from within its own body.

During the evaluation of churchSum, cons will be invoked recursively by list, as we implemented earlier. At each step, x will hold the current value of the list’s head, and y will hold the result of summing the tail of the list.

Ergonomics and performance of Church encodings #

There are a number of tradeoffs between the ADT and Church encodings of lists.

This comparison sounds like a lot of bad news for Church encoded lists, and to be fair, there are a lot of downsides in their practical use. That said, Church encodings can situationally provide performance benefits. Compare these functions to concatenate two lists together:

function concat<A>(left: List<A>, right: List<A>): List<A> {
    if (left.tag === "nil") {
        return right;
    }
    return cons(left.head, concat(left.tail, right));
}

function churchConcat<A>(left: ChurchList<A>, right: ChurchList<A>): ChurchList<A> {
    return function concattedList<B>({ cons, nil }: ChurchListArgs<A, B>): B {
        return left({ cons, nil: () => right({ cons, nil })});
    }
}

The concat function defined on our ADT List type creates a new list by wrapping its second argument (right: List<A>) in new cons cells, copying the values from left. If the first list provided to concat has N elements, then N new cells will be created. This means that the runtime of concat is linear in the size of its first argument. There are other ways we could have implemented concat, such as tail-recursively or iteratively, but so long as we’re working with immutable data no alternatives can run in faster than linear time.

The churchConcat function defined on our Church encoding runs in constant time. concattedList is a ChurchList; it is a function which takes cons and nil as arguments and invokes them with the proper encoded values. Recall that invoking a Church-encoded list will cause the list to recurse down to the root nil node and then combine the values it contains using the provided cons function. concattedList does this by first recursing over left (by invoking left as a function) and then, when nil is found in left, recursing over right (by invoking right as a function). At no point is any copying needed. churchConcat thus both runs in constant time and produces a concattedList value which only imposes a constant amount of overhead, regardless of the size of the involved lists.

For me, converting a linear-time operation to a constant-time one feels magical. By reimagining the way we represent our data we’ve completely changed the performance of basic operations. That said, I do not know of any good general heuristics for when Church-encoded data types are more or less performant or ergonomic than directly-encoded ADTs. They are two very distinct approaches, which will be beneficial in different cases.

Equivalence of Church and ADT encodings #

Church encodings represent data as folds. It may be instructive to compare the implementation of churchSum above to the related function for performing this operation on arrays:

function arraySum(arr: number[]): number {
    return arr.reduce(
    	(x, y) => x + y,
	0);
}

The logic is almost identical, though the execution differs. reduce is a “left fold”, and collapses the array from front to back. Our Church encoding is a “right fold”, and collapses the list from back to front. In both cases we have followed the functional programming maxim “separate the ‘what’ from the ‘how’”. To consume a sequence of values we need only specify what logic is used to combine two values. How this logic is applied (by iterating or recursing over the sequence) is hidden by the implementation.

At first blush, one might expect representing a list as a right fold to be limiting. It’s challenging to implement certain algorithms using Church encodings. For example, consider writing a function which returns the third value in a list, or a default value if the list has length less than 3:

function thirdOrDefault<A>(list: ChurchList<A>, dflt: A): A {
    // ?????
};

This is quite a brainteaser. It is possible, though. In fact, any function which can be written on the ADT representation can be implemented on a Church-encoded representation. One way to prove this is to show that both representations contain the same information, which we can do by writing functions that turn them into each other:

function churchEncode<A>(list: List<A>): ChurchList<A> {
    return function encodedList<B>({ cons, nil }: ChurchListArgs<A, B>): B {

        function recursive(list: List<A>): B {
            if (list.tag === "nil") {
                return nil();
            }
            return cons(list.head, recursive(list.tail));
        }

        return recursive(list);
    }
}

function churchDecode<A>(list: ChurchList<A>): List<A> {
    return list<List<A>>({
        cons: (head, tail) => ({ tag: "cons", head, tail }),
        nil: () => ({ tag: "nil" })
    })
}

If we do not wish to take advantage of the different performance characteristics of Church-encoded lists, any function which operates on them has the option to trade performance for ease by converting the list to an ADT before processing it.2

Scott encodings #

Scott encodings are an alternative way to encode recursive ADTs. The first two rules for performing the encoding (covering the non-recursive cases) are the same as with Church encodings.3 The third rule for Scott encodings are that recursive references in the definition of the ADT should be replaced with recursive references to the Scott encoding.

As an example, here is the Scott encoding of our List ADT:

type ScottList<A> = <B>(choices: {
    cons: (head: A, tail: ScottList<A>) => B,
    nil: () => B
}) => B;

This type definition is the same as that of ChurchList with one exception: the argument tail has the type ScottList<A> rather than type B.

Here is the rest of the implementation of Scott-encoded lists:

type ScottListArgs<A, B> = {
    nil: () => B,
    cons: (head: A, tail: ScottList<A>) => B
};

const scottNil: ScottList<never> =
    <B>({ nil }: ScottListArgs<never, B>): B => nil();

function scottCons<A>(head: A, tail: ScottList<A>): ScottList<A> {
    return function<B>({ cons }: ScottListArgs<A, B>): B {
        return cons(head, tail);
    }
}

const sevenEightNine = scottCons(7, scottCons(8, scottCons(9, scottNil)));

This implementation is much the same as that of Church encodings. The same trick with the use of never applies. We can also see by the definition of sevenEightNine that the interface for building lists has the same structure as when working with ADTs or Church encodings.

In our Church encoding, churchCons ran recursively when invoked, via a call to its tail argument. With Scott encodings no such recursion occurs. When a Scott-encoded list is invoked it provides the data it contains to the callback it’s provided, and nothing more. Personally I find this makes Scott encodings easier to write and reason about.

Let’s look at one of the same functions we wrote above, this time implemented on Scott encodings:

function scottSum(list: ScottList<number>): number {
    return list({
        cons: (head, tail) => head + scottSum(tail),
	nil: () => 0
    });
}

Ergonomically, this sum function sits somewhere between the ADT sum and Church-encoded churchSum functions. Like the functions on ADTs, scottSum is explicitly recursive and must manually invoke itself. Like churchSum, scottSum does not need explicit control flow or type narrowing, and instead declaratively specifies the logic for each case via labelled functions.

I think of Scott encodings as a form of shallow pattern matching, i.e. pattern matching without support for nesting constructors in a single pattern. The Scott encoding of a data type takes one function per variant of that data type and uses said function to “destructure” the fields corresponding to that variant. Declaratively grouping logic by the constructors of a data type and extracting the constructor’s arguments is at the core of pattern matching in ML-family languages. (This can be contrasted with “structural pattern matching”, a less consistent way of coupling algorithms’ logic to the internal structure of ad-hoc objects.)

Scott encodings and stack safety #

The implementation of scottSum above is recursive and can blow the stack on very large lists. This is not an inherent limitation to Scott encodings. Here’s an example of how the same operation might be written using mutable variables and loop-based iteration:

function scottSumIterative(list: ScottList<number>): number {
    let sum = 0;
    let done = false;
    let l = list;

    while (!done) {
        l({
	    cons: (head, tail) => {
	        sum += head;
		l = tail;
		return undefined;
	    },
	    nil: () => {
	        done = true;
	    }
	})
    }

    return sum;
}

The iterative implementation is much less ergonomic than the recursive one but it won’t build up stack frames with each step of evaluation. This change has made us lose the benefits of a declarative, pattern-match-esque interface. To try to win these back, we can define a helper function which gives us some of the benefits of both worlds:

function foldlScottList<A, B>(list: ScottList<A>, accumulator: B, consFn: (acc: B, a: A) => B): B {
    let acc = accumulator;
    let done = false;
    let l = list;

    while (!done) {
        l({
	    cons: (head, tail) => {
	        acc = consFn(acc, head);
		l = tail;
		return undefined;
	    },
	    nil: () => {
	        done = true;
	    }
	})
    }

    return acc;
}

const summed = foldlScottList(sevenEightNine, 0, (x, y) => x + y);

foldlScottList encapsulates the recursion over lists, and allows us to write algorithms with similar ergonomics as doing so via Church-encoded lists. The semantics are not the same: Church-encoded lists express right folds, from the nil node of the list back up to the head, while foldlScotList expresses a left fold, from the head of the list down to the nil node. The two are equivalent only when the function for processing cons nodes is commutative. If we want to express a right fold without building up stack frames we can do so as well:

function foldlScottList<A, B>(list: ScottList<A>, accumulator: B, consFn: (acc: B, a: A) => B): B {
    let acc = accumulator;
    let done = false;
    let l = list;

    while (!done) {
        l({
	    cons: (head, tail) => {
	        acc = consFn(acc, head);
		l = tail;
		return undefined;
	    },
	    nil: () => {
	        done = true;
	    }
	})
    }

    return acc;
}

const summed = foldlScottList(sevenEightNine, 0, (x, y) => x + y);

This function could also be written by using our list ADT to build up the internal copy of the data rather than an array, if we wanted to maintain more of a sense of conceptual purity. Note that avoiding building stack frames has come with a cost: We now have to copy the array over, doubling our space requirements, as well as iterate over the array a second time.

Performance characteristics of Scott encodings #

Here’s another one of our examples defined on Scott-encoded lists, the operation for concatenating two lists:

function scottConcat<A>(left: ScottList<A>, right: ScottList<A>): ScottList<A> {
    return function concatted<B>({ cons, nil }: ScottListArgs<A, B>): B {
        return left({
            cons: (head, tail) => cons(head, scottConcat(tail, right)),
            nil: () => right({ cons, nil })
        });
    };
}

Concatenation returns a new ScottList, the function concatted. Behaviorially, concatted should take the functions cons and nil, and call cons if the concatenation contains any elements (i.e., if both lists are not empty) and nil otherwise.

scottConcat has different performance characteristics from those of the concat and churchConcat functions we saw previously. scottConcat returns a single function in constant time, like churchConcat, but now there is an additional overhead when consuming the created lists. Every time concatted is called it will invoke scottConcat again, adding a constant cost. This means that if we consume the entire concatenated list, the total runtime cost will be linear in the length of the first list. This is the same asymptotic behavior as our concat function on ADTs, except in the case of the Scott encodings the cost is paid lazily. We only pay the overhead for the list elements we actually use, which can be a significant speedup if we only consume a small percentage of the length of the created list. Note also that the lazy behavior means that concatenating ScottLists only adds a small constant overhead in the program’s space consumption, whereas the additional space consumption of concat is linear in the size of the first list.

As with Church encodings, I do not know of any heuristics for when the performance tradeoffs of Scott encodings are beneficial. Whether or not they cause a significant change in the resource consumption of a program will depend on specific details of the program’s behavior. That said, laziness is not just about performance. Lazy data structures also open the door to more expressive programs.

Infinite data structures with Scott Encodings #

scottConcat shows that we can create the tail of our list on the fly each time do a match. We can use that to our advantage by producing data structures of any size, including infinite ones. Take this function as an example:

function count(start: number, increment: number): ScottList<number> {
    return function counting<B>({ cons, nil }: ScottListArgs<number, B>): B {
        return cons(start, count(start + increment, increment));
    }
}

const counter = count(0, 1);

const zero = counter({
    cons: (num, tail) => num,

    nil: () => -999 // some number to satisfy typechecker
});

const one = counter({
    cons: (num, tail) => tail({
        cons: (num, tail) => num,
        nil: () => -999
    }),
    nil: () => -999
});

count produces a list of numbers which can be consumed by matching on the list. one shows what it looks like to do a nested match, while zero shows a simple match.

JavaScript provides built-in functionality for producing and consuming lazy/infinite one-dimensional data in the form of iterators, meaning that lazy infinite lists are not exactly a “killer feature”. However, there are still a couple of benefits here:

Algorithms which consume infinite data structures face the dangers of unpredictable performance or nontermination, but the ability to write them at all is still important.

Equivalence of Church and Scott encodings #

Church encodings and Scott encodings of finite data are isomorphic; anything we can express with one we can express with the other. This is most easily demonstrated by writing functions which convert them to and from the algebraic data type that they encode. The conversion functions for Church-encoded lists was shown above. Here are the conversion functions for Scott-encoded lists:

function scottEncode<A>(list: List<A>): ScottList<A> {
    return function encodedList<B>({ cons, nil }: ScottListArgs<A, B>): B {
        if (list.tag === "nil") {
            return nil();
	}
	return cons(list.head, scottEncode(list.tail));
    }
}

function scottDecode<A>(list: ScottList<A>): List<A> {
    return list({
        cons: (head, tail) => cons(head, scottDecode(tail)),
	nil: () => nil
    });
}

It is also possible to write conversion functions directly from ChurchList to ScottList and back, without any intermediate steps. As with many functions on Church encodings, this implementation is a fun brainteaser. It is left as an exercise for the reader.

Conclusion #

If you have made it through the length of this post I thank you. I consider both of these encodings to be very important and powerful concepts. Scott encodings specifically form the conceptual basis for object algebras, which are a means of solving the expression problem in object oriented languages, as well as provide a way to simulate GADTs in TypeScript. I plan on writing on both of these topics in the future.

All tools are situational, and these encodings are no exception. Still, I find great value in having as large a conceptual toolbox as possible, and I hope that this post has helped to expand yours.

All code samples in this post are released into the public domain under a Creative Commons 0 license. Code samples and full license text may be found here.

  1. It’s been a year since I wrote the previous post and I’m not completely satisfied with the way I explained things in it. I’m hoping the new explanations are more clear and that the differences between the two posts are not too distracting. ↩

  2. There are ways of writing this algorithm without first converting the list to an ADT, but I consider them to be of theoretical interest and they are beyond the scope of this post. Information on this topic may be found in the paper “Programming in the λ-Calculus: From Church to Scott and Back” by Jan Martin Jansen. ↩

  3. Note that this means that the Church encoding and Scott encoding of non-recursive algebraic data types are identical. ↩

Related Posts