The Church and Scott Encodings of Algebraic Data Types
Recursive data as pure functions
02 Jan 2022Previously I wrote about the Church encoding of nonrecursive 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
 The Church encoding of linked lists
 Consuming lists
 Ergonomics and performance of Church encodings
 Equivalence of Church and ADT encodings
 Scott encodings
 Scott encodings and stack safety
 Performance characteristics of Scott encodings
 Infinite data structures with Scott encodings
 Equivalence of Church and Scott encodings
Linked lists as an algebraic data type #
Linked lists are the bread and butter of functional programming. Here is an ADTstyle 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 nonrecursive ADTs. Here is a restated^{1} version of them, along with an additional third rule which covers recursive cases:
 To Churchencode an algebraic data type with multiple variants, create a higherorder 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.
 To Churchencode a product type, create a higherorder function which takes a second function,
f
, as an argument. Thisf
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 tof
and return the result.  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 Churchencoding our list ADT.
First, working out the nonrecursive 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 Churchencoded 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 tochurchNil
enables us to usechurchNil
in lists of different types. For allA
,ChurchList<A>
is a supertype ofChurchList<never>
. Whether we’re making a type ofChurchList<number>
,ChurchList<string>
, etc., we can use the samechurchNil
value to build the data structure.  I’ve introduced the convenience type
ChurchListArgs
in order to reduce the verbosity ofchurchNil
andchurchCons
. 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 nonrecursive 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 aB
, but we shouldn’t use this as our source.encodedCons
represents a cons cell, not a nil value.cons
returns aB
, but it also requires aB
. We can’t use it to get aB
from thin air.tail
is aChurchList
, meaning that it is a generic function which can produce aB
. All we have to do to produce aB
is to give itnil
andcons
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 Churchencoded 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 Churchencoded 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 ofchurchCons
you will see that it is not possible to writechurchCons
in a tailrecursive way.  We could write a nonrecursive version of
adtSum
, which uses looping constructs to avoid building up stack frames. This is not true forchurchSum
.  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
thanchurchSum
. 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 tailrecursively 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 Churchencoded 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 lineartime operation to a constanttime 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 Churchencoded data types are more or less performant or ergonomic than directlyencoded 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 Churchencoded 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 Churchencoded 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 nonrecursive 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 Scottencoded 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 Scottencoded 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 Churchencoded 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 MLfamily languages. (This can be contrasted with “structural pattern matching”, a less consistent way of coupling algorithms’ logic to the internal structure of adhoc 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 loopbased 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, patternmatchesque 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 Churchencoded lists. The semantics are not the same: Churchencoded 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 Scottencoded 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 builtin functionality for producing and consuming lazy/infinite onedimensional 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 Churchencoded lists was shown above. Here are the conversion functions for Scottencoded 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.

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. ↩

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. ↩

Note that this means that the Church encoding and Scott encoding of nonrecursive algebraic data types are identical. ↩