用TypeScript类型系统编程实现斐波那契数列
作为一名前端开发者，一定知道TypeScript经常被用于项目中的类型约束，使得在JavaScript这种弱类型语言中有了静态检查的能力，也推进了前端工程化的演进速度，在研究学习TypeScript过程中，我的小伙伴发现了TS的一些好玩儿功能，独乐乐不容众乐乐，遂分享这篇文章给大家。
小伙伴（育豪）的原文可能理解起来有一些难度，笔者有尝试增加一些描述，但想要完全领略TS的“类型体操”的奥妙，还是得实操一番。
一、我们要做什么
我们的目的是想要通过TypeScript的类型声明式语法，编程实现一个斐波那契数列算法。换句话说，类似于用现有的机器码到指令集、二进制到十进制、汇编语言到高级编程语言的过程，让类型定义语法也可以实现编程。
最终我们要实现的斐波那契数列代码是这样的？
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));
}
运行结果如下：
斐波那契数列打印结果
程序完全没问题，完结撒花！
开玩笑的，上面是只一个用了TypeScript类型定义的JavaScript写法，我们其实真正想这样做↓↓↓, 也就是使用TS Type解决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
类型提示
二、我们该怎么做
要想实现斐波那契数列，参考一开始的代码，有基本的比较, 加法, 循环语法, 所以我们也需要使用类型系统依次实现这三种功能
2.1 加法的实现
为了实现加法, 需要先实现一些工具类型
// 元组长度
type Length<T extends any[]> = T['length'];
type one = 1
// 使用extends实现数字相等的比较
type a111 = 0 extends one ? true : false // type a111 = false
type a112 = 1 extends one ? true : false // type a112 = true
range的实现是递归实现的
// 伪代码
function range(n, list=[]){
if(n<=0) return list.length
return range(n-1, [1, ...list])
}
TypeScript的限制, 没有循环, 只能用递归代替循环, 后面会有几个类似的写法, 记住一点：递归有几个出口, 对象就有几个 key, 每个 key 就是一个条件
// 创建指定长度的元组, 用第二个参数携带返回值
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 Ten = Length<Range<10>>;
// type Ten = 10
type Five = Length<Range<5>>;
// type Five = 5
type One = Length<Range<1>>;
有了上面的工具语法，那么实现加法就比较容易了, 只需要求两个元组合并后的长度
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
有了加法，该如何实现减法呢？一般减法和除法都比加法难, 所以我们需要更多的工具类型函数！
2.2 工具函数
2.2.1 实现一些基本工具类型
Shift：删除第一个元素Append：在元组末尾插入元素IsEmpty/NotEmpty：判断列表为空
// 去除元组第一个元素 [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]
// 向元组中追加
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
2.2.2 逻辑类型
And：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
2.2.3 小于等于
伪代码: 主要思想是同时从列表中取出一个元素, 长度先到0的列表比较短
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
}
}
思想：将数字的比较转换为列表长度的比较
// 元组的小于等于 T <= P, 同时去除一个元素, 长度先到0的比较小
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];
// 数字的小于等于
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
2.3 减法的实现
减法有两个思路，列表长度相减求值和数字相减求值
2.3.1 列表减法
默认大减小, 小减大只需要判断下反着来, 然后加个符号就行了, 这里为了简单没有实现，可参考伪代码如下：
// 伪代码
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);
// 元组的减法 T - P, 同时去除一个元素, 长度到0时, 剩下的就是结果, 这里使用第三个参数来携带结果, 每次做一次减法, 向第三个列表里面追加
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
2.3.2 数字减法
思想：将数字转成元组后再比较
// 集合大小不能为负数, 默认大减小
// 数字的减法
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
我们有了这些工具后, 就可以将一开始用JavaScript实现的斐波那契数列的实现代码，翻译为TypeScript类型编码
三、Fib: JS函数 --> TS类型
在JavaScript中，我们使用函数
const fib = (n: number): number => n <= 1 ? n : fib(n - 1) + fib(n - 2);
在TypeScript中，我们使用类型, 其实只是换了一种写法, 用类型函数描述运算, 万变不离其宗~
由于TypeScript递归限制, 并不能求解非常大的项, 不过好玩就完事了~
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
最后，推荐一些其他好玩的项目：
- 《TypeScript类型元编程：实现8位数的算术运算》 - https://zhuanlan.zhihu.com/p/85655537
- 《TypeScript 4.1 新特性:字符串模板类型，Vuex 终于有救了?》 - https://juejin.cn/post/6867785919693832200
- 《Ts 类型系统实现线性查找》 - https://bytedance.feishu.cn/docs/doccney0oWRZMSM1w9e0izshW5d
四、总结
看了TypeScript实现斐波纳切数列这一套操作有没有让你有体验到重回“实现流水线CPU”的实验室时光？
IT在最近几十年的发展突飞猛进，越来越多的“程序员”加入到了互联网行业，在一些高级语言以及开发框架下，“程序员”的编码也只需要关注业务逻辑实现，很少有人会再去关注计算机底层是怎么实现加减乘除的，当然社会在进步，技术也在日新月异地迭代，偶尔驻足，回忆刚接触计算机编程，在命令行输出第一行“Hello World！”代码那时欣喜的自己，也许那是我们都回不去的青春...
腾讯云开发者
