DEV Community: Florian "Aamu" KAUDER

The Useless Type Array Sorter in Typescript

Florian "Aamu" KAUDER — Mon, 11 Nov 2024 20:48:02 +0000

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.

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.

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.

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

The Useless Type Calculator in Typescript

Florian "Aamu" KAUDER — Sat, 26 Oct 2024 11:51:30 +0000

It's time for one of the most useless things I ever made — something beyond reason, where the logic stops being rational and the void is the reality. It's time to create a calculator using only types from Typescript.

Originally posted on my blog October, 5th 2021 : https://aamulumi.info/Dev/The-Useless-Type-Calculator-in-Typescript

A few days ago, I remembered a discussion with a friend about Turing-complete systems. We checked Wikipedia article on the subject, and we discovered that many things (like games) were Turing-complete. So yes, Minecraft is Turing-complete, Factorio too, Dwarf Fortress too, and it seems that Habbo Hotel and Magic: The Gathering (yes, the cards game) are also Turing-complete.

We also found somewhere that the type system of Typescript is Turing-complete. With this knowledge, I decided to start developing something that would not change anything: a calculator with only Typescript types.

Yes. This is one of the most stupid ideas I got for a while. But this is a fun exercise you can do to prove your skills in typing everything.

The rules

If you want to try to do the calculator, here are the rules of the "game" (if we can call this a game):

you have to start with only two types: BZero (for Boolean Zero) and BOne (for Boolean One).

type BZero = false;
type BOne = true;

you can only use types. No interface, no enum, only types.
you have to compute the four basic mathematical operations (with types): add, subtract, multiply and divide. You can also add modulo.
this code should works:

// Equivalent of (6 + 6 * (1 + 2)) / (6 - 2) = 6
type StrangeOperation = Divide<
  Add<Multiply<Six, Add<One, Two>>, Six>,
  Subtract<Six, Two>
>;

Due to the way I implement the calculator, I use another type Result to read the result:

type OpResult = Result<StrangeOperation>;

This type is totally optional in the rules. But you must have a exact number type at the end of the computation. For example, you should have:

type OpResult = 6;

And here you go! It's time for you to code!

...

Yeah, better read the solution, isn't it?

The solution

Conception

Firstly, I search what the ways to get a number type from a type in Typescript are. You have your base operation to transform BZero and BOne to Zero and One number if you know this.

I tried something based on array indexes, but there was no way to get a number. So I discovered that Typescript tuples have a length property. And it works with variable tuples since 3.0. With this information, I began to write a calculator based on Tuples.

type TypeNumber = Array<any>;

The first types we need are the Zero and the One based on tuples. In this way, I write a simple conditional type that returns a tuple with the number of elements equivalent to the number it describes. For example :

type ToTypeNumber<A> = A extends true ? [true] : [];

type Zero = ToTypeNumber<BZero>;
type One = ToTypeNumber<BOne>;

// Result
type Zero = [];
type One = [true];

In this way, we need a type to read the length of the tuple to get the desired type number.

type Result<A extends TypeNumber> = A["length"];

// Example
type C = Result<One>;

// Result
type C = 1;

Operation 1 : Add

With this conception, the Add type is the most straightforward operation to implement, thanks to Typescript 4.0. We have to concatenate the two tuples, and we have done an Add type.

type Add<A extends TypeNumber, B extends TypeNumber> = [...A, ...B];

// Example
type Two = Add<One, One>;
type TwoResult = Result<Two>;
type Four = Add<Two, Two>;
type FourResult = Result<Four>;

// Result
type Two = [true, true];
type TwoResult = 2;
type Four = [true, true, true, true];
type FourResult = 4;

Operation 2 : Subtract

The hard way

Now, the fun begins.

We need to think about the computation behind the subtraction. So let's come back to elementary school.

I have 6 balloons. I give 4 balloons to Manu. I now have 2 balloons remaining.

In terms of tuples, we can illustrate the problem with this :

type MyBalloons = [true, true, true, true, true, true];
type NewManuBalloons = [true, true, true, true];
type NewMyBalloons = [true, true];

To implement the subtraction, I take each element of MyBalloons one by one and check if each element exists in NewManuBalloons. When I arrive at the moment there's no more element in NewManuBallooons, I start to increment a variable which will be the result.

But there's a problem: it looks like a loop. How can we achieve a loop in Typescript?

The answer here is to use a recursive type. And with a condition, we can do that with a recursive conditional type. Here's the code:

type Subtract<
  A extends TypeNumber,
  B extends TypeNumber,
  Res extends TypeNumber = []
> = A extends [boolean, ...infer H]
  ? B extends [boolean, ...infer J]
    ? Subtract<H, J, Res>
    : Subtract<H, B, Add<Res, One>>
  : Res;

Oh yeah, there's another tip: I use type inference to remove elements of a tuple. For example, if I have type A = [true, true, true], I will get type H = [true, true]. This is because I check if A's first element is a boolean, and I send the rest of the tuple in another type variable.

I use the type inference in a second condition to check if the current element exists in B. When there's an element in A and B, I recall the Subtract type with the remaining elements of A (H) and the remaining elements of B (J). If there's no more element in B, we continue to call Subtract, but we increase Res at each call. And when A is empty, we return Res type.

And now, we have a subtraction with only types. Note that this subtraction only works with positive integers. This problem is caused by tuples, because yes, you cannot have a tuple with a negative length.

// Example
type TwoFromSubtract = Subtract<Four, Two>;
type TwoFromSubtractResult = Result<TwoFromSubtract>;

// Result
type TwoFromSubtract = [true, true];
type TwoFromSubtractResult = 2;

The smart way

The hard way is a pure example of overengineering. Because there's such a simple method to do a subtraction: subtract B from A and keep the result.

For my defense, I understood that I could use type inference between 2 dynamic types when working on Divide. But you can shame me, and it's okay.

Here's the code:

type BetterSubtract<A extends TypeNumber, B extends TypeNumber> = A extends [
  ...B,
  ...infer Res
]
  ? Res
  : Zero;

Operation 3 : Multiply

We already have seen all the techniques we need to Multiply. So we need to add B times the A number. This is now a piece of cake since the subtraction's hard way.

To multiply, make a loop (with recursive types). In this loop, remove One from B, add A to the result, and send the Res when B is Zero. In this way, we will add A B-times, so we are doing A x B.

type Multiply<A extends TypeNumber, B extends TypeNumber> = B extends [
  boolean,
  ...infer S
]
  ? Add<Multiply<A, S>, A>
  : [];

// Example
type MultTest = Multiply<Four, Six>;
type MultTestResult = Result<MultTest>;

// Result
type MultTest = [
  true,
  ... 22 more,
  true
];
type MultTestResult = 24;

Operation 4 : Divide

We have worked since the beginning with integers. So we can only have a Euclidian division for this part.

In the subtraction, we search if A can contain B and what's remaining. We will do the same thing, except we need to search how many times A contains B. So we have the same primary condition as the subtraction, but we add a recursive type with an incremented result at each loop iteration. When A cannot contain B anymore, send the number of loops done until here.

type Divide<
  A extends TypeNumber,
  B extends TypeNumber,
  Res extends TypeNumber = Zero
> = A extends [...B, ...infer T] ? Divide<T, B, Add<Res, One>> : Res;

// Example
type DivideTest = Divide<MultTest, Six>;
type DivideTestResult = Result<DivideTest>;
type DivideTest2 = Divide<Six, Four>;
type DivideTest2Result = Result<DivideTest2>;

// Result
type DivideTest = [true, true, true, true];
type DivideTestResult = 4;
type DivideTest2 = [true];
type DivideTest2Result = 1;

Operation Bonus : Modulo

Modulo is almost the same as the Divide. We keep checking how many times A contains B, and when we reach the end, we return the remaining value instead of the number of iterations. And tadaaaaaa, we get the modulo operation.

type Modulo<T extends TypeNumber, U extends TypeNumber> = T extends [
  ...U,
  ...infer S
]
  ? Modulo<S, U>
  : T;

// Example
type ModuloTest = Modulo<MultTest, Six>;
type ModuloTestResult = Result<ModuloTest>;
type ModuloTest2 = Modulo<Six, Four>;
type ModuloTest2Result = Result<ModuloTest2>;

// Result
type ModuloTest = [];
type ModuloTestResult = 0;
type ModuloTest2 = [true, true];
type ModuloTest2Result = 2;

So here we have a working calculator with only Typescript types. I thought about implementing the decimal calculator based on the binary representation of decimals. But this is clearly madness. I hope you enjoy reading this piece of programming like I enjoyed writing it. And last but not least, here's the topic of the initial discussion I had with my friend about Turing-Complete Typescript.

Thanks for reading! From all of us here, I want to wish you happy programming and God Bless, my friend! :)