背景
接触 TypeScript 已经有一段时间了,这期间写过一些复杂的类型(例如 这篇文章),我开始意识到:TypeScript 的类型系统写起来就像函数式编程一样。去年某天,一个同事给我发了个链接,里面讲的是“TypeScript 类型系统的图灵完备”,里面的一些内容我还在努力理解到可以分享的程度,但一些代码差不多可以说明 TypeScript 类型系统跟函数式编程的思想非常接近了。
前期知识
- 掌握 TypeScript 的 基本类型,相信大家都了解;
- 掌握 TypeScript 的 高级类型 和 泛型;
- 非常熟悉
extends
和infer
的使用; - “函数式编程”的概念,相信大家都或多或少从公众号里面听到过。
文中接下来所有跟 TypeScript 相关的部分,除非特殊说明,否则“函数”、“参数”均为新的概念,而非 TypeScript 中的“函数类型”、“参数列表”。
免责声明
- 本文只是讲述一个“理论上”可行的东西,并非推荐大家日常这样写。事实上,类型标注应当在适当精确的情况下尽可能简洁(参考
@types/ramda
中对于pipe
等函数的类型标注),因为需要提高效率; - 本文的代码实现均只停留在实验室阶段,不考虑可能的性能问题。
从函数式编程说起
函数式编程有以下几个特点:
- 描述映射:函数式编程并非描述解决问题的步骤,而是描述输入与输出的某种映射关系;
- 不可变量:函数式编程中没有所谓的“变量赋值”,只有“参数绑定”,一旦某个参数绑定了一个值,则不能被重新绑定;
- 无副作用:函数的输出只依赖于输入的参数,入参相同则返回值一定相同,函数运行过程中也不会对外界产生任何影响。
- 惰性求值:只有真正用到的值才需要被计算;
- 函数是一等公民:函数可以(甚至经常)作为另一个函数的参数和返回值,if 等语句也是函数;
例如下面的代码:
/**
* 简单的斐波那契数列
*/
function fibonacci(n) {
return n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}
/**
* 简单的欧几里得算法
*/
function gcd(x, y) {
return y === 0 ? x : gcd(y, x % y);
}
/**
* 超运算函数
* https://en.wikipedia.org/wiki/Hyperoperation
* n = 0: b+1(后继)
* n = 1: a+b(加法,即 b 次 a 的后继)
* n = 2: a*b(乘法,即 b 个 a 相加)
* n = 3: a^b(乘方,即 b 个 a 相乘)
* n = 4: a^a^a^...^a(超幂,即 b 个 a 不断乘方)
* \_________/
* b 个 a
* n = …………
*/
function hyperoperation(n, a, b) {
return n === 0
? b + 1
: n === 1 && b === 0
? a
: n === 2 && b === 0
? b
: n > 2 && b === 0
? 1
: hyperoperation(n - 1, a, hyperoperation(n, a, b - 1));
}
由于函数式编程经常出现递归,专门的语言(Haskell 等)会将尾递归转换为循环,以提升运行效率;此外由于函数式编程有“无副作用”的特性,也可以使用记忆化等方式避免重复计算。
TypeScript 泛型的例子
在 TypeScript 中,我们偶尔会用到泛型,比如下面的冷饭(你猜对了,这些都出自本文的第一个链接):
type InstanceType<T> =
T extends ConstructorType<infer R>
? R
: T;
type RemovePropOptions<T> =
NonNullable<
T extends PropOptions<infer R>
? R
: null
>;
type OneOfTypePropOptions<T> =
T extends ArrayType
? RemovePropOptions<ValueOf<T>>
: T;
type ShapePropOptions<T> =
T extends ShapeType
? { [K in keyof T]: RemovePropOptions<T[K]> }
: T;
乍看上去,TypeScript 的泛型长得很像函数:定义泛型相当于定义一个函数,其中的 T
、R
等类型变量可以被看作参数。但通过不断尝试外加查资料,我们最终都会意识到:在 TypeScript 的泛型定义中是无法自由的定义变量并赋值的,这意味着它跟我们日常写的函数还有一些区别。
然鹅大家是否觉得这种写法跟函数式编程有点眼熟?有没有可能用 TypeScript 类型系统来重写上面的函数式编程代码呢?
不管有没有意义,我们先试着用易于理解、但是错误的语法写一下(为了避免高亮出现混乱,这段代码就不加高亮了):
type Fibonacci<N> =
N <= 1 ? 1 : Fibonacci<N - 1> + Fibonacci<N - 2>;
type Gcd<X, Y> =
Y = 0 ? X : Gcd<Y, X % Y>;
type Hyperoperation<N, A, B> =
N = 0
? B + 1
: N = 1 & B = 0
? A
: N = 2 & B = 0
? B
: N > 2 & B = 0
? 1
: Hyperoperation<N - 1, A, Hyperoperation<N, A, B - 1>>;
从零开始的造轮子生活
Emmm……虽然看起来挺容易理解的,但这毕竟完全不是 TypeScript……为了用真正的 TypeScript 来编写这段代码,我们来看看究竟需要哪些轮子(工具类型)。
定义“类型”
首先,为了能让 TypeScript 允许我们对泛型参数做一些操作(例如取长度),我们需要先定义一些类型。在这里我们抛开 JavaScript 的一切知识,因为在 TypeScript 类型系统的世界中,我们目前一无所有——这意味着我们要从最基础的开始定义:
// 用字符串来代替逻辑值
type Bool = 'true' | 'false';
// 用数组的长度作为数字的大小
type Int = any[];
// 第一个数字
type _0 = [];
简单的代数系统
除了“类型”以外,映入眼帘的就是 <=
、+
、-
等符号。我们需要先实现一个简单的代数系统。为了简单起见,我们假设所有的数字都是非负整数。
首先从“后继”运算开始,期望的效果如下:
type Next<I extends Int> = Prepend<any, I>;
type _1 = Next<_0>; // [any]
type _2 = Next<_1>; // [any, any]
type _3 = Next<_2>; // [any, any, any]
这里的 Prepend
该如何实现呢?有一个很 Tricky 的方法,我们构造一个函数,它的参数类型是 any
+ any[]
,然后通过 extends
和 infer
将真正的参数类型提取出来:
type Prepend<E, T extends Int> =
((e: E, ...list: T) => any) extends ((...list: infer R) => any)
? R : T;
同理,我们需要一个 Prev
函数,它是 Next
函数的逆运算,我们可以用函数式编程中常用的 Tail
来实现:
type Tail<T extends Int> =
((...t: T) => any) extends ((_: any, ...tail: infer R) => any)
? R : [];
type Prev<I extends Int> = Tail<I>;
type __2 = Prev<_3>; // [any, any]
加法就是不断地调用 Next
:
type Add<A extends Int, B extends Int> =
B extends _0 ? A : Add<Next<A>, Prev<B>>;
// ^^^^^^^^^^^^^^^^^^^^^
然而如果这样写,TypeScript 在推导时会无法确定 Add
究竟是个什么类型(报错 ts(2456)
,因为它在每一层都无法得到一个确定的结果),所以需要一点变通。下面一种写法可以让 TypeScript 在递归的每一层都有一个确定的结果:
type Add<A extends Int, B extends Int> = {
'true': A
'false': Add<Next<A>, Prev<B>>
}[B extends _0 ? 'true' : 'false'];
type _4 = Add<_1, _3>; // [any, any, any, any]
type _5 = Add<_2, _3>; // [any, any, any, any, any]
注意:TypeScript 在递归超过 50 层之后,会强行推导为 any
,所以实际上来讲,我们目前的代码无法处理 50 以上的加法。
当然,其中的 B extends _0 ? 'true' : 'false'
可以抽成一个工具函数:
type Eq<A extends Int, B extends Int> = A extends B ? 'true' : 'false';
type Add<A extends Int, B extends Int> = {
'true': A
'false': Add<Next<A>, Prev<B>>
}[Eq<B, _0>];
减法也可以通过类似的方式写出来:
type Sub<A extends Int, B extends Int> = {
'true': A
'false': Sub<Prev<A>, Prev<B>>
}[Eq<B, _0>];
type __3 = Sub<_5, _2>; // [any, any, any]
乘法我们需要写一个辅助函数,因为我们要保存一个累加器:
type _Mul<Counter extends Int, A extends Int, B extends Int> = {
'true': Counter
'false': _Mul<Add<Counter, A>, A, Prev<B>>
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
}[Eq<B, _0>];
type Mul<A extends Int, B extends Int> = _Mul<_0, A, B>;
看似很简单的东西,但是 TypeScript 会报 ts(2589)
,因为它认为这样可能会递归非常深,所以直接拒绝推导。这里可以用 infer
将未来需要的运算提前一些:
type _Mul<Counter extends Int, A extends Int, B extends Int> = {
'true': Counter
'false': Add<Counter, A> extends infer R ? _Mul<R, A, Prev<B>> : never
// ^
}[Eq<B, _0>];
报错变成了 ts(2344)
,说 R
不是一个 Int
。因为 TypeScript 的 infer
是无法预先知道结果的,但我们知道它一定是个 Int
,因此再写一个转换函数 Cast
,相当于强制类型转换(事实上根本没转):
type Cast<X, Y> = X extends Y ? X : Y;
type _Mul<Counter extends Int, A extends Int, B extends Int> = {
'true': Counter
'false': Add<Counter, A> extends infer R ? _Mul<Cast<R, Int>, A, Prev<B>> : never
}[Eq<B, _0>];
type _6 = Mul<_2, _3>; // [any, any, any, any, any, any]
整除和取模通过目前已有的工具函数已经可以写出来了,原理是循环相减,有兴趣的同学可以自行实践一下,开头就用 Div<A extends Int, B extends Int>
和 Mod<A extends Int, B extends Int>
吧。
然后是一些针对布尔值的逻辑运算 And
、Or
、Not
:
type And<A extends Bool, B extends Bool> =
A extends 'false' ? 'false' : B extends 'false' ? 'false' : 'true';
type _and_true_true = And<'true', 'true'>; // 'true'
type _and_true_false = And<'true', 'false'>; // 'false'
type _and_false_true = And<'false', 'true'>; // 'false'
type _and_false_false = And<'false', 'false'>; // 'false'
type Or<A extends Bool, B extends Bool> =
A extends 'true' ? 'true' : B extends 'true' ? 'true' : 'false';
type _or_true_true = Or<'true', 'true'>; // 'true'
type _or_true_false = Or<'true', 'false'>; // 'true'
type _or_false_true = Or<'false', 'true'>; // 'true'
type _or_false_false = Or<'false', 'false'>; // 'false'
type Not<A extends Bool> = A extends 'true' ? 'false' : 'true';
type _not_true = Not<'true'>; // 'false'
type _not_false = Not<'false'>; // 'true'
最后是比较运算符,我们先从小于号开始,首先判断 A
是否是 0
,然后 B
是否是 0
,最后是一个递归。这是一个三叉路口,但对于 TypeScript 来说不在话下:
type Lt<A extends Int, B extends Int> = {
'A = 0': Not<Eq<B, _0>>
'B = 0': 'false'
'other': Lt<Prev<A>, Prev<B>>
}[
A extends _0
? 'A = 0'
: B extends _0
? 'B = 0'
: 'other'
];
type _lt_1_2 = Lt<_1, _2>; // 'true'
type _lt_5_3 = Lt<_5, _3>; // 'false'
type _lt_4_4 = Lt<_4, _4>; // 'false'
其它的符号,其实可以通过 Lt
、Eq
配合 And
、Or
、Not
来实现:
type Lte<A extends Int, B extends Int> =
// 使用 `extends` 和 `infer` 来提前计算 a<b
Lt<A, B> extends infer R
? Or<Cast<R, Bool>, Eq<A, B>>
: never;
type Gt<A extends Int, B extends Int> = Not<Lte<A, B>>;
type Gte<A extends Int, B extends Int> = Or<Gt<A, B>, Eq<A, B>>;
一个比较完美的实现
有了之前的积累,上面的几个函数就比较好写了:
type Fibonacci<N extends Int> = {
'true': _1
// 使用 `extends` 和 `infer` 来提前计算 f[n-1] 和 f[n-2]
'false': Fibonacci<Sub<N, _1>> extends infer F_N_1
? Fibonacci<Sub<N, _2>> extends infer F_N_2
? Add<Cast<F_N_1, Int>, Cast<F_N_2, Int>>
: never
: never
}[Lte<N, _2>];
type _fibonacci_1 = Fibonacci<_1>; // [any]
type _fibonacci_2 = Fibonacci<_2>; // [any]
type _fibonacci_3 = Fibonacci<_3>; // [any, any]
type _fibonacci_4 = Fibonacci<_4>; // [any, any, any]
type _fibonacci_5 = Fibonacci<_5>; // [any, any, any, any, any]
type _fibonacci_6 = Fibonacci<_6>; // [any, any, any, any, any, any, any, any]
type Gcd<X extends Int, Y extends Int> = {
'true': X
'false': Gcd<Y, Mod<X, Y>>
}[Eq<Y, _0>]
type H<N extends Int, A extends Int, B extends Int> = {
'N = 0': Next<B>
'N = 1 & B = 0': A
'N = 2 & B = 0': _0
'N > 2 & B = 0': _1
// 使用 `extends` 和 `infer` 来提前计算 h(n, a, b-1)
'other': H<N, A, Prev<B>> extends infer R ? H<Prev<N>, A, Cast<R, Int>> : never
}[
Eq<N, _0> extends 'true'
? 'N = 0'
: And<Eq<N, _1>, Eq<B, _0>> extends 'true'
? 'N = 1 & B = 0'
: And<Eq<N, _2>, Eq<B, _0>> extends 'true'
? 'N = 2 & B = 0'
: And<Gt<N, _2>, Eq<B, _0>> extends 'true'
? 'N > 2 & B = 0'
: 'other'
]
type _h_0_0_3 = H<_0, _0, _3>; // 3+1=4, [any, any, any, any]
type _h_1_5_6 = H<_1, _5, _6>; // 5+6=11, [any, any, any, any, any, any, any, any, any, any, any]
type _h_2_4_2 = H<_2, _4, _2>; // 4*2=8, [any, any, any, any, any, any, any, any]
type _h_3_3_3 = H<_3, _3, _3>; // 3^3=27, [any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any]
无法实现的问题,以及未来的解决方案
上面的例子看起来很完美、很符合逻辑,但毕竟 TypeScript 类型系统并不是为了函数式编程而服务的,因此也有一些思想是它暂时无法实现的。
注意:只是思想无法实现。TypeScript 类型系统在理想状态下是图灵完备的。
惰性计算
这其实是 TypeScript 目前的定位和设计所导致的。本文的“函数”只是 TypeScript 中普通的“工具类型”,并没有真正的“函数”的功能,所谓的“返回值”也只是跟这个定义的内容等价的“TypeScript 类型”而已。虽然每个工具类型本身写起来是函数式编程,但不同的工具类型却是按照命令式逐一定义并推导的。
函数是一等公民
考虑到这样一个函数,它的输入和输出都是函数:
function compose(...f) {
return f.length === 0
? undefined
: f.length === 1
? f[0]
: (...args) => f[0](compose(...f.slice(1))(args));
}
如果用 TypeScript 类型系统来写,会是什么样的呢?
注意:从这里开始,所有的 TypeScript 代码在本文发布的时期都是错误的,不要模仿。
type Compose<F> =
F['length'] extends 0
? undefined
: F['length'] extends 1
? F[0]
: ########
井号的部分写起来并没有那么直观。事实上,TypeScript 目前不支持高阶工具类型(Higher order types),因此我们没有办法把“函数”作为输入和输出。
未来的解决方案
目前 TypeScript 有这样一个 Proposal:Higher Order, Lamda, Reference types,目前的状态是 Backlog(待办)。它的语法有点类似于 C 里面的函数指针:
type A<T extends string> = { 0: T }
type B<T extends string> = [T]
type C<T extends number> = 42
// Here's our lamda
type Referer<*Ref<X extends string>, T extends string> = Ref<T>
type testA = Referer<A, 'hi'> // { 0: 'hi' }
type testB = Referer<B, 'hi'> // ['hi']
type testC = Referer<C, 'hi'> // ERROR
唯一需要做的就是在“参数”前面加一个星号,表示这个“参数”是一个泛型,这样我们就能将“函数”作为“参数”传进去了。如果用普通的代码来写,大概是这样:
const a = (t: string) => ({ 0: t });
const b = (t: string) => [t];
const c = (t: number) => 42;
// Here's our lamda
const referer = (ref: (x: string) => any, t: string) => ref(t)
const testA = referer(a, 'hi') // { 0: 'hi' }
const testB = referer(b, 'hi') // ['hi']
const testC = referer(c, 'hi') // type mismatch
先不管它以后会不会被实现,至少可以确定的是:如果有了这个功能,上面两个问题就都能解决了:第二个问题无需多讲;对于第一个问题,由于需要支持传入一个泛型,那么支持传入泛型的那个泛型(上文的 Referer
)在传入之前是无法被推导的。作者也说了:In this context, we can say that *
"protects" against immediate evalutation.
做个脑力游戏吧
假如真的有了这个功能,我们该怎么实现 Compose
呢?
type Compose<
F extends Array<*Ref<T extends any>>
> =
F['length'] extends 0
? undefined
: F['length'] extends 1
? F[0]
: ########
这个特性依旧无法让我们在井号的地方直接用 type xxx = yyy
这种方式来定义“函数”。
方法总比困难多,不是不能在定义中定义吗,我在之前先定义好不就可以了?我把井号部分抽成一个辅助函数 P
:
type P<F extends Array<*Ref<T extends any>>> = *(F[0])<Compose<Tail<F>>>;
那么井号的部分就可以直接写 *(P<F>)
了!
然而这有个问题:P
要在 Compose
之前定义,但 P
里面又用到了 Compose
。在函数式编程中有一个方法可以解决:我们可以将 Compose
作为参数传入 P
,就像这样:
type P<
*H<*F extends Array<*Ref<T extends any>>>,
F extends Array<*Ref<T extends any>>
> = *(F[0])<H<Tail<F>>>;
type Compose<
F extends Array<*Ref<T extends any>>
> =
F['length'] extends 0
? undefined
: F['length'] extends 1
? F[0] // is a generic
: *(P<Compose, F>) // is also a generic
更进一步,我们可能可以推出函数式编程中的 Y-组合子,从而从另一个方向上证明了它是图灵等价的。