Posted on Oct 2, 2020

How to use TS Type solve Fibonacci

I learned a lot from the post, and this is why I registered account to write my first post.
https://medium.com/free-code-camp/typescript-curry-ramda-types-f747e99744ab

0x00 what we want to do

We want to do like this ↓↓↓ use TS Type solve FIbonacci

type r0 = Fib<Zero>; // type r10= 0 type r1 = Fib<One>; // type r1 = 1 type r2 = Fib<Two>; // type r2 = 1 type r3 = Fib<3>; // type r3 = 2 type r4 = Fib<4>; // type r4 = 3 type r5 = Fib<5>; // type r5 = 5 type r6 = Fib<6>; // type r6 = 8

1x00 How we can do this

1x01 First, we need some util types

They are simple and very easy to understand

Range: generate list
Length: get list's size
Concat: concat two list

 type Length<T extends any[]> = T["length"]; type Range<T extends Number = 0, P extends any[] = []> = { 0: Range<T, [any, ...P]>; 1: P; }[Length<P> extends T ? 1 : 0]; type Concat<T extends any[], P extends any[]> = [...T, ...P]; type t1 = Range<3>; // type t1 = [any, any, any] type Zero = Length<Range<0>>; // type Zero = 0 type One = Length<Range<1>>; // type One = 1 type Ten = Length<Range<10>>; // type Ten = 10 type Five = Length<Range<5>>; // type Five = 5 type Six = Length<Concat<Range<5>, Range<1>>>; // type Six = 6

Add is also easy

We generate two list
Concat them
Get the result size

 type Add<T extends number, P extends number> = Length< Concat<Range<T>, Range<P>> >; type Two = Add<One, One>; // type Two = 2 type Three = Add<One, Two>; // type Three = 3

But how to implement subtraction?

1x02 We need more util types

Some array types

Append: insert element in head of list
IsEmpty/NotEmpty: judge list is/not empty
Tail: delete the first element

 type Append<T extends any[], E = any> = [...T, E]; type IsEmpty<T extends any[]> = Length<T> extends 0 ? true : false; type NotEmpty<T extends any[]> = IsEmpty<T> extends true ? false : true; type t4 = IsEmpty<Range<0>>; // type t4 = true type t5 = IsEmpty<Range<1>>; // type t5 = false type Tail<T extends any[]> = ((...t: T) => any) extends ( _: any, ...tail: infer P ) => any ? P : []; type t22 = Tail<[1, 2, 3]>; // type t22 = [2, 3] type t23 = Tail<[1]>; // type t23 = [] type t24 = Tail<[]>; // type t24 = []

logic type

And: a && b
LessList: a.length <= b.length
Less: a <= b

 type And<T extends boolean, P extends boolean> = T extends false ? false : P extends false ? false : true; type t6 = And<true, true>; // type t6 = true type t7 = And<true, false>; // type t7 = false type t8 = And<false, false>; // type t8 = false type t9 = And<false, true>; // type t9 = false // T <= P type LessList<T extends any[], P extends any[]> = { 0: LessList<Tail<T>, Tail<P>>; 1: true; 2: false; }[And<NotEmpty<T>, NotEmpty<P>> extends true ? 0 : IsEmpty<T> extends true ? 1 : 2]; type Less<T extends number, P extends number> = LessList<Range<T>, Range<P>>; type t10 = Less<Zero, One>; // type t10 = true type t11 = Less<One, Zero>; // type t11 = false type t12 = Less<One, One>; // type t12 = true

Now we can 'translate' js to ts

- SubList:

const a = [1, 2, 3]; const b = [4, 5]; const c = []; while (b.length !== a.length) { a.pop(); c.push(1); } // c.length === a.length - b.length console.log(c.length);

Sub: a - b

 type SubList<T extends any[], P extends any[], R extends any[] = []> = { 0: Length<R>; 1: SubList<Tail<T>, P, Append<R>>; }[Length<T> extends Length<P> ? 0 : 1]; type t13 = SubList<Range<10>, Range<5>>; // type t13 = 5 // T - P type Sub<T extends number, P extends number> = { 0: Sub<P, T>; 1: SubList<Range<T>, Range<P>>; }[Less<T, P> extends true ? 0 : 1]; type t14 = Sub<One, Zero>; // type t14 = 1 type t15 = Sub<Ten, Five>; // type t15 = 5

2x00 JS Function ==> TS Type

In js we use function

const fib = (n) => (n <= 1 ? n : n++);

in ts we use type!!! they look like same!

 type Fib<T extends number> = { 0: T; 1: Add<Fib<Sub<T, One>>, Fib<Sub<T, Two>>>; }[Less<T, One> extends true ? 0 : 1]; type r0 = Fib<Zero>; // type r10= 0 type r1 = Fib<One>; // type r1 = 1 type r2 = Fib<Two>; // type r2 = 1 type r3 = Fib<3>; // type r3 = 2 type r4 = Fib<4>; // type r4 = 3 type r5 = Fib<5>; //type r5 = 5 type r6 = Fib<6>; // type r6 = 8