Simulating a recursive linked List data type (a la Haskell, PureScript, etc.) in TypeScript

List.ts

// A list is either empty (represented by the `Nil` constructor) or non-empty, in
// which case it consists of a head element, and another list (represented by the
// `Cons` constructor).
//
// data List a = Nil | Cons a (List a)

interface Nil {
    readonly tag: 'Nil'
}

interface Cons<A, ListOfA extends List<A>> {
    readonly tag: 'Cons'
    readonly head: A
    readonly tail: ListOfA
}

interface List_<A> {
    readonly tag: 'List'
    readonly values: Cons<A, List<A>> // this is the most important part
}

type List<A> = Nil | List_<A>

// we are simulating tagged unions or "algebraic data types" from other languages
// see the Discriminated Unions section here:
// https://www.typescriptlang.org/docs/handbook/advanced-types.html

TypeScript Playground links

Tiny: https://tinyurl.com/y99kha6q

Full: https://www.typescriptlang.org/play/#src=%2F%2F%20A%20list%20is%20either%20empty%20(represented%20by%20the%20%60Nil%60%20constructor)%20or%20non-empty%2C%20in%0D%0A%2F%2F%20which%20case%20it%20consists%20of%20a%20head%20element%2C%20and%20another%20list%20(represented%20by%20the%0D%0A%2F%2F%20%60Cons%60%20constructor).%0D%0A%2F%2F%0D%0A%2F%2F%20data%20List%20a%20%3D%20Nil%20%7C%20Cons%20a%20(List%20a)%0D%0A%0D%0Ainterface%20Nil%20%7B%0D%0A%20%20%20%20readonly%20tag%3A%20'Nil'%0D%0A%7D%0D%0A%0D%0Ainterface%20Cons%3CA%2C%20ListOfA%20extends%20List%3CA%3E%3E%20%7B%0D%0A%20%20%20%20readonly%20tag%3A%20'Cons'%0D%0A%20%20%20%20readonly%20head%3A%20A%0D%0A%20%20%20%20readonly%20tail%3A%20ListOfA%0D%0A%7D%0D%0A%0D%0Ainterface%20List_%3CA%3E%20%7B%0D%0A%20%20%20%20readonly%20tag%3A%20'List'%0D%0A%20%20%20%20readonly%20values%3A%20Cons%3CA%2C%20List%3CA%3E%3E%20%2F%2F%20this%20is%20the%20most%20important%20part%0D%0A%7D%0D%0A%0D%0Atype%20List%3CA%3E%20%3D%20Nil%20%7C%20List_%3CA%3E%0D%0A%0D%0A%2F%2F%20we%20are%20simulating%20tagged%20unions%20or%20%22algebraic%20data%20types%22%20from%20other%20languages%0D%0A%2F%2F%20see%20the%20Discriminated%20Unions%20section%20here%3A%0D%0A%2F%2F%20https%3A%2F%2Fwww.typescriptlang.org%2Fdocs%2Fhandbook%2Fadvanced-types.html

@joshburgess The only thing that comes to mind is that we can avoid this name collision by introducing a separate constructor (in exactly the same way global JavaScript objects like Object or Array are defined).

interface Nil {
  readonly tag: 'Nil';
}

interface Cons<T, U extends List<T>> {
  readonly tag: 'Cons';
  readonly head: T,
  readonly tail: U;
}

interface List<T> {
  readonly tag: 'List';
  readonly values: Cons<T, List<T>>;
}

interface ListConstructor {
  new <T>(): Nil | List<T>;
}

declare const List: ListConstructor;

Then we can use it like this:

declare function isNil(argument: unknown): argument is Nil;

const numbers = new List<number>();

isNil(numbers)
  ? 42
  : numbers.values.head;

Although it's hardly an improvement.