Recursive Types
Lets ask everyone's favorite AI about recursive types:
Q: How would you define recursive types?
ChatGPT: Recursive types are types that can contain values of the same type. This selfreferential structure allows for the creation of complex data structures. Recursive types are commonly used in computer programming languages, particularly in functional programming languages, to represent recursive data structures such as trees or linked lists.
Wow! And since Motoko provides an implementation of a linked list, a common data structure in programming languages, we will use that as an example.
List
Consider the following type declaration in the List module in the Base Library:
type List<T> = ?(T, List<T>);
A generic type List<T>
is declared which takes one type parameter T
. It is a type alias for an option of a tuple with two elements.
The first element of the tuple is the type parameter T
, which could take on any type during the construction of a value of this List<T>
type by providing a type argument.
The second element of the tuple is List<T>
. This is where the same type is used recursively. The type List<T>
contains a value of itself in its own definition.
This means that a List
is a repeating pattern of elements. Each element is a tuple that contains a value of type T
and a reference to the tail List<T>
. The tail is just another list element of the same type with the next value and tail for the next value and so on...
Null list
Since our List<T>
type is an option of a tuple, a value of type <List<T>
could be null
as long as we initialize a value with a type argument for T
:
let list : List<Nat> = null;
Our variable list
has type List<Nat>
(a list of Nat
values) and happens to have the value null
.
The 'tail' of a list
The shortest list possible is a list with exactly one element. This means that it does not refer to a tail for the next value, because there is no next value.
let list1 : List<Nat> = ?(0, null);
The second element in the tuple, which should be of type List<T>
is set to null
. We use the null list as the second element of the tuple. This list could serve as the last element of a larger list.
The 'head' of a list
If we wanted to add another value to our list list1
we could just define another value of type List<T>
and have it point to list1
as its tail:
let list2 : List<Nat> = ?(1, list1);
list2
is now called the head of the list (the first element) and list1
is the tail of our 2element list.
We could repeat this process by adding another element and using list2
as the tail. We could do this as many times as we like (within memory limits) and construct a list of many values.
Recursive functions
Suppose we have a list bigList
with many elements. This means we are presented with a head of a list, which is a value of type <List<T>
.
There several possibilities for this head value:

The head value
bigList
could be the null list and in that case it would not contain any values of typeT
. 
Another possibility is that the head value
bigList
has a value of typeT
but does not refer to a tail, making it a single element list, which could be the last element of a larger list. 
Another possibility is that the head value
bigList
contains one value of typeT
and a tail, which is another value of typeList<T>
.
These possibilities are used in the last<T>
function of the List module. This function is used to retrieve the last element of a given list:
func last<T>(l : List<T>) : ?T {
switch l {
case null { null };
case (?(x, null)) { ?x };
case (?(_, t)) { last<T>(t) };
};
};
We have a generic function List<T>
with one type parameter T
. It takes one argument l
of type List<T>
, which is going to be a head of some list.
If the function finds a last element, it returns an option of the value ?T
within it. If there is no last element it returns null
.
In the function body, we switch on the argument l : List<T>
and are presented with the three possibilities described above.

In the case that
l
is the null list, we returnnull
because there would not be a last element. 
In the case that
l
is a list element?(x, null)
, then we are dealing with the last element because there is not tail. We bind the namex
to that last value by pattern matching and return an option?x
of that value as is required by our function signature. 
In the case that
l
is a list element?(_, t)
, then there is a tail with a next value. We use the wildcard_
because we don't care about the value in this element, because it is not the last value. We do care about the tail for which we bind the namet
. We now use the functionlast<T>
recursively by calling it again inside itself and provide the tailt
as the argument:last<T>(t)
. The function is called again receiving a list which it now sees as a head that it can switch on again and so on until we find the last element. Pretty cool, if you ask me!