What are we going to do
The goal is to programmatically implement a Fibonacci sequence algorithm using TypeScript’s type declarative syntax. In other words, similar to the process of using existing machine code to instruction set, binary to decimal, assembly language to high-level programming language, make programming possible with type-definition syntax.
And finally the Fibonacci sequence that we’re going to implement looks like this, right?
const fib = (n: number) :number= > n <= 1 ? n : fib(n - 1) + fib(n - 2);
for (let i = 0; i < 10; i++) {
console.log(i, fib(i));
}
Copy the codeThe running results are as follows:
The program is totally fine. End of the flower!
Just kidding, this is just a JavaScript script that uses TypeScript Type definitions. We really want to do this ↓↓↓, using TS Type to solve FIbonacci
import { Fib, Add } from './fib-type';
type one = Fib<1>;
type zero = Fib<0>;
type Two = Add<one, one>;
type Five = Add<Two, Add<Two, one>>;
type Fib5 = Fib<Five>;
type Fib9 = Fib<9>;
type r0 = Fib<Zero>; // type r0= 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
type r9 = Fib<9>; // type r9 = 34
type sum = Add<r9, r6>; // type sum = 42
Copy the code
Two, what should we do
To implement the Fibonacci sequence, refer to the original code, there is a basic comparison, addition, loop syntax, so we also need to use the type system to implement all three functions in sequence
2.1 Implementation of addition
To implement addition, you need to implement some tool types first
//
type Length<T extends any[]> = T['length'];
type one = 1
// Uses extends to compare numbers
type a111 = 0 extends one ? true : false // type a111 = false
type a112 = 1 extends one ? true : false // type a112 = true
Copy the codeThe implementation of range is recursive
/ / pseudo code
function range(n, list=[]){
if(n<=0) return list.length
return range(n-1[1. list]) }Copy the codeTypeScript limits the use of recursion instead of loops. There will be several similar ones later. Remember that recursion has several exits, and objects have several keys, and each key is a condition
// Creates a tuple of the specified length with the second argument carrying the return value
type Range<T extends Number = 0, P extends any[] = []> = {
0: Range<T, [any. P]>;1: P;
}[Length<P> extends T ? 1 : 0];
// Splice two tuples
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 Ten = Length<Range<10> >;// type Ten = 10
type Five = Length<Range<5> >;// type Five = 5
type One = Length<Range<1> >;Copy the codeWith the tool syntax above, it is relatively easy to add by asking for the length of the combined elements
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
Copy the codeWith addition, how do you subtract? Subtraction and division are generally harder than addition, so we need more tool-type functions!
2.2 Tool Functions
2.2.1 Implement some basic tool types
Shift: Deletes the first elementAppend: Inserts an element at the end of a tupleIsEmpty/NotEmpty: Determines that the list is empty
[1,2,3] -> [2,3]
type Shift<T extends any[] > = ((. t: T) = > any) extends (
_: any. Shift: infer P ) =>any
? P
: [];
type pp = Shift<[number.boolean.string.Object] >// type pp = [boolean, string, Object]
// Append to the tuple
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
Copy the code2.2.2 Logical Types
And:a && b
// Logical operation
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
Copy the code2.2.3 Less than or equal to
Pseudo-code: The main idea is to extract an element from a list at the same time. The list with length 0 first is shorter
function dfs (a, b){
if(a.length && b.length){
a.pop()
b.pop()
return dfs(a,b)
}else if(a.length){
a >= b
}else if (b.length){
b > a
}
}
Copy the codeIdea: Convert a comparison of numbers to a comparison of list lengths
// The length of a tuple is less than or equal to T <= P, and one element is removed
type LessEqList<T extends any[], P extends any[] > = {0: LessEqList<Shift<T>, Shift<P>>;
1: true;
2: false;
}[And<NotEmpty<T>, NotEmpty<P>> extends true
? 0
: IsEmpty<T> extends true
? 1
: 2];
// The number is less than or equal to
type LessEq<T extends number, P extends number> = LessEqList<Range<T>, Range<P>>;
type t10 = LessEq<Zero, One>;
// type t10 = true
type t11 = LessEq<One, Zero>;
// type t11 = false
type t12 = LessEq<One, One>;
// type t12 = true
Copy the code2.3 Realization of subtraction
There are two ideas for subtraction, list length subtraction and number subtraction
2.3.1 List subtraction
The default is to decrease the value by a large amount, and then decrease the value by a small amount. You just need to judge the reverse and then add a symbol. For simplicity, the pseudo-code is not implemented here, which can be referred to as the following:
/ / pseudo code
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.lengthconsole.log(c.length);
// Subtract T - P from the tuple, and remove one element. When the length reaches 0, what is left is the result, which is carried by the third argument
type SubList<T extends any[], P extends any[], R extends any[] = []> = {
0: Length<R>;
1: SubList<Shift<T>, P, Apped<R>>;
}[Length<T> extends Length<P> ? 0 : 1];
type t13 = SubList<Range<10>, Range<5> >;// type t13 = 5
Copy the code2.3.2 Digital subtraction
Idea: Compare numbers into tuples
// Set size cannot be negative, default is greatly reduced
// Number subtraction
type Sub<T extends number, P extends number> = {
0: Sub<P, T>;
1: SubList<Range<T>, Range<P>>;
}[LessEq<T, P> extends true ? 0 : 1];
type t14 = Sub<One, Zero>;
// type t14 = 1
type t15 = Sub<Ten, Five>;
// type t15 = 5
Copy the codeWith these tools in hand, we can translate the Fibonacci sequence that we originally implemented in JavaScript into TypeScript type encoding
Fib: JS function –> TS
In JavaScript, we use functions
const fib = (n: number): number= > n <= 1 ? n : fib(n - 1) + fib(n - 2);
Copy the codeIn TypeScript, we use types, but we’re just writing them in a different way, using type functions to describe operations
Because of TypeScript recursion limitations, you can’t solve very large items, but it’s fun
export type Fib<T extends number> = {
0: T;
1: Add<Fib<Sub<T, One>>, Fib<Sub<T, Two>>>;
}[LessEq<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
Copy the codeFour,
Does seeing TypeScript implement Fibonacci sequences make you feel like you’re back in the lab “implementing pipelined cpus”?
IT’s development by leaps and bounds in recent decades, more and more “programmers” to join in the Internet industry, under some high-level language and development framework, “programmers” coding is also need to focus only on the business logic implementation, few people will pay attention to the computer is how to implement the underlying addition, subtraction, multiplication, and division, social in progress, of course, technology is also in the rapid iteration, Occasionally stop and recall the first line of “Hello World!” output at the command line when I just got into computer programming. Code then happy themselves, maybe that is the youth we can not go back…
I have a lot of fun ideas, but there’s too little dian square here to write, you know
