Hackweek - `GoodTypes`

Good TypeScript, but without the "Script" part.

const num1 = "1";
const num2 = "2";
let sum: AddStrings<typeof num1, typeof num2>;

// sum can only be "3"
sum = "3";

// otherwise TypeScript reports a compilation error
sum = "4"; // Error: Type '"4"' is not assignable to type '"3"'.

Motivation

Making use the type system in TypeScript to ensure build robust software
Demonstrating the power of literal types and generics in TypeScript
To practice advance type gynastics

That's kind of vague, so what problem does it solve?

none 😐
(im sorry)

There isn't a lot of TypeScript code in the company
and most of these techniques are not required to create robust software, albeit NiceToHave^TM.

Note: Using a robust type system does not automagically make your code robust.
Your code can still have bugs even it passed the compiler's checks.

That said, let's build a calculator anyways.

Background knowledge on TypeScript

TypeScript "compiles" to JavaScript, and the types are non-existent at runtime.
So adding extensive type checking incurs zero overhead in production.

let a: number = 1;
let b: string = "a";
let c: number = 0;

c = c + a;
// c is now value of `3`

c = c + b;
// Error: Type 'string' is not assignable to type 'number'. ts(2322)
//
// This is actually valid JavaScript, c would be value of `3a`
// after string concantination by the `+` operator.
//
// But TypeScript reports this as an error during "compilation"
// and we can avoid having bugs in our code.

Let's talk about the number type

let a: number;
a = 1;     // works!
a = 2;     // also works!
a = "abc"; // Error: Type 'string' is not assignable to type 'number'. ts(2322)

Unlike most programming languages, TypeScript has
literal types

let b: 0 | 1 | 2;
b = 0; // works!
b = 3; // Error: Type '3' is not assignable to type '0'. ts(2322)

Note: One of the goals of TypeScript's type system is to support existing patterns in the JavaScript ecosystem,
some of them does not make sense as a "regular" programming language.
If you're new to TypeScript and find this confusing, that's completely fine :)

Let's talk about `strings`

Like numerical literal types, you can do the same with the string type

type StringABC = "A" | "B" | "C";
let c: StringABC;

c = "A"; // works!
c = "a"; // Error: Type '"A"' is not assignable to type '"A" | "B" | "C"'. ts(2322)

What's more powerful is that, you can "compose" types with template literal types

type StringABC = "A" | "B" | "C";
type LunchOptions = `SET_${StringABC}`;
let d: LunchOptions;

d = "SET_A"; // works!
d = "set_d"; // Error:Type '"set_d"' is not assignable to type '"SET_A" | "SET_B" | "SET_C"'. ts(2322)

You can also use some tricks to deduce types from existing types

type LunchOptions = "SET_A" | "SET_B" | "SET_C";
type DeduceLetter<T> = T extends `SET_${infer L}` ? L : never;
type LunchLetters = DeduceLetter<LunchOptions>;
let e: LunchLetters;

e = "A"; e = "B"; e = "C"; // works!
e = "d"; // Error: Type '"d"' is not assignable to type 'LunchLetters'. ts(2322)

So what then?

The type system in TypeScript is more powerful than you think

I'll try to demonstrate that by:

building a calculator with the type system only

type Result1 = AddStrings<"11", "22">;    // type is "33"
type Result2 = SubtractStrings<"5", "3">; // type is "2"

I'm going to skip over implementation details a lot
because they're boring

Adding numbers

To calculate "a" + "b":
   We can increment "a" by 1, decrement "b" by 1,
   until "b" reaches 0, then return "a" as result
Example:
   2 + 2
-> 3 + 1
-> 4 + 0
== 4

So we have 2 operations:
1. increment a number by 1
2. decrement a number by 1

To calculate 10 + 10:
   10 + 10
-> [1, 0] plus [1, 0]
-> [(1+1), (0+0)]
-> [2, 0]
== 20

So we can reuse the same 2 operations.

Wait, what about carrying, like 19 + 1 = 20?

We can define this as a special case:
increment(x) ->
   if x is 9, then return 0, with carry=1
   otherwise return next digit, with carry=0

And to implement this "increment" function, let's use a lookup table
   0 ->   digit=1, carry=0
   1 ->   digit=2, carry=0
   2 ->   digit=3, carry=0
   3 ->   digit=4, carry=0
   4 ->   digit=5, carry=0
   5 ->   digit=6, carry=0
   6 ->   digit=7, carry=0
   7 ->   digit=8, carry=0
   8 ->   digit=9, carry=0
   9 ->   digit=0, carry=1

The "decrement" function is similar, and is left as an exercise to the audience :)

With this "increment" function in place, we can calculate 19 + 21 with:
   19 + 21
-> [1, 9] + [2, 1]
-> [(1+2), (9+1)]
-> [(1+2), (0 with carry=1)]
-> [(1+2+1), 0]
-> [3, 0]
== 30

Result: see live demo :)

Subtracting numbers

To calculate "a" + "b":
   We can increment "a" by 1, decrement "b" by 1,
   until "b" reaches 0, then return "a" as result
Example:
   3 - 2
-> 2 - 1
-> 1 - 0
== 1

Yadda yadda, TLDR, same as addition but "borrowing" instead of "carrying".
(Insufficient time for preparation, sorry)

Show me the code

type Digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;

type Cast<T, U> = T extends U ? T : U;

type DecMap = {
    0: [1, 9];
    1: [0, 0];
    2: [0, 1];
    3: [0, 2];
    4: [0, 3];
    5: [0, 4];
    6: [0, 5];
    7: [0, 6];
    8: [0, 7];
    9: [0, 8];
};

type Dec<T extends Digit[], O extends Digit[] = []> = T extends [...infer Init, infer Last]
    ? DecMap[Cast<Last, keyof DecMap>] extends [infer Borrow, infer Unit]
        ? Init extends []
            ? Borrow extends 1
                ? never
                : Unit extends 0
                ? O extends []
                    ? [0]
                    : O
                : [Unit, ...O]
            : Borrow extends 1
            ? Dec<Cast<Init, Digit[]>, [Cast<Unit, Digit>, ...O]>
            : [...Cast<Init, Digit[]>, Unit, ...O]
        : never
    : never;

type IncMap = {
    0: [0, 1];
    1: [0, 2];
    2: [0, 3];
    3: [0, 4];
    4: [0, 5];
    5: [0, 6];
    6: [0, 7];
    7: [0, 8];
    8: [0, 9];
    9: [1, 0];
};

type Inc<T extends Digit[], O extends Digit[] = []> = T extends [...infer Init, infer Last]
    ? IncMap[Cast<Last, keyof IncMap>] extends [infer Carry, infer Unit]
        ? Init extends []
            ? Carry extends 0
                ? [Unit, ...O]
                : [Carry, Unit, ...O]
            : Carry extends 0
            ? [...Cast<Init, Digit[]>, Unit, ...O]
            : Inc<Cast<Init, Digit[]>, [Cast<Unit, Digit>, ...O]>
        : never
    : never;

type DigitMap = {
    "0": 0;
    "1": 1;
    "2": 2;
    "3": 3;
    "4": 4;
    "5": 5;
    "6": 6;
    "7": 7;
    "8": 8;
    "9": 9;
};

type Parse<T extends string, O extends any[] = []> = T extends `${infer Head}${infer Tail}`
    ? Head extends `${Digit}`
        ? Tail extends ""
            ? Cast<[...O, DigitMap[Head]], Digit[]>
            : Parse<Tail, [...O, DigitMap[Head]]>
        : never
    : never;

type Stringify<T extends any[], O extends string = ""> = T extends [infer Head, ...infer Tail]
    ? Head extends number
        ? Stringify<Tail, `${O}${Head}`>
        : never
    : O;

type Add<T extends Digit[], U extends Digit[]> = U extends [0] | [] ? T : Add<Inc<T>, Dec<U>>;

type Subtract<T extends Digit[], U extends Digit[]> = U extends [0] | [] ? T : Subtract<Dec<T>, Dec<U>>;

type AddStrings<T extends string, U extends string> = Add<Parse<T>, Parse<U>> extends infer R
    ? Stringify<Cast<R, any[]>>
    : never;

type SubtractStrings<T extends string, U extends string> = Subtract<Parse<T>, Parse<U>> extends infer R
    ? Stringify<Cast<R, any[]>>
    : never;

lokshunhung/good-types.md

Hackweek - GoodTypes