用TypeScript类型系统编程实现斐波那契数列

本文转载自微信公众号「DYBOY」，作者DYBOY。转载本文请联系DYBOY公众号。

创新互联于2013年开始，先为定日等服务建站，定日等地企业，进行企业商务咨询服务。为定日企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

作为一名前端开发者，一定知道TypeScript经常被用于项目中的类型约束，使得在JavaScript这种弱类型语言中有了静态检查的能力，也推进了前端工程化的演进速度，在研究学习TypeScript过程中，我的小伙伴发现了TS的一些好玩儿功能，独乐乐不容众乐乐，遂分享这篇文章给大家。

小伙伴(育豪)的原文可能理解起来有一些难度，笔者有尝试增加一些描述，但想要完全领略TS的“类型体操”的奥妙，还是得实操一番。

一、我们要做什么

我们的目的是想要通过TypeScript的类型声明式语法，编程实现一个斐波那契数列算法。换句话说，类似于用现有的机器码到指令集、二进制到十进制、汇编语言到高级编程语言的过程，让类型定义语法也可以实现编程。

最终我们要实现的斐波那契数列代码是这样的?

 
 
 
 
    
  
  
  
  
  1. const fib = (n: number): number => n <= 1 ? n : fib(n - 1) + fib(n - 2); 
    2.   
  
  
  
  2.  
    3.   
  
  
  
  3. for (let i = 0; i < 10; i++) { 
    4.   
  
  
  
  4.   console.log(i, fib(i)); 
    5.   
  
  
  
  5. } 
    6.

运行结果如下：

斐波那契数列打印结果

程序完全没问题，完结撒花!

开玩笑的，上面是只一个用了TypeScript类型定义的JavaScript写法，我们其实真正想这样做↓↓↓, 也就是使用TS Type解决FIbonacci

 
 
 
 
    
  
  
  
  
  1. import { Fib, Add } from './fib-type'; 
    2.   
  
  
  
  2.  
    3.   
  
  
  
  3. type one = Fib<1>; 
    4.   
  
  
  
  4. type zero = Fib<0>; 
    5.   
  
  
  
  5. type Two = Add; 
    6.   
  
  
  
  6. type Five = Add>; 
    7.   
  
  
  
  7. type Fib5 = Fib; 
    8.   
  
  
  
  8. type Fib9 = Fib<9>; 
    9.   
  
  
  
  9. type r0 = Fib; // type r0= 0 
    10.   
  
  
  
  10. type r1 = Fib; // type r1 = 1 
    11.   
  
  
  
  11. type r2 = Fib; // type r2 = 1 
    12.   
  
  
  
  12. type r3 = Fib<3>; // type r3 = 2 
    13.   
  
  
  
  13. type r4 = Fib<4>; // type r4 = 3 
    14.   
  
  
  
  14. type r5 = Fib<5>; // type r5 = 5 
    15.   
  
  
  
  15. type r6 = Fib<6>; // type r6 = 8 
    16.   
  
  
  
  16. type r9 = Fib<9>; // type r9 = 34 
    17.   
  
  
  
  17. type sum = Add; // type sum = 42 
    18.

类型提示

二、我们该怎么做

要想实现斐波那契数列，参考一开始的代码，有基本的比较, 加法, 循环语法, 所以我们也需要使用类型系统依次实现这三种功能

2.1 加法的实现

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

 
 
 
 
    
  
  
  
  
  1. // 元组长度 
    2.   
  
  
  
  2. type Length = T['length']; 
    3.   
  
  
  
  3. type one = 1  
    4.   
  
  
  
  4.  
    5.   
  
  
  
  5. // 使用extends实现数字相等的比较 
    6.   
  
  
  
  6. type a111 = 0 extends one ? true : false // type a111 = false 
    7.   
  
  
  
  7. type a112 = 1 extends one ? true : false // type a112 = true 
    8.

range的实现是递归实现的

 
 
 
 
    
  
  
  
  
  1. // 伪代码 
    2.   
  
  
  
  2. function range(n, list=[]){ 
    3.   
  
  
  
  3.   if(n<=0) return list.length 
    4.   
  
  
  
  4.   return range(n-1, [1, ...list]) 
    5.   
  
  
  
  5. } 
    6.

TypeScript的限制, 没有循环, 只能用递归代替循环, 后面会有几个类似的写法, 记住一点：递归有几个出口, 对象就有几个 key, 每个 key 就是一个条件

 
 
 
 
    
  
  
  
  
  1. // 创建指定长度的元组, 用第二个参数携带返回值 
    2.   
  
  
  
  2. type Range = { 
    3.   
  
  
  
  3.   0: Range; 
    4.   
  
  
  
  4.   1: P; 
    5.   
  
  
  
  5. }[Length
     extends T ? 1 : 0]; 
    6.   
  
  
  
  6.  
    7.   
  
  
  
  7. // 拼接两个元组 
    8.   
  
  
  
  8. type Concat = [...T, ...P]; 
    9.   
  
  
  
  9.  
    10.   
  
  
  
  10. type t1 = Range<3>; 
    11.   
  
  
  
  11. // type t1 = [any, any, any] 
    12.   
  
  
  
  12.  
    13.   
  
  
  
  13. type Zero = Length>; 
    14.   
  
  
  
  14. //   type Zero = 0 
    15.   
  
  
  
  15. type Ten = Length>; 
    16.   
  
  
  
  16. // type Ten = 10 
    17.   
  
  
  
  17.  
    18.   
  
  
  
  18. type Five = Length>; 
    19.   
  
  
  
  19. // type Five = 5 
    20.   
  
  
  
  20.  
    21.   
  
  
  
  21. type One = Length>; 
    22.

有了上面的工具语法，那么实现加法就比较容易了, 只需要求两个元组合并后的长度

 
 
 
 
    
  
  
  
  
  1. type Add = Length< 
    2.   
  
  
  
  2.    Concat, Range
    > 
    3.   
  
  
  
  3.  >; 
    4.   
  
  
  
  4.  type Two = Add; 
    5.   
  
  
  
  5.  //   type Two = 2 
    6.   
  
  
  
  6.  type Three = Add; 
    7.   
  
  
  
  7.  // type Three = 3 
    8.

有了加法，该如何实现减法呢?一般减法和除法都比加法难, 所以我们需要更多的工具类型函数!

2.2 工具函数

2.2.1 实现一些基本工具类型

  • Shift：删除第一个元素
  • Append：在元组末尾插入元素
  • IsEmpty / NotEmpty：判断列表为空
 
 
 
 
    
  
  
  
  
  1. // 去除元组第一个元素 [1,2,3] -> [2,3] 
    2.   
  
  
  
  2. type Shift = ((...t: T) => any) extends ( 
    3.   
  
  
  
  3.   _: any, 
    4.   
  
  
  
  4.   ...Shift: infer P 
    5.   
  
  
  
  5. ) => any 
    6.   
  
  
  
  6.   ? P 
    7.   
  
  
  
  7.   : []; 
    8.   
  
  
  
  8.  
    9.   
  
  
  
  9. type pp = Shift<[number, boolean,string, Object]> 
    10.   
  
  
  
  10. // type pp = [boolean, string, Object] 
    11.   
  
  
  
  11.  
    12.   
  
  
  
  12. // 向元组中追加 
    13.   
  
  
  
  13. type Append = [...T, E]; 
    14.   
  
  
  
  14. type IsEmpty = Length extends 0 ? true : false; 
    15.   
  
  
  
  15. type NotEmpty = IsEmpty extends true ? false : true; 
    16.   
  
  
  
  16. type t4 = IsEmpty>; 
    17.   
  
  
  
  17. // type t4 = true 
    18.   
  
  
  
  18.  
    19.   
  
  
  
  19. type t5 = IsEmpty>; 
    20.   
  
  
  
  20. // type t5 = false 
    21.

2.2.2 逻辑类型

  • And：a && b
 
 
 
 
    
  
  
  
  
  1. // 逻辑操作 
    2.   
  
  
  
  2. type And = T extends false 
    3.   
  
  
  
  3.   ? false 
    4.   
  
  
  
  4.   : P extends false 
    5.   
  
  
  
  5.   ? false 
    6.   
  
  
  
  6.   : true; 
    7.   
  
  
  
  7. type t6 = And; 
    8.   
  
  
  
  8. // type t6 = true 
    9.   
  
  
  
  9.  
    10.   
  
  
  
  10. type t7 = And; 
    11.   
  
  
  
  11. // type t7 = false 
    12.   
  
  
  
  12.  
    13.   
  
  
  
  13. type t8 = And; 
    14.   
  
  
  
  14. // type t8 = false 
    15.   
  
  
  
  15.  
    16.   
  
  
  
  16. type t9 = And; 
    17.   
  
  
  
  17. // type t9 = false 
    18.

2.2.3 小于等于

伪代码: 主要思想是同时从列表中取出一个元素, 长度先到0的列表比较短

 
 
 
 
    
  
  
  
  
  1. function dfs (a, b){ 
    2.   
  
  
  
  2.     if(a.length && b.length){ 
    3.   
  
  
  
  3.         a.pop() 
    4.   
  
  
  
  4.         b.pop() 
    5.   
  
  
  
  5.         return dfs(a,b) 
    6.   
  
  
  
  6.     }else if(a.length){ 
    7.   
  
  
  
  7.         a >= b 
    8.   
  
  
  
  8.     }else if (b.length){ 
    9.   
  
  
  
  9.         b > a 
    10.   
  
  
  
  10.     } 
    11.   
  
  
  
  11. } 
    12.

思想：将数字的比较转换为列表长度的比较

 
 
 
 
    
  
  
  
  
  1. // 元组的小于等于   T <= P, 同时去除一个元素, 长度先到0的比较小 
    2.   
  
  
  
  2. type LessEqList = { 
    3.   
  
  
  
  3.   0: LessEqList, Shift
    >; 
    4.   
  
  
  
  4.   1: true; 
    5.   
  
  
  
  5.   2: false; 
    6.   
  
  
  
  6. }[And, NotEmpty
    > extends true 
    7.   
  
  
  
  7.   ? 0 
    8.   
  
  
  
  8.   : IsEmpty extends true 
    9.   
  
  
  
  9.   ? 1 
    10.   
  
  
  
  10.   : 2]; 
    11.   
  
  
  
  11.  
    12.   
  
  
  
  12.  
    13.   
  
  
  
  13. // 数字的小于等于 
    14.   
  
  
  
  14. type LessEq = LessEqList, Range
    >; 
    15.   
  
  
  
  15.  
    16.   
  
  
  
  16. type t10 = LessEq; 
    17.   
  
  
  
  17. // type t10 = true 
    18.   
  
  
  
  18. type t11 = LessEq; 
    19.   
  
  
  
  19. // type t11 = false 
    20.   
  
  
  
  20.  
    21.   
  
  
  
  21. type t12 = LessEq; 
    22.   
  
  
  
  22. // type t12 = true 
    23.

2.3 减法的实现

减法有两个思路，列表长度相减求值和数字相减求值

2.3.1 列表减法

默认大减小, 小减大只需要判断下反着来, 然后加个符号就行了, 这里为了简单没有实现，可参考伪代码如下：

 
 
 
 
    
  
  
  
  
  1. // 伪代码 
    2.   
  
  
  
  2. const a = [1, 2, 3]; 
    3.   
  
  
  
  3. const b = [4, 5]; 
    4.   
  
  
  
  4. const c = []; 
    5.   
  
  
  
  5. while (b.length !== a.length) { 
    6.   
  
  
  
  6.   a.pop(); 
    7.   
  
  
  
  7.   c.push(1); 
    8.   
  
  
  
  8. }// c.length === a.length - b.lengthconsole.log(c.length); 
    9.   
  
  
  
  9.  
    10.   
  
  
  
  10. // 元组的减法 T - P, 同时去除一个元素, 长度到0时, 剩下的就是结果, 这里使用第三个参数来携带结果, 每次做一次减法, 向第三个列表里面追加 
    11.   
  
  
  
  11. type SubList = { 
    12.   
  
  
  
  12.   0: Length; 
    13.   
  
  
  
  13.   1: SubList, P, Apped>; 
    14.   
  
  
  
  14. }[Length extends Length
     ? 0 : 1]; 
    15.   
  
  
  
  15. type t13 = SubList, Range<5>>; 
    16.   
  
  
  
  16. // type t13 = 5 
    17.

2.3.2 数字减法

思想：将数字转成元组后再比较

 
 
 
 
    
  
  
  
  
  1. // 集合大小不能为负数, 默认大减小 
    2.   
  
  
  
  2. // 数字的减法 
    3.   
  
  
  
  3. type Sub = { 
    4.   
  
  
  
  4.   0: Sub; 
    5.   
  
  
  
  5.   1: SubList, Range
    >; 
    6.   
  
  
  
  6. }[LessEq extends true ? 0 : 1]; 
    7.   
  
  
  
  7.  
    8.   
  
  
  
  8. type t14 = Sub; 
    9.   
  
  
  
  9. //   type t14 = 1 
    10.   
  
  
  
  10. type t15 = Sub; 
    11.   
  
  
  
  11. // type t15 = 5 
    12.

我们有了这些工具后, 就可以将一开始用JavaScript实现的斐波那契数列的实现代码，翻译为TypeScript类型编码

三、Fib: JS函数 --> TS类型

在JavaScript中，我们使用函数

 
 
 
 
    
  
  
  
  
  1. const fib = (n: number): number => n <= 1 ? n : fib(n - 1) + fib(n - 2); 
    2.

在TypeScript中，我们使用类型, 其实只是换了一种写法, 用类型函数描述运算, 万变不离其宗~

由于TypeScript递归限制, 并不能求解非常大的项, 不过好玩就完事了~

 
 
 
 
    
  
  
  
  
  1. export type Fib = { 
    2.   
  
  
  
  2.   0: T; 
    3.   
  
  
  
  3.   1: Add>, Fib>>; 
    4.   
  
  
  
  4. }[LessEq extends true ? 0 : 1]; 
    5.   
  
  
  
  5.  
    6.   
  
  
  
  6. type r0 = Fib; 
    7.   
  
  
  
  7. // type r10= 0 
    8.   
  
  
  
  8. type r1 = Fib; 
    9.   
  
  
  
  9. // type r1 = 1 
    10.   
  
  
  
  10.  
    11.   
  
  
  
  11. type r2 = Fib; 
    12.   
  
  
  
  12. // type r2 = 1 
    13.   
  
  
  
  13.  
    14.   
  
  
  
  14. type r3 = Fib<3>; 
    15.   
  
  
  
  15. // type r3 = 2 
    16.   
  
  
  
  16.  
    17.   
  
  
  
  17. type r4 = Fib<4>; 
    18.   
  
  
  
  18. // type r4 = 3 
    19.   
  
  
  
  19.  
    20.   
  
  
  
  20. type r5 = Fib<5>; 
    21.   
  
  
  
  21. //type r5 = 5 
    22.   
  
  
  
  22.  
    23.   
  
  
  
  23. type r6 = Fib<6>; 
    24.   
  
  
  
  24. //   type r6 = 8 
    25.

最后，推荐一些其他好玩的项目：

  • 《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!”代码那时欣喜的自己，也许那是我们都回不去的青春...

本文标题：用TypeScript类型系统编程实现斐波那契数列
分享网址：http://www.36103.cn/qtweb/news22/28022.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

定制开发知识

行业网站建设

川西大数据中心　　 　成都小程序开发　　 　马边网站建设　　 　成都主机租用　　 　新都网站建设　　 　网站建设费用　　 　app网站建设　　 　网站建设公司　　 　安卓开发　　 　成都网站设计　　 　网站制作　　 　东电技改　　 　企业网站维护　　 　成都网站制作　　 　关键词排名优化　　 　400电话申请　　 　成都网站托管　　 　达州博佩科技　　 　红锐电子　　 　南宁旺客科技