用ts类型系统实现斐波那契数列-一一网

0x00 我们要做什么

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));
}
复制代码

我们获得如下输出, 完结撒花 ✿✿ヽ(°▽°)ノ✿

然而我们其实真正想这样做↓↓↓, 也就是使用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
复制代码

1×00 我们该怎么做

fib中有基本的比较, 加法, 循环, 所以我们也需要使用类型系统依次实现

1×01 加法

为了实现加法, 需要先实现一些工具类型

// 元组长度
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]);
}
复制代码

ts的限制, 没有循环, 只能用递归代替循环, 后面会有几个类似的写法, 记住一点, 递归有几个出口, 对象就有几个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
复制代码

但是如何实现减法呢？一般减法和除法都比加法难, 所以我们需要更多的工具

1×02 比较函数

一些工具类型

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 extends 0 ? true : false;
type NotEmpty<T extends any[]> = IsEmpty extends true ? false : true;
type t4 = IsEmpty<Range<0>>;
// type t4 = true
type t5 = IsEmpty<Range<1>>;
// type t5 = false

逻辑类型

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

小于等于

伪代码:

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
复制代码

1×03 减法

列表减法

默认大减小, 小减大只需要判断下反着来, 然后加个符号就行了, 这里为了简单没有实现

// 伪代码
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, Append<R>>;
}[Length<T> extends Length<P> ? 0 : 1];

type t13 = SubList<Range<10>, Range<5>>;
// type t13 = 5
复制代码

数字减法

其实只是将数字转成元组后再比较

// 集合大小不能为负数, 默认大减小
// 数字的减法
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
复制代码

我们有了这些工具后, 就可以将js翻译为ts

2×00 Fib: JS函数 –> TS类型

在js中，我们使用函数

const fib = (n: number): number => n <= 1 ? n : fib(n - 1) + fib(n - 2);
复制代码

在ts中，我们使用类型, 其实只是换了一种写法, 万变不离其宗~

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
复制代码

我还有很多好玩的想法, 可惜这里地(dian)方(zan)太少写不下了, 你懂得 \(^o^)/~