服务器之家

服务器之家 > 正文

用 TypeScript 实现斐波那契数列

时间:2021-11-01 22:00     来源/作者:windliang

用 TypeScript 实现斐波那契数列

前几天在知乎看到一篇文章,用 TypeScript 类型运算实现一个中国象棋程序 :

用 TypeScript 实现斐波那契数列

边看边 woc,TypeScript 不是一个类型系统吗,咋还实现象棋了,感觉发现了新大陆一样,然后把大佬的代码 clone下来,本地「运行」了一下,只能是带引号的运行了,因为 TS就是动态推导类型,只需要安装相关插件,鼠标 hover 上去就可以看到结果了。

用 TypeScript 实现斐波那契数列

看到这种神奇魔法,于是自己就查了查这是为什么。

图灵完备

这是接触到的第一个概念,维基百科是这样定义的:

一个计算系统可以计算任何图灵-可计算函数,被称作图灵完全(或者图灵完备)。或者任何可以模拟通用图灵机的系统。

可计算函数粗暴的理解为「人能计算的问题」,而现在例如 C++、JAVA几乎所有编程语言都是具有图灵完备性的,关于图灵完备是一个更大的问题,更通俗的解释可以看 什么是图灵完备?知乎这篇回答,很有意思。

https://www.zhihu.com/question/20115374/answer/288346717

还了解到了一门有趣的编程语言 —— 1993 年Urban Müller 发明的Brainfuck 语言,感受一下它怎么打印 Hello World。

  1. ++++++++++initializecounter(cell#0)to10
  2. [uselooptoset70/100/30/10
  3. >+++++++add7tocell#1
  4. >++++++++++add10tocell#2
  5. >+++add3tocell#3
  6. >+add1tocell#4
  7. <<<<-decrementcounter(cell#0)
  8. ]
  9. >++.print'H'
  10. >+.print'e'
  11. +++++++.print'l'
  12. .print'l'
  13. +++.print'o'
  14. >++.print''
  15. <<+++++++++++++++.print'W'
  16. >.print'o'

是的,你没有看错,左边是代码,右边是注释,这里有运行的单句执行图示,可以感受一下:

http://fatiherikli.github.io/brainfuck-visualizer/

用 TypeScript 实现斐波那契数列

上边的纸带代表内存中的情况,然后通过左移右移加加减减,最终输出了 Hello world!。

而在 TypeScript 仓库的一个 issues 中也讨论过 TypeScript 的图灵完备了,作者还分享了一个判断是否是质数的代码,也很有意思。

用 TypeScript 实现斐波那契数列

TypeScript 相关知识

为了实现文章的标题 「用 TypeScript 实现斐波那契数列」,需要先学习下相关的知识点。

泛型

如果之前学过 C++ 或者 Java 之类的语言,对泛型一定不陌生,泛型可以让我们定义函数参数的时候不指定参数类型,用一个占位符代替,当运行的时候再由外界传过来的类型决定。

举个简单的例子,实现两个元素相加,如果用 TypeScript 限制的话,即使是相同的逻辑也要写多次了。

  1. functionaddTwoNumber(a:number,b:number):number{
  2. returna+b;
  3. }
  4. functionaddTwoNumberString(a:string,b:string):string{
  5. returna+b;
  6. }
  7. addTwoNumber(1,3)
  8. addTwoNumberString('1','2');

不然的话就只能 anyScript 了,完全失去了类型校验。

  1. functionaddTwoNumber(a:any,b:any):any{
  2. returna+b;
  3. }
  4. addTwoNumber(1,3)
  5. addTwoNumber('1','2');
  6. addTwoNumber('1',2);//不报错

如果有泛型的话,就既可以达到逻辑的复用,同时对类型进行校验。

  1. functionaddTwoNumber(a:T,b:T):T{
  2. return<any>a+<any>b;//这里需要强制转换下,不然会报Operator'+'cannotbeappliedtotypes'T'and'T'.ts(2365)
  3. }
  4. addTwoNumber(1,3);
  5. addTwoNumber("1","3");
  6. addTwoNumber('1',2);//报错

当然上边有强行用泛型的嫌疑了,不过能大体理解泛型的作用就好,哈哈。上边的情况用 TS 的重载会更好些。

类型 type

TS 中除了基本的类型,number、string 、number[] 等,比较特殊的地方 1 、abc 、true 也可以单独算一个类型。1 的类型是 1,当然也属于 number。

最重要的是 TS 允许我们定义新的类型,而且我们还可以通过泛型变量,进行类型的运算然后产生新的类型。举几个例子:

  1. typeType1=Textendsnumber?number:string;
  2. typeType2=Type1<2121>;//此时Type2就相当于number
  3. typeType3=Type1<{}>;//此时Type3就相当于string

exstends 和后边的 ? 构成了一个三元表达式,如果 extends 前面的类型能够赋值给 extends 后面的类型,那么表达式判断为真,否则为假。

因为单个数字也是一个类型,所以我们就可以判断传入的 T 是否等于某个数。

  1. typeType4=Textends1?true:false;
  2. typeType5=Type4<2121>;//此时Type5就相当于false类型
  3. typeType6=Type4<1>;//此时Type6就相当于true类型

可以仔细体会一下这里,很关键,后边写斐波那契数列的时候,一不小心就会被绕进去,因为我们是在操控类型之间的运算,和平时的编程感觉很不一样。

一句话总结,每个类型可以看成一个函数,传入的泛型是函数参数,并且也是一个类型,最后再返回一个新的类型。

  1. Type(type,type)=>type

infer

infer 表示在 extends 条件语句中待推断的类型变量。

简单理解,我们是为了判断某个类型是否 extends 某个「结构」,但结构中参数的类型我们并不知道,此时我们写一个 infer R(R只是占位,任何名字都可以),在类型推导的时候,R 就是当前类型真正的参数类型。举个例子:

我们判断 T 是否是 {a: XXX, b: XXX}的类型,因为 T 是泛型,我们并不知道T 中的 a 是什么类型,此时就可以用 infer 占位。当传入具体的类型是就可以拿到 a 是什么类型了。

  1. typeFoo=Textends{a:inferU;b:inferU}?U:never;
  2. typeT1=Foo<{a:string;b:string}>;//T1类型为string
  3. typeT2=Foo<{a:string;b:number}>;//T2类型为string|number

斐波那契数列

斐波那契数列就不多解释了,先用 js 实现一个斐波那契数列。

  1. functionFibonacci(n){
  2. if(n===1){
  3. return1;
  4. }
  5. if(n===2){
  6. return1;
  7. }
  8. returnFibonacci(n-1)+Fibonacci(n-2);

最关键的递归不用担心,TS 支持类型的递归定义,我们先写一个大概的雏形,看象棋直接用中文定义类型挺有意思,这里也直接中文了。之前总结的那句话这里再加深一下,每个类型可以看成一个函数,传入的泛型是函数参数,并且也是一个类型,最后再返回一个新的类型。

我们先定义「斐波那契」类型,泛型是传入一个数字(这里的数字是当作类型),先判断传入的类型是否是 1 或者 2,然后直接返回 1 类型。

  1. type斐波那契<某数extendsnumber>=某数extends1
  2. ?1
  3. :某数extends2
  4. ?1
  5. :相加<斐波那契<减一<某数>>,斐波那契<减一<减一<某数>>>>;

: 相加<斐波那契<减一<某数>>, 斐波那契<减一<减一<某数>>>>;

上边需要注意的是 <> 里边的 extends 是为了限定传入的类型,和外边的 extends 不一样。

我们还需要定义一个「相加」类型和一个「减一」类型。

相加是两个类型相加,但是类型系统是不支持数字直接相加的,1 + 2 并不能直接相加,这里有个 trick。

数组类型和 js 中的数组一样,同样拥有 length 属性,返回一个具体的数字类型,也支持扩展运算符。举个例子:

  1. typeA=[any,any,any]
  2. typeB=A["length"]//B就是3类型

所以我们可以将数字转为数组,操作数组,然后再将数组通过 length 转回数字。

先写一个得到对应数组的 Type,这里就需要用到递归了。

  1. type得到长度<数组extendsany[]>=数组["length"];
  2. type转为数组<
  3. 某数extendsnumber,
  4. 对应数组extendsany[]=[]//默认值赋一个空数组,外部调用的时候不需要传
  5. >=得到长度<对应数组>extends某数//长度是否等于了需要的长度
  6. ?对应数组//如果长度等于所需要的了就返回
  7. :转为数组<某数,[any,...对应数组]>;//否则再添加一个元素进入数组,然后递归调用

: 转为数组<某数, [any, ...对应数组]>; // 否则再添加一个元素进入数组,然后递归调用

有了转为数组的的 Type,相加方法就很好写了,我们只需要将两个数先转为对应的数组,将两个数组连接,最后返回连接后的数组长度即可。

  1. type相加<某数甲extendsnumber,某数乙extendsnumber>=得到长度<
  2. [...转为数组<某数甲>,...转为数组<某数乙>]
  3. >;

然后定义减一的方法,也就是数组长度减 1,这里就利用到了 infer,还需要利用数组的解构。

  1. type数组减一<某数组类型extendsany[]>=((
  2. ...参数:某数组类型
  3. )=>any)extends(拆一个元素:any,...剩下的数组:infer剩下的数组类型)=>any
  4. ?剩下的数组类型
  5. :[];

我们定义了一个函数类型,通过函数参数的解构,使得剩下的数组少了一个元素。

有了「数组减一」的类型,数字「减一」就水到渠成了,将数字转为对应数组,数组减去一个元素,然后恢复为数字即可。

  1. type减一<某数extendsnumber>=得到长度<数组减一<转为数组<某数>>>;

整体代码就出来了:

  1. type斐波那契<某数extendsnumber>=某数extends1
  2. ?1
  3. :某数extends2
  4. ?1
  5. :相加<斐波那契<减一<某数>>,斐波那契<减一<减一<某数>>>>;
  6. type得到长度<数组extendsany[]>=数组["length"];
  7. type转为数组<
  8. 某数extendsnumber,
  9. 对应数组extendsany[]=[]
  10. >=得到长度<对应数组>extends某数
  11. ?对应数组
  12. :转为数组<某数,[any,...对应数组]>;
  13. type相加<某数甲extendsnumber,某数乙extendsnumber>=得到长度<
  14. [...转为数组<某数甲>,...转为数组<某数乙>]
  15. >;
  16. type数组减一<某数组类型extendsany[]>=((
  17. ...参数:某数组类型
  18. )=>any)extends(拆一个元素:any,...剩下的数组:infer剩下的数组类型)=>any
  19. ?剩下的数组类型
  20. :[];
  21. type减一<某数extendsnumber>=得到长度<数组减一<转为数组<某数>>>;
  22. //测试
  23. type斐波那契八=斐波那契<8>

看下结果:

用 TypeScript 实现斐波那契数列

不过到斐波那契 11 就因为递归层度太深 gg 了。

用 TypeScript 实现斐波那契数列

这里主要就是体验下 TS 的图灵完备,优化就不考虑了。

总结

通过写一个这个例子对 TS 的类型有了更多的了解,但平时开发肯定不会这样搞,主要是写着玩哈哈,毕竟一个简单的斐波那契数列都写的这么麻烦,引用 Linus Torvalds 自传的书名结束吧,Just for Fun!

原文链接:https://mp.weixin.qq.com/s/Etqhtid6G0LtMNYksaQpcw

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部