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,以后再写个续。