The Useless Type Array Sorter in Typescript

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 they stupid idea too far. Really too far.

So I have now 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 which will help someone to do a specific task I don’t know, I preferred to dig up my really useless project : the good ol’ calculator made only with types and without any numbers.

The main problem was to find what I can do with this project. I did something funny (yes, strange notion of fun), but is there something funnier ? Is there something which 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 the part two of this project.

We will sort an array of number.

Without numbers.

Only with types.

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. But you can use 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 !

…

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

The solution

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

You. 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 they are 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;

The main idea behind GTE is to check if our number A contained the number B (the same technique used to code Divide). 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 operator 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 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 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 !

The sorting algorithm

I 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 stop condition. It seems very simple, but there’s a problem in Typescript : programming with types is 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 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 with functional programming, we get this :

Typescript	Functional programming language
Types (`boolean`, `string`)	Primitives (`boolean`, `string`)
Generic types (`ReturnType`, `Omit`)	Functions (`(x, y) => x+y`)
Generic of generic types ? (`T<F<~>, X> = F<X>`)	Higher-order functions (`(f, x) => f(x)`)

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 achieve implementations of HKTs :

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

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 to the good place in the output. So we will have something like this :

type SortArray<
	ArrayParam extends Array<TypeNumber>, 
	Out extends Array<TypeNumber> = []
> =  
    IF<GT<ArrayParam["length"], Zero>,  
		never, // Call sorting
	    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. And 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 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's 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-infering 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.

Me. Me.

A place to call home

The search part of the algorithm is easier than what 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 sortfunction 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 and the rest of the array after. Else, 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 think you’ll see someday 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 system : 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 to this funny series of articles. I’ve started 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, to discuss with me on Mastodon or just to code anything funny.

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

Cute goat wanted to thanks you.

Pink in the dark

Discussions et écrits autour de la tech, des jeux vidéos, de la sociologie et de la musique

🕵️ Explorateur

📝 Derniers articles