腳本之家服務器常用軟件

快捷導航

教你用typescript類型來推算斐波那契

更新時間：2022年01月23日 15:25:30 作者：字節(jié)跳動數(shù)據(jù)平臺前端團隊

斐波那契是自然界與社會中存在的一種數(shù)學規(guī)律,下面這篇文章主要給大家介紹了關(guān)于如何用typescript類型來推算斐波那契的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下

寫在前面

本文執(zhí)行環(huán)境typescript，版本4.5.4

斐波那契

雖然大家都熟悉斐波那契了，還是簡單的說說吧，一個知名的數(shù)學數(shù)列，地推方式如下

Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)

最后得出來的數(shù)列就是

0 1 1 2 3 5 8 13 21 34 55 89 ...

實現(xiàn)邏輯

介紹完斐波那契后，再來看看typescript類型推算要解決核心點

第0和第1個數(shù)返回自身
某個數(shù)等于前兩個數(shù)相加
推算一個數(shù)需要循環(huán)或者遞歸得到前兩個值
輸入的只能是數(shù)字，且不能是負數(shù)

分析完我們再來看看typescript能夠提供哪些，缺少哪些

第一個問題：第0和第1個數(shù)返回自身

這個滿足，可以通過extends來實現(xiàn)

type GetSelf<T> = T extends 0 | 1 ? T : never;
// 測試
type Test0 = GetSelf<0>; // 0
type Test1 = GetSelf<1>; // 1
type Test2 = GetSelf<2>; // 2

第二個問題：某個數(shù)等于前兩個數(shù)相加

這個就開始麻煩了，因為typesript中是沒有加法運算的，也就是說 1 + 2 = 的結(jié)果typescript并不知道，所以列一個todo

第三個問題：推算一個數(shù)需要循環(huán)或者遞歸得到前兩個值

看看typescript中有沒有遞歸呢，是有的，比如實現(xiàn)一個鏈表

type Node<T> = {
    val: T;
    next: Node<T>;
}

不過怎么跳出循環(huán)，另外我們需要的是一個值，而不是返回一個對象，再列一個todo

第四個問題

輸入的只能是數(shù)字，且不能是負數(shù)

限定數(shù)字很好做，extends number就可以判斷了，判斷負數(shù)呢？

負數(shù)和正數(shù)有啥區(qū)別呢？

負數(shù)多個符號顯示，那改造成字符串后的長度和正數(shù)不等是吧，嘗試

type len1 = '123'['length']; // number
type len2 = number[]['length']; // number;
type len3 = [1, 2, 3]['length']; // 3
type len4 = [number, string]['length']; // 3

字符串和未定義的數(shù)組的長度竟然無法推算，看起來只有元組是可以的

負數(shù)比0小，可是typescript中沒有比較大小的操作，再列一個todo

結(jié)論

我們可以解決第一個問題，同時得知可以通過 length 來獲取元祖長度，todo如下

加法運算
循環(huán)或者遞歸計算，并有跳出條件
判斷非負數(shù)

解決todo

+1操作

雖然上一輪大部分功能沒有推算出來，但是得到一個有用的結(jié)論，元祖是可以得到length的值。

那 +1操作是不是可以理解成 PUSH操作后拿出 length 了？嘗試

type Push<T extends Array<number>, P extends number> = [...T, P];

type arr1 = [1, 2];
type arr2 = Push<arr1, 3>; // [1, 2, 3]
type len1 = arr1['length'] // 2
type len2 = arr2['length']; // 3

確實實現(xiàn)了 +1操作，加法應該是可以解決了，+n 就是循環(huán)n次，結(jié)束條件就是結(jié)果為n

所以加法運算最后可以轉(zhuǎn)成元祖后計算長度，類似 JavaScript的Array(n).fill(0)，第一步實現(xiàn) 數(shù)字轉(zhuǎn)array

數(shù)字轉(zhuǎn)array

type ArrOf<T extends number, P extends Array<0> = []> = {
    ['loop']: ArrOf<T, [...P, 0]>;
    ['result']: P;
}[P['length'] extends T ? 'result' : 'loop'];

type arrof1 = ArrOf<5>; // [0, 0, 0, 0, 0]

因為我們需要遞歸后再跳出條件，最后返回值，所以可以構(gòu)造一個對象后獲取key，而key就是跳出循環(huán)的關(guān)鍵，跳出循環(huán)的判斷就是元祖的長度等于輸入的數(shù)

基于以上實現(xiàn)，我們可以得到add的完整實現(xiàn)了

type ADD<A extends number, B extends number> = [...ArrOf<A>, ...ArrOf<B>]['length'];

type add1 = ADD<3, 4>; // 7

雖然可以推算出結(jié)果，但是給我報了一個warning

A rest element type must be an array type.

我覺得可能他推算不出來返回的是array，所以需要我們聲明ArrOf返回的數(shù)都是array，類似 Array.from

type ArrFrom<T> = T extends Array<T> ? T : T;

type ADD<A extends number, B extends number> = [...ArrFrom<ArrOf<A>>, ...ArrFrom<ArrOf<B>>]['length'];

加法和遞歸都被搞定了，接下來看看非負數(shù)的問題

非負數(shù)判斷

再重新看看之前的分析，負數(shù)有什么特殊的地方，負數(shù)多個符號顯示，且符號固定是第一位

type str11 = 'abcde';
type str12 = str11[0]; // string

看來并不能通過下標來取巧，那我們只能上 infer 了

type getFirst<T extends string> = T extends `${infer P}${string}` ? P : T;

type str11 = 'abcde';
type str12 = getFirst<str11>; // a

所以我們可以把數(shù)字轉(zhuǎn)換字符串后求得符號，然后得出負數(shù)的判斷

type FirstStr<T extends number> = `${T}` extends `${infer P}${string}` ? P : T;

type isFu<T extends number> = FirstStr<T> extends '-' ? true : false;

type isFu1 = isFu<0>; // false
type isFu2 = isFu<12>; // false
type isFu3 = isFu<-6>; // true
type isFu4 = isFu<-0>; // true

實現(xiàn)斐波那契

所有的部分都就緒了，實現(xiàn)一下斐波那契

type ArrOf<T extends number, P extends Array<0> = []> = {
    ['loop']: ArrOf<T, [...P, 0]>;
    ['result']: P;
}[P['length'] extends T ? 'result' : 'loop'];
// 第8行提示結(jié)果可能不是array
type ArrFrom<T> = T extends Array<T> ? T : T;

type ADD<A extends number, B extends number> = [...ArrFrom<ArrOf<A>>, ...ArrFrom<ArrOf<B>>]['length'];
// 第23行提示結(jié)果可能不是number
type NumberFrom<T> = T extends number ? T : T & number;

type ADD2<A extends number, B extends number> = NumberFrom<ADD<A, B>>;

type FirstStr<T extends number> = `${T}` extends `${infer P}${string}` ? P : T;
// 添加負數(shù)判斷
type isFu<T extends number> = FirstStr<T> extends '-' ? true : false;

type FIB<T extends number, A extends number = 0, B extends number = 1, N extends number = 0> = isFu<T> extends true
    ? never
    : T extends 0 | 1
? T
: {
    ['loop']: FIB<T, B, ADD2<A, B>, ADD2<N, 1>>;
    ['result']: B;
}[T extends ADD2<N, 1> ? 'result' : 'loop'];

type FIFU1 = FIB<-6> // never
type FI0 = FIB<0> // 0
type FI1 = FIB<1>; // 1
type FI2 = FIB<2>; // 1
type FI3 = FIB<3>; // 2
type FI4 = FIB<4>; // 3
type FI5 = FIB<5>; // 5
type FI6 = FIB<6>; // 8
type FI7 = FIB<7>; // 13
type FI8 = FIB<8>; // 21
type FI9 = FIB<9>; // 34