30/01/2025 8 Minutes read

The Useless Type Array Sorter in TypeScript

The stupid idea came back

To understand this article, you need to read the first part of the article: The Useless Type Calculator in Typescript

Through space and time, when you never wait for their comeback, they arrive with the future. Not the future you wanted, clearly not the one with flying cars and toaster robots preparing your delicious meal, but the one where a human pushed their stupid idea too far. Really too far.

So, I have a new job. It’s cool, and I have some time and motivation to work on my side projects. But instead of working on something useful, something that will help someone do a specific task I don’t know, I prefer to dig up my truly useless project: the good ol’ calculator made only with types and without any numbers.

The main problem is figuring out what I can do with this project. I did something funny (yes, a strange notion of fun), but is there something funnier? Is there something that can be more ridiculous than computing numbers with types? Can we level up our stupidity to go higher than the stratosphere?

Of course, we can.

Here comes part two of this project.

We will sort an array of numbers.

Without numbers.

Only with types.

An image from Grand Theft Auto of a man saying : “Ah shit, here we go again !

The rules

The challenge is pretty simple:

  • you start with our two booleans.
type BZero = false;
type BOne = true;
  • you can’t use any number. However, you can use the numbers and operations created in the first part. I defined a simple structure with them:
type D = {  
Zero: Zero,
One: One,
Two: Add<One, D['One']>,
Three: Add<One, D['Two']>,
Four: Add<One, D['Three']>,
Five: Add<One, D['Four']>,
Six: Add<One, D['Five']>,
Seven: Add<One, D['Six']>,
Eight: Add<One, D['Seven']>,
Nine: Add<One, D['Eight']>,
}
  • you have an array, and you have to sort it.
type TestArrayToSort = [D['Six'], D['One'], D['Five'], D['Three'], D['Eight'], D['One']];

// The result to obtain
type Result = [D['One'], D['One'], D['Three'], D['Five'], D['Six'], D['Eight']];
  • it’s a TypeScript types-only challenge. So you can’t use type guards or any code using JavaScript.

Happy coding!

An image from The Office of a woman behind a desk screaming “Let’s go !”

Ok, I know you’re here to read the solution.

An image from The Office of a man winking to the camera

The solution

To code this algorithm, I‘ve decided to … create conditions and control flow structures like any programming language.

An image zooming on the face of a turtle in a animation movie. The turtle is doing a surprised expression (like “What ???”).
You.

Comparison operators and conditions

type EQ<A extends TypeNumber, B extends TypeNumber> =  
A extends B
? true
: false;

The EQ operator is pretty obvious. We're just checking A and B have the same type.

type GTE<A extends TypeNumber, B extends TypeNumber> =  
A extends [...infer _, ...B]
? true
: false;

type LTE<A extends TypeNumber, B extends TypeNumber> =
B extends [...infer _, ...A]
? true
: false;

Small reminder: the infer keyword in a conditional type will retrieve a type into a type variable. In this case, …infer _ will retrieve the type of what’s left by the …B type in the array. (infer keyword documentation)

The main idea behind GTE is to check if our number A contains the number B (the same technique used to code Divide in the first part). It feels a bit counterintuitive, but you can read the syntax as is A equals to (something + B) ?.

By swapping A and B, you get the LTE operator.

type GT<A extends TypeNumber, B extends TypeNumber> =  
A extends [...infer _, ...B]
? A extends B
? false
: true
: false;

type LT<A extends TypeNumber, B extends TypeNumber> =
B extends [...infer _, ...A]
? B extends A
? false
: true
: false;

The GT and LT operators are curiously more complex than GTE and LTE because we added a check to return false if we are in the case of A extends B (the EQ case).

So we have our basic operators. We can now define a type using these operators and, according to the result, we use the TrueCase or the FalseCase.

type ComparisonOperator<A extends TypeNumber = Zero, B extends TypeNumber = Zero> =  
LTE<A, B> |
LT<A, B> |
GTE<A, B> |
GT<A, B> |
EQ<A, B>;

type Instruction = any;
type I_DoNothing = never;

type IF<C extends ComparisonOperator,
TrueCase extends Instruction = I_DoNothing,
FalseCase extends Instruction = I_DoNothing> =
C extends true ? TrueCase : FalseCase;

I’ve constrained the TrueCase and FalseCase with an Instruction type because I'm pretty sure I will have a cool Instruction type in the future. And tadaaaa! We have a type system with condition and comparison operators! Piece of cake!

An image of a man saying “It’s a weird flex, but sure.”

The sorting algorithm

I’ve decided to implement an insertion sort because it’s a very simple and intuitive algorithm. You take each element of your input array, and you place these elements at the good index of the output array. Nothing more.

Typescript types as a functional programming language?

The first important thing is to create a loop with a stop condition. It seems very simple, but there’s a problem in TypeScript: programming with types is a kind of functional programming and not imperative programming. Writing a while would be something like this:

type While<  
LoopCondition extends ComparisonOperator,
LoopCase extends Instruction = I_DoNothing,
OutCase extends Instruction = I_DoNothing
> =
LoopCondition extends true ?
While<LoopCondition, LoopCase, OutCase> :
OutCase;

But I said a kind of functional programming. Because TypeScript can compute basic types (boolean, string, etc.) and generic types (ReturnType, Omit, etc.) but can't compute generic of generic types. If we compare TypeScript with functional programming, we get this:

Comparison table between TypeScript and any functional programming language

Higher-order functions are an important part of functional programming because it’s the principle used to define predicates for loops, mapping functions, etc. Without that, we could only give a literal or computed value ( myVar < 5) to a while function and not a step-by-step computed value ((myVar) => myVar < 5).

That’s exactly what is happening with our While type: if we use it, we will pass a value for the LoopCondition and not a predicate. So it's an infinite loop because the LoopCondition is never recomputed.

This issue has been quickly spotted by some developers and is still active since 2014. Until the implementation of these Higher Kinded Types (HKTs) in Typescript core, some crazy developers worked on the subjects and achieved implementations of HKTs:

Maybe I’ll use them in future projects for a better code readability and simpler implementation, but let’s not use them for our current algorithm.

An image of a woman saying “You’re crazy.”
Probably you.

Back to the sorting

We start to work here with an input array and an output array. We will take elements one by one from the input and place them in their good place in the output. So we will have something like this:

type DoNothing = never; // A stupid placeholder type

type SortArray<
ArrayParam extends Array<TypeNumber>,
Out extends Array<TypeNumber> = []
> =
IF<GT<ArrayParam["length"], Zero>,
DoNothing, // We will call sorting here
Out
>

But this code can’t work because our GT needs a TypeNumber and not a number. In this case, the easiest thing to do is to compute manually the size of our array with a custom type instead of trying to transform a number to a TypeNumber. This custom type is quite easy after all the things we've done: we're just emptying the array until it's empty, and we increment a counter after each iteration.

type NumberOfElements<
A extends unknown[],
Result extends TypeNumber = Zero
> =
A extends [infer _, ...infer Rest]
? Rest extends unknown[]
? NumberOfElements<Rest, Add<Result, One>>
: NumberOfElements<Rest, Result>
: Result;

The next step is to “iterate” on our array, do something until there’s no element in the input array, and return the output type. It will be something like this:

type SortArray<
ArrayParam extends TypeNumber[],
Out extends TypeNumber[] = []
> =
IF<GT<NumberOfElements<ArrayParam>, Zero>,
ArrayParam extends [infer CurrentElement, ...infer Rest]
? Rest extends TypeNumber[]
// There are elements after the current one
? CurrentElement extends TypeNumber
// We will search the index of our element here
? SortArray<Rest, never>
: SortArray<Rest, Out>
: CurrentElement extends TypeNumber
// Search index of the last element
? never
: Out
: Out,
Out
>

When reading this, someone in my imagination will say: “But why are you re-inferring CurrentElement type? ArrayParam extends TypeNumber[] and CurrentElement is the first element of ArrayParam, so CurrentElement is already TypeNumber, isn't it?" That's true in theory. But we're using Typescript with only 5k+ open issues on the repository. So yes, this is only a check to remove a buggy TS2344 error. Why does it happen? Y'know, I'm a stupidity genius, not a wizard.

An image of a man pointing his finger on his head.
Me.

A place to call home

The search part of the algorithm is easier than you think. Because our algorithm is really dumb: loop until we find a greater number than our element, and place our element at this place. Using functional programming (so recursive functions), we will produce something like this:

Call rec. 0 // sort(6, [1, 4, 7, 9]) 
Call rec. 1 // [1, ...sort(6, [4, 7, 9])]
Call rec. 2 // [1, ...[4, ...sort(6, [7, 9])]]
Resolve 2 // [1, ...[4, ...[6, 7, 9]]]
Resolve 1 // [1, ...[4, 6, 7, 9]]
Resolve 0 // [1, 4, 6, 7, 9]

Each sort function call has to check if the new number is greater than the first element in the array. The call returns an array with the new elements followed by the rest of the array. Otherwise, we call another sort function but without the first element of the array.

With our set of magical types, we can implement this logic:

type _SearchIndexForElement<
NewNumber extends TypeNumber,
R extends Array<TypeNumber>,
// We remove an extends ternary by placing it here
CurrentElement extends TypeNumber = R[ToRealNumber<Zero>]
> =
R extends [CurrentElement, ...infer Rest]
? IF<GT<NewNumber, CurrentElement>,
// Another useless check because it's Typescript
Rest extends TypeNumber[]
// There's elements remaining in the array
? [CurrentElement, ..._SearchIndexForElement<
NewNumber, Rest>]
// Useless case for a useless check
: [...R, NewNumber],
// We found a place for NewNumber
[NewNumber, ...R]
>
// No more elements in array, so
// NewNumber is the bigger number
: [...R, NewNumber];

Now we just have to call our new _SearchIndexForElement type in our sort algorithm:

type SortArray<
ArrayParam extends TypeNumber[],
Out extends TypeNumber[] = []
> =
IF<GT<NumberOfElements<ArrayParam>, Zero>,
ArrayParam extends [infer CurrentElement, ...infer Rest]
? Rest extends TypeNumber[]
? CurrentElement extends TypeNumber
? SortArray<Rest, _SearchIndexForElement<CurrentElement, Out>>
: SortArray<Rest, Out>
: CurrentElement extends TypeNumber
? _SearchIndexForElement<CurrentElement, Out>
: Out
: Out,
Out
>

When testing the algorithm, we got this result:

type TestArrayToSort = [D['Six'], D['One'], D['Five'], D['Three'], D['Eight'], D['One']];  
type TransformedResult<T extends TypeNumber[]> = { [K in keyof T]: ToRealNumber<T[K]> };
type TestSort = TransformedResult<SortArray<TestArrayToSort>>;
// Got [1, 1, 3, 5, 6, 8]

Oh yeah, we did it! It’s not perfect and poorly optimized, but hey, did you ever think somday you’d see a sort algorithm only with types? And the most interesting thing in this experience is not writing the algorithm but studying the complexity existing in types systems: as I explained before, we’re near to a real functional programming language. Typescript has its bugs, but it works correctly in a huge amount of use cases. And even in some of the strangest cases.

Thanks a lot for reading this article. I don’t know if I’ll write another part of this funny series of articles. I started a few months ago a work on coding a decimal calculator with types, but it’s not as easy as I thought. Anyway, don’t hesitate to share this article, discuss it with me on Bluesky or Mastodon, or just code anything funny.

Oh, and all the code is now available here: https://github.com/AamuLumi/extreme-typescript

An image of a sheep running to the camera and saying “Hi”.
Cute goat wanted to thank you.

Thanks to Elodie and Armand for their help and advice. You rock!

Originally published at https://aamulumi.info on November 11, 2024.


The Useless Type Array Sorter in Typescript was originally published in ekino-france on Medium, where people are continuing the conversation by highlighting and responding to this story.