# The Church and Scott Encodings of Algebraic Data Types

### Recursive data as pure functions

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.

### 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:

We can use these to create linked lists:

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

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:

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`:

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

We can create functions for building `ChurchList` values:

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

• Using `never` as the type argument to `churchNil` enables us to use `churchNil` in lists of different types. For all `A`, `ChurchList<A>` is a supertype of `ChurchList<never>`. Whether we’re making a type of `ChurchList<number>`, `ChurchList<string>`, etc., we can use the same `churchNil` value to build the data structure.
• I’ve introduced the convenience type `ChurchListArgs` in order to reduce the verbosity of `churchNil` and `churchCons`. We have to explicitly declare the type of the arguments in all of the functions shown above because TS will not infer them.

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:

• `nil` returns a `B`, but we shouldn’t use this as our source. `encodedCons` represents a cons cell, not a nil value.
• `cons` returns a `B`, but it also requires a `B`. We can’t use it to get a `B` from thin air.
• `tail` is a `ChurchList`, meaning that it is a generic function which can produce a `B`. All we have to do to produce a `B` is to give it `nil` and `cons` functions of the appropriate type.

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:

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.

• The Church encoding is more syntactically lightweight, and (in my mind, in this case) makes the intent of the logic more clear. This depends strongly on what kind of algorithm is being implemented.
• The ADT approach requires explicit control flow and understanding of TypeScript’s type narrowing to implement.
• The implementation of `churchSum` is recursive. If it is passed a list of tens of thousands of items, a stack overflow will result.
• The ADT approach is tail recursive. In practice this means very little, but in a fantasy world where browsers were willing to implement proper tail calls per the ECMAScript specification or were to adopt the syntactic tail calls proposal, it would be possible to write a recursive version of `adtSum` which does not blow the stack. If you go back to the implementation of `churchCons` you will see that it is not possible to write `churchCons` in a tail-recursive way.
• We could write a non-recursive version of `adtSum`, which uses looping constructs to avoid building up stack frames. This is not true for `churchSum`.
• Developers who are familiar with imperative programming (including most JavaScript and TypeScript developers) usually find it easier to reason about the runtime behavior of `adtSum` than `churchSum`. Reasoning about either of them is a skill which can be learned with practice.

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:

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:

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:

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:

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:

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:

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:

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:

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:

`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:

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:

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 `ScottList`s 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:

`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:

• JavaScript iterators are stateful, so there is no way to “replay” a previously passed segment of values. Proper lists, whether represented as ADTs or Scott encodings, allow you to restart consumption from any point which you still posess a reference to.
• Scott encodings are not limited to lists, and so one could produce for example an infinite tree.

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:

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.