How to Make Fibonacci Confusing

时间：2022-05-23 23:52:01

前几天同事发了这么一段代码：

(fn =>

  (f => f(f))(f => fn(n => f(f)(n))))(g => n =>

  [1, 2].indexOf(n) > -1 ? 1 : g(n - 1) + g(n - 2)

)(10);

你看这段代码时，一定是这样的心情：

How to Make Fibonacci Confusing

好端端的 斐波那契 是怎么变成这样的，因吹斯听，我们来回放一下。

从正常的写法开始：

const fib = n =>

  [1, 2].indexOf(n) >= 0

    ? 1

    : fib(n - 1) + fib(n - 2);

为了让上面看起来不像递归，改写一下，把递归调用改成调用参数 g：

const wrappedFib = g => n =>

  [1, 2].indexOf(n) >= 0

    ? 1

    : g(n - 1) + g(n - 2);

不管 g 传什么，例如就传 null，1,2 两项都可以计算了，因为压根和 g 无关。

wrappedFib(null)(1);

wrappedFib(null)(2);

如果要计算第 3 项，那么 g 可以是 wrappedFib(null)。

let g = wrappedFib(null);

wrappedFib(g)(3);

同理，第 4 项：

let g = wrappedFib(wrappedFib(null));

wrappedFib(g)(4);

第 5 项......第 N 项我就不列了。

看起来需要构造一个 g，它由无限层 wrappedFib 组成。

递归的思想：

const g = n => wrappedFib(g)(n);

运行一下试试吧：

const wrappedFib = g => n =>

  [1, 2].indexOf(n) >= 0

    ? 1

    : g(n - 1) + g(n - 2);

const g = n => wrappedFib(g)(n);

console.log(wrappedFib(g)(10));

g 本身是由无限层 wrappedFib 组成的，所以 wrappedFib(g) 和 g 是等价的。

因此也可以直接调 console.log(g(10))。

const g = n => wrappedFib(g)(n);

又看到了明显的递归对不对，试着把它藏起来。思想跟刚开始一样，通过参数传进来。

这段要花点时间理解。

const g = (f => n =>

  wrappedFib(f(f))(n))(f => n =>

  wrappedFib(f(f))(n)

);

函数本身和函数传参一样，换个写法：

const g = (f => f(f))(f => n =>

  wrappedFib(f(f))(n)

);

能到这里，我们和最终的代码已经很接近了。

把 g 中的 wrappedFib 去掉，通过参数 fn 传进来。

const gWaitForWrappedFib = fn =>

  (f => f(f))(f => n => fn(f(f))(n));

const g = gWaitForWrappedFib(wrappedFib);

好了，去掉常量的定义，全部连起来吧：

(fn =>

  (f => f(f))(f => fn(n => f(f)(n))))(g => n =>

  [1, 2].indexOf(n) > -1 ? 1 : g(n - 1) + g(n - 2)

)(10);

拆解这段代码挺烧脑，膜拜一下代码的作者。

更新

读《The Little Schemer》时发现：这段代码和 Y-Combinator 有关。Mark，以后再写个续。

相关文章