Y组合子推导(ES6版)

网上以“Y组合子”为关键字搜,结果其实挺多的,这里只是以我个人的理解再推一遍。

在日常开发中,Y组合子除了可以实现匿名递归以外好像也没有其他用,不过推导的过程倒是挺有意思,这里记录下。

另外,对相关问题感兴趣的可以看看《康托尔、哥德尔、图灵——永恒的金色对角线》这篇有意思的文章。

推导前的几个共识:

  1. 如何让下例函数体中不出现console.log
const log = info => console.log(info)
//  升高一阶然后立即执行降一阶
const log =  (fn => info => fn(info))(console.log)
  1. 如何惰性求值?
const fn = cb => {
    // cb 永远不会执行
    if(false) cb("Hello World!")
}
const genCb = msg1 => {
    console.log("可能是个耗时的任务..")
    return msg2 => console.log(`${msg1} ${msg2}`) 
}
// 下例中,尽管fn中的cb永远不会被调用,但genCb还是被执行了
fn(genCb('Hello'))
// 在不改变 fn 与 genCb 的情况下,如何让genCb延迟计算呢?
// 可以试试这个方法:
// 原理是对fn的参数(需是函数)升高一阶,然后在其被执行时自调用一次再执行原来的逻辑
fn((...arg) => genCb('Hello')(...arg))

下面开始推导,以阶乘为例:

const F = x => x ? x * F(x-1) : 1

根据共识1,我们将依赖的F提前出来:

// 这里注意,提取F为参数f后,里面的F(x-1)调用也要改为递归形式f(f,x-1)
const F = (f, x) => x ? x * f(f, x-1) : 1
 // 试下效果
// F(F, 5) // 120

柯里化为单参形式

// f(f, x-1)也要随之变为f(f)(x-1)
const F = f => x => x ? x * f(f)(x-1) : 1
// 再验算下
// F(F)(5) // 120

对于F(F),根据共识1用高阶函数来表示就是:

(f => f(f))(F)

代入前面推导出的F,我们现在得到:

(f => f(f))(f => x => x ? x * f(f)(x-1) : 1)

为了看起来不那么闪眼睛,后面将(f => f(f))A表示:

A(f => x => x ? x * f(f)(x-1) : 1)

接下来想办法从上面的式子中提取出原阶乘函数x => x ? x * f(x-1) : 1,使得其他部分一般化。对比发现,差别在于f(f)(x-1).

根据共识1,我们将f(f)提出去,作为参数传入,得到:

A(f => (g => x => x ? x * g(x-1) : 1)(f(f)))

这里有个问题,最后的f(f)作为参数会被立即求值而没经过条件判断,形成了无限递归,这里按共识2处理一下:

A(f => (g => x => x ? x * g(x-1) : 1)(n => f(f)(n)))

我们将g => x => x ? x * g(x-1) : 1部分用Fn来表示:

A(f => Fn(n => f(f)(n)))

紧接着将Fn 依据共识1往外拧,作为参数传入:

(g => A(f => g(n => f(f)(n))))(Fn)

现在将A所代表的(f => f(f))代回原函数体,得到:

(g => (f => f(f))(f => g(n => f(f)(n))))(Fn)

Y组合子就是前面这部分啦:

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

验算下:

// 阶乘
Y(fac => n => n ? n * fac(n - 1) : 1)(5) // 120
// 斐波拉契
Y(fib => n => n >1 ? fib(n - 2) + fib(n - 1) : 1)(5) // 8

是不是有些绕,但还是蛮有趣的?

哎, 老乡别走呀,不喜欢Y组合子,这里有Z组合子了解下?另外,B、C、K、I、S..也可以看看