Persistent data structures thanks to recursive type aliases
7 min read Β·
Itβs well known that mutability is evil and often troublesome. But, itβs also a fact that mutable data structures are, in some cases, more straightforward to implement and have better performance. Sometimes, you can go with it and be completely fine, but other times immutability is required. Letβs focus on arrays for now. What would you do if you want to append or prepend an item to the list in an immutable way? A shallow copy? A deep copy (god forbid)? These operations are expensive. They have greater asymptotic time complexity β O(n), and what we want is O(1). In this article, Iβm going to show a simple data structure that achieves that.
Do I get your attention now? So, letβs start!
Persistent vs immutable data structure π
Firstly, I need to confess. For quite a lot of time, I thought that a persistent structure is just an immutable structure. Pretty lame. Then I got to know that the data structure is persistent when it preserves previous versions of itself when itβs modified. Itβs like it never forgets who it was. They are, in fact, effectively immutable, but it doesnβt work the other way around. Immutable data structures donβt have to be necessarily persistent.
You can read more about it here.
Meet Cons List
And here it is. Star of the show π
Firstly, letβs focus on what cons means. Soβ¦ itβs a function. Whatβs more, itβs the fundamental function in many programming languages. Especially in Lisp dialects. It takes two objects or pointers to the objects x and y and constructs object in the memory holding x and y. When it comes to cons lists, it takes a value, and the cons list and constructs brand new object out of it, which is also cons list. You may have seen this before:

1::[2]: ML, Scala, F# and Elm

1:[2]: Haskell

(cons 1 2): Lisp and itβs dialects
The above are the constructors for the list data structure. cons list is also called a linked list, which I guess, is a more recognizable name.
We can visualize cons list in the following way:
ββββββββββββββ ββββββββββββββ ββββββββββββββ
β 1  tail β βββ 2  tail β βββ 3  null β
ββββββββββββββ β ββββββββββββββ β ββββββββββββββ
βββββββββ βββββββββ
a linked list of (1, 2, 3)
How is it persistent?
There were a few words about persistent data structures, so you may wonder if cons list is persistent. Yes, it is! Letβs see how.
Letβs say we have a cons list β xs, and we want to cons an element to it. It results in a brand new list ys, and what you can notice is that items from xs are now shared between xs and ys. Thus the list xs hasnβt been modified, and itβs a part of the new list ys.
xs ys
βββββββ βββββββ
β 3 β β 4 β
βββββββ βββββββ
βββββββ xs β
β 2 β cons 4 xs β ββββ
βββββββ βββββββ
βββββββ β 3 β
β 1 β βββββββ
βββββββ βββββββ
β 2 β
βββββββ
βββββββ
β 1 β
βββββββ
How it looks in TypeScript 3.7
I can write the type of cons list in the following way and it perfectly works thanks to recursive type aliases introduced in TypeScript 3.7.
ts
export type ConsList<T> = null  readonly [T, ConsList<T>];
ts
export type ConsList<T> = null  readonly [T, ConsList<T>];
Before 3.7, I would get the following error:
Type alias βConsListβ circularly references itself. ts(2456)
Long story short, type aliases needed to be eagerly built, so you couldnβt have on the right side the same thing as on the left side because the compiler would try to substitute the former with the later and then the later with the former and so onβ¦ You can read more about it on TypeScript 3.7 announcement.
Functions operating on ConsList
Okay, so we already have some overview of what cons list is. Now itβs time to see what we can do with it and how to make it useful. cons list may come as an immutable replacement for Array. That means we can expect it to have some of its functionalities. Letβs add some!
 Prepend element to list
ts
function cons<T>(h: T, t: ConsList<T>): ConsList<T> {return [h, t];}
ts
function cons<T>(h: T, t: ConsList<T>): ConsList<T> {return [h, t];}
 Extract head and tail from the list
ts
function head<T>(xs: ConsList<T>): T {if (!xs) {throw new Error("can't take head of empty ConsList");}return xs[0];}function tail<T>(xs: ConsList<T>): ConsList<T> {if (!xs) {throw new Error("can't take tail of empty ConsList");}return xs[1];}
ts
function head<T>(xs: ConsList<T>): T {if (!xs) {throw new Error("can't take head of empty ConsList");}return xs[0];}function tail<T>(xs: ConsList<T>): ConsList<T> {if (!xs) {throw new Error("can't take tail of empty ConsList");}return xs[1];}
 Map over it.
Note: cons list with map is no longer persistent. Itβs just immutable. To make it persistent, we would need to memorize previous versions. Iβll skip it for now.
ts
function map<A, B>(xs: ConsList<A>, f: (a: A) => B): ConsList<B> {let res: ConsList<B> = null;while (xs) {const [head, tail] = xs;res = [f(head), res];xs = tail;}return reverse(res);}
ts
function map<A, B>(xs: ConsList<A>, f: (a: A) => B): ConsList<B> {let res: ConsList<B> = null;while (xs) {const [head, tail] = xs;res = [f(head), res];xs = tail;}return reverse(res);}
 Reduce it
ts
function reduce<T, R = T>(xs: ConsList<T>,reducer: (acc: R, val: T) => R,initialValue: R): R {while (xs) {const [head, tail] = xs;initialValue = reducer(initialValue, head);xs = tail;}return initialValue;}
ts
function reduce<T, R = T>(xs: ConsList<T>,reducer: (acc: R, val: T) => R,initialValue: R): R {while (xs) {const [head, tail] = xs;initialValue = reducer(initialValue, head);xs = tail;}return initialValue;}
 Construct a new cons list from Array and vice versa
ts
const of = <T>(...xs: T[]): ConsList<T> => {let res: ConsList<T> = null;for (let i = xs.length  1; i >= 0; i) {res = cons(xs[i], res);}return res;};function toArray<T>(xs: ConsList<T>) {return reduce<T, T[]>(xs,(a, v) => {a.push(v);return a;},[]);}
ts
const of = <T>(...xs: T[]): ConsList<T> => {let res: ConsList<T> = null;for (let i = xs.length  1; i >= 0; i) {res = cons(xs[i], res);}return res;};function toArray<T>(xs: ConsList<T>) {return reduce<T, T[]>(xs,(a, v) => {a.push(v);return a;},[]);}
 Reverse it
ts
function reverse<T>(xs: ConsList<T>): ConsList<T> {return reduce(xs, (acc, v) => cons(v, acc), null as ConsList<T>);}
ts
function reverse<T>(xs: ConsList<T>): ConsList<T> {return reduce(xs, (acc, v) => cons(v, acc), null as ConsList<T>);}
 Concat two cons lists
ts
function concat<T>(xs: ConsList<T>, ys: ConsList<T>): ConsList<T> {return xs ? cons(head(xs), concat(tail(xs), ys)) : ys;}
ts
function concat<T>(xs: ConsList<T>, ys: ConsList<T>): ConsList<T> {return xs ? cons(head(xs), concat(tail(xs), ys)) : ys;}
So far, so good. Iβll stop now. Itβs pretty powerful already πͺ
Reallife use cases π
As you might have noticed, the cons list gives us rapid access to the first element of the list. That means we can prepend to the list and take the first element from it extremely fast. As a matter of fact, a stack (or lastinfirstout queue) is the data structure that is based on these two operations. Push to the stack is just doing cons on the cons list, and pop is extracting the head. In common stack nomenclature it would go like that:
const push = cons;
const pop = tail;
const peek = head;
Great! We have stack done effortlessly. Without any modifications and without any new code. That one was easy, now it is time for something more complex. Firstinfirstout queue. The structure when we are taking elements from the front and pushing to the end. So, we need rapid access to both the first and last element of the list. Itβs pretty straightforward with mutations and pointers. We would only need to maintain two pointers for the first and the last item. But we donβt have mutations. We have our cons list instead!
There was this smart guy named Chris Okasaki, who came up with a clever way how to implement an effective, immutable FIFO quque, using a pair of two cons lists (front, back). They are representing, respectively, the front and the back of the queue. But the back is reversed, so the head of this list is the last element of the queue.
ts
type Queue<T> = {front: ConsList<T>;back: ConsList<T>;};
ts
type Queue<T> = {front: ConsList<T>;back: ConsList<T>;};
Key points of this structure:
 When we want to push an item to the queue, we need to prepend it to the back
 When we want to pop an item, we need to extract the head from front
When we keep pushing elements to the queue, they all will drift into the back list. Letβs say we pushed one after another numbers from 1 to 5. That means our structure would look somehow like this:
ts
{ front: null, back: [5, [4, [3, [2, [1, null]]]]]}
ts
{ front: null, back: [5, [4, [3, [2, [1, null]]]]]}
The front list is empty. So how can we take an element out of it? Thatβs the best part. We do a rotation. That means we take the back list, reverse it, attach it as the new front and make back empty.
Hereβs the whole implementation:
ts
const empty = <T>(): Queue<T> => ({front: null,back: null,});const isEmpty = (queue: Queue<unknown>) => (queue.front  queue.back) === null;const enqueue = <T>(x: T, { front, back }: Queue<T>) => ({front,back: ConsList.cons(x, back),});const dequeue = <T>(queue: Queue<T>): [T  null, Queue<T>] => {const { front, back } = queue;if (front) {const [value, newFront] = front;return [value, { back, front: newFront }];}if (back) {return dequeue({back: null,front: ConsList.reverse(back),});}return [null, queue];};
ts
const empty = <T>(): Queue<T> => ({front: null,back: null,});const isEmpty = (queue: Queue<unknown>) => (queue.front  queue.back) === null;const enqueue = <T>(x: T, { front, back }: Queue<T>) => ({front,back: ConsList.cons(x, back),});const dequeue = <T>(queue: Queue<T>): [T  null, Queue<T>] => {const { front, back } = queue;if (front) {const [value, newFront] = front;return [value, { back, front: newFront }];}if (back) {return dequeue({back: null,front: ConsList.reverse(back),});}return [null, queue];};
When not to use cons list
 Itβs not a replacement to Array.
 Itβs not a random access list (thus I didnβt even implement it), so if you want fast random access then better use Array.
Benchmarks βοΈ
You may wonder if using cons lists pays off somehow. In fact, it does! I did some benchmarks comparing operations on Array and on cons list and the results are thrilling! Hereβs the gist with benchmarks.
Mutable operations vs cons
Opeation  ops/s 

array.unshift(50)  99953.939 
array.push(50)  70675.276 
cons(50, list)  5822999.798 
Immutable operation vs cons
Operation  ops/s 

[50, β¦array]  12680.588 
cons(50, list)  5485947.933 
Array.prototype.map vs map
Operation  ops/s 

array.map(x => x * 2)  4389.837 
map(list, x => x * 2)  662.805 
I hope the above benchmarks speak for themselves. Itβs kind of funny because I expected a cons list map to be a little bit slower, but it surprisingly fast. If you know why let me know π