typescript - 是否可以实现 Y-combinator 的 TypeScript 通用版本？

Question

Y-combinator JavaScript 实现:

const Y = g => (x => g(x(x)))(x => g(x(x)))
//or
const Y = f => {
  const g = x => f(x(x))
  return g(g)
}

我只是好奇，是否可以实现 Y-combinator 的 TypeScript 通用版本？

type Y<F> = ???

Answer 1

简短的回答:
输入为单参数函数的定点组合器的 TypeScript 类型是:type Y = <I, O>(F: (f: (i: I) => O) => ((i: I) => O)) => (i: I) => O;长答案如下:

fixed point combinator的类型应该是以下形式的通用函数:

type Fixed = <T>(f: (t: T) => T) => T;

所以如果你有一个值 fixed类型 Fixed ，你应该能够在任何一个输出与输入相同类型的参数函数上调用它，并且(神奇地？)得到一个结果，它是该函数的一个不动点:

console.log(fixed(Math.cos)) // 0.739085...

对于某些行为良好的函数，您可以得到类似这种行为 f只需从一些随机值开始并迭代 f一堆时间:

const fixed: Fixed = f => {
  let r = null as any;
  for (let i = 0; i < 1000; i++) r = f(r);
  return r;
}

这是一个愚蠢的实现(或者至少不是经典的实现)，但它对于找到一个函数的不动点的正常用例来说已经足够了，该函数的输入本身就是一个函数。
例如，让我们定义一个 protoFactorial其不动点计算 factorial 的函数通过递归的非负整数:

const protoFactorial = (f: (n: number) => number) =>
  (n: number) => n === 0 ? 1 : n * f(n - 1)

注意输入 f是 (n: number) => number 类型的函数，并且输出是该类型的另一个函数，其输入 n是 n是我们要计算其阶乘的数字。如 n是 0它返回 1 ;否则返回 n * f(n - 1) .
如果我们有一个不动点组合器 fixed ，我们应该能够得到所需的阶乘函数，如下所示:

const factorial = fixed(protoFactorial);
console.log(factorial(7)); // 5040

而上面的 fixed确实为此工作。

但是对于 Y 组合器，我们倾向于要求类型 T。它操作的本身就是一个函数类型(尽管在无类型的 lambda 演算中并没有真正的区别)，因此我倾向于给出 Y一个泛型类型，特别依赖于 T 的输入和输出功能类型:

type Y = <I, O>(F: (f: (i: I) => O) => ((i: I) => O)) => (i: I) => O;

那就像 Fixed如果您更换 T与 (i: I) => O .无论如何，有一个值 Y类型 Y ，我们想必应该可以调用 Y(protoFactorial)并得到正确的 factorial .
这是 Y 的实现在 typescript 中:

interface Ω<T> {
  (x: Ω<T>): T;
}

const Y: Y = <I, O>(F: (f: (i: I) => O) => (i: I) => O) =>
  ((x: Ω<(i: I) => O>) => F(x(x)))((x: Ω<(i: I) => O>) => F(x(x)));

请注意，为了强类型 Y 组合器实现，我们需要递归类型 Ω<T> ; x参数必须是这样的类型才能允许像 x(x) 这样的调用。编译并生成 (i: I) => O 类型的输出.
这与您的 g => (x => g(x(x)))(x => g(x(x))) 相同使用 g 实现重命名为 F并带有类型注释以帮助编译器。

这就是所问问题的答案，但不幸的是 Y组合器不能在 JavaScript 中按原样使用，它在评估函数体之前急切地评估所有函数输入:

try {
  const factorial = Y(protoFactorial);
} catch (e) {
  console.log(e); // too much recursion
}

糟糕，调用 Y(protoFactorial)热切地扩展到无止境 F(F(F(F(F(F(....并爆炸。

为了在 JavaScript 中获得可行的定点组合器，我们需要更像 Z combinator 的东西。这会延迟 x(x) 的计算通过使用 eta 抽象(见 What is Eta abstraction in lambda calculus used for?)产生 v => x(x)(v) :

const Z: Y = <I, O>(F: (f: (i: I) => O) => (i: I) => O) =>
  ((x: Ω<(i: I) => O>) => F(v => x(x)(v)))((x: Ω<(i: I) => O>) => F(v => x(x)(v)));

现在如果我们使用 Z代替 Y它在运行时工作:

const factorial = Z(protoFactorial);
// const factorial: (i: number) => number
console.log(factorial(7)); // 5040

当然，如果我们只关心类型并且不需要假装 JavaScript 和 TypeScript 在运行时缺乏一流的递归，那么我们可以只实现类型 Y 的函数。递归地减少麻烦:

const R: Y = f => f(x => R(f)(x))    
console.log(R(protoFactorial)(7)) // 5040

从类型系统的角度来看，所有 fixed , Y , Z , 和 R是 Y 类型的值:

function acceptY(y: Y) { }
acceptY(fixed)
acceptY(Y)
acceptY(Z)
acceptY(R)

所以我们可以相当自信地说，输入是单参数函数的定点组合器的 TypeScript 类型是:

type Y = <I, O>(F: (f: (i: I) => O) => ((i: I) => O)) => (i: I) => O;

Playground link to code