关于Y组合子

Y组合子是lambda演算的一部分，属于存粹理论上的东西。

因为lambda演算不能定义名字，但是递归是需要通过名字来调用函数本身的。那么如何构建一个匿名递归函数呢？这就是Y组合子需要解决的问题。

举个简单的例子，一个普通的递归函数：

// 利用递归计算 n+(n-1)+(n-2)+...+1+0
var sum = (n) => {
  if (n===0) {
    return 0
  } else {
    // 通过“sum”标志函数本身，调用自身实现递归
    return n+sum(n-1)
  }
}

有没有某种神奇的力量（Y组合子），把递归函数变成下面的形式：

// Y 就是 Y组合子，sumR 表示 sum recursion
var sum = Y((sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      // 通过调用传进来的参数实现递归
      // sumR 代表 sum recursion
      return n+sumR(n-1)
    }
  }
})

从而在不引用自身而实现递归呢。

这就是今天我们需要做的事情。把这个神奇力量找出来。

推导过程

由于推导过程比较难理解，所以将这个过程分成两个部分。

第一部分，对一个普通函数进行一系列演变，推导出一个能实现递归的函数。

第二部分，对这个递归的函数做等价的转换，从这个递归函数中提取出 Y组合子。

第一部分

因为不能在函数中引用自身，所以我们先定义几个函数

// eternity 函数，是个执行之后无限循环的函数。所以最好别去执行。
// 在这里用 console.error 代替无限循环，以防手贱执行了。。
var eternity = () => {
  // while(true) {}
  console.error('you are in eternity')
}

// sum0 函数，只能处理参数为 0 的情况，传其他参数的话它会疯掉，进入无限循环。。
var sum0 = (n) => {
  if (n===0) {
    return 0
  } else {
    return n+eternity()
  }
}

// sum1 函数，只能处理参数为 0, 1 的情况
var sum1 = (n) => {
  if (n===0) {
    return 0
  } else {
    return n+sum0(n-1)
  }
}

// sum2 函数，只能处理参数为 0, 1, 2 的情况
var sum2 = (n) => {
  if (n===0) {
    return 0
  } else {
    return n+sum1(n-1)
  }
}

假如可以这样一直定义下去，我们就能定义能过处理足够大的 n 的函数。

观察上面的 sum0，sum1，sum2 发现它们有很多相似的地方，很自然想到需要定义一个 mkSum 来生成。

// 生成 sumN 函数
var mkSum = (fn) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+fn(n-1)
    }
  }
}

var sum0 = mkSum(eternity)
var sum1 = mkSum(sum0)
var sum2 = mkSum(sum1)

这样看起来就顺眼很多对不(→_→)

接下来关键的地方要来了，注意集中力了(￣0 ￣)y

因为 eternity 函数是永远不能执行的，既然如此，我干嘛不换成其他函数呢。换什么函数都是一样的，那我就把

eternity 换成 mkSum 吧。

var sum0 = mkSum(mkSum)
var sum1 = mkSum(sum0)
var sum2 = mkSum(sum1)

为了方便观察，我们把 sum1，sum2 展开，得到如下：

var sum0 = mkSum(mkSum)
var sum1 = mkSum(mkSum(mkSum))
var sum2 = mkSum(mkSum(mkSum(mkSum)))

仔细看看上面的三个函数定义，看出来什么了么？

没错！这三个函数全部由 mkSum 组合而成的！！ Σ(っ °Д °;)っ

仔细观察，每次当 sum 要处理的 n 变成 n+1 的时候，只需要把最里面的 mkSum 变成 mkSum(mkSum) 就行了。

只要吧 sum0 最里面的mkSum 替换成 mkSum(mkSum) ，就是 sum1 了。同理， sum1 最里面的 mkSum 替换成 mkSum(mkSum) ，就成了 sum2 。

怎么样，是不是嗅到一点递归的气息啦。最关键的就是怎么在需要的时候把 mkSum 转成 mkSum(mkSum)。

如果可以做到这点，我们就能实现递归了。(ΦωΦ)

接下来放慢脚步，让我们看下 sum0，因为在 sum0 中，传给 mkSum 的参数就是它自身。那我们不妨改下 mkSum 的参数名。为了区别 mkSum，我们改成 mkSum1（其实不区别也可以）。

// 改成参数名 mkSum1 提醒我们传进来的参数就是 mkSum
var mkSum = (mkSum1) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+mkSum1(n-1)
    }
  }
}

var sum0 = mkSum(mkSum)

之前已经提到，推导思想的关键就是在需要的时候，把 mkSum 转成 mkSum(mkSum)。

那什么时候是需要的时候呢？没错，就是递归函数在想要调用自身的时候！。

所以，我们把 mkSum 改造成下面的样子👇：

// 请注视这个函数至少一分钟。好好参悟。(￣ω￣)
var mkSum = (mkSum1) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      // 姨妈大！就是这里！！把 mkSum 改成 mkSum(mkSum)
      return n+mkSum1(mkSum1)(n-1)
    }
  }
}

// 已经实现递归，所以 sum0 已经变成 sum 了
var sum = mkSum(mkSum)

这里就是推导过程中最关键最难理解的地方了，到这一步，已经实现递归的效果了，sum 已经完美可运行。

接下来的就是在对 mkSum 函数进行等价的转换，从而抽象出真正的Y组合子，但请务必弄懂上面的部分才继续看下面的内容。

第二部分

抽象出真正的Y组合子

一个小方法

在下面的推导之前，为了让大家更好理解下面的内容，先写个小方法，下面的推导中很多地方都用的了。

那就是如何把函数中的某些内容提取出来作为参数。

var d = 1, e = 2
// 原函数
var a = c => {
  var b = d + e
  return b + c
}

// 变换形式，将 b 提取出来变成参数形式，和上面的原函数等价
var aCreator = b => c => b+c
var a = aCteator(d+e)

a(10)

在接下来的内容中，凡是涉及到提取某某变成参数形式的说法，都是利用这种方法。

首先，我们简单转换下 mkSum 函数的形式，把 mkSum1(mkSum1) 提取出来变成参数形式。

var mkSum = (mkSum1) => {
  var sumR = mkSum1(mkSum1)
  
  // sumFn 不就是传给 Y组合子 的参数么？！
  var sumFn = (sumR) => {
    (n) => {
      if (n===0) {
        return 0
      } else {
        // 原来的 mkSum1(mkSum1) 被提取到外面，变成 sumR
        return n+sumR(n-1)
      }
    }
  }

  return sumFn(sumR)
}

var sum = mkSum(mkSum)

很简单的提取，用这个函数试下执行 sum(3) 试试？

啊咧？？刚刚明明还很正常的啊，怎么突然就爆栈了？(＃°Д°)

具体的原因就不解释了，自己好好想想就能得出答案了。

为了解决爆栈的问题，mkSum1(mkSum1) 外面裹一层函数就可以了。

var mkSum = (mkSum1) => {
  // 外面裹一层匿名函数，解决栈溢出问题
  var sumR = (x) => mkSum1(mkSum1)(x)
  
  var sumFn = (sumR) => {
    return (n) => {
      if (n===0) {
        return 0
      } else {
        return n+sumR(n-1)
      }
    }
  }

  return sumFn(sumR)
}

var sum = mkSum(mkSum)

接下来把sum中的mkSum提取出来变成参数形式：

var mkSum = (mkSum1) => {
  var sumR = (x) => mkSum1(mkSum1)(x)
  
  var sumFn = (sumR) => {
    return (n) => {
      if (n===0) {
        return 0
      } else {
        return n+sumR(n-1)
      }
    }
  }
  
  return sumFn(sumR)
}

var w = f => f(f)
// 原来的 mkSum(mkSum) 变成了 函数w
var sum = w(mkSum)

我们再把sumFn提取到mkSum外面变成参数形式：

// 被提取出来的 sumFn
var sumFn = (sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+sumR(n-1)
    }
  }
}

var mkSumCreator = (sumFn) => (mkSum1) => {
  var sumR = (x) => mkSum1(mkSum1)(x)
  return sumFn(sumR)  // 原来的 sumFn 已经变成形参了
}
var mkSum = mkSumCreator(sumFn)

var w = f => f(f)
var sum = w(mkSum)

再外面包一层函数，作为 Y组合子的原型

var sumFn = (sumR) => {
  return (n) => {
    if (n === 0) {
      return 0
    } else {
      return n + sumR(n - 1)
    }
  }
}

// 将所有元素包在一个函数中，这个函数就是 Y组合子 的原型
var poorY = () => {
  var mkSumCreator = (sumFn) => (mkSum1) => {
    var sumR = (x) => mkSum1(mkSum1)(x)
    return sumFn(sumR)
  }
  var mkSum = mkSumCreator(sumFn)
  var w = f => f(f)

  return w(mkSum)
}

var sum = poorY()

最后一次，让我们再看一下最终要的效果：

var sumFn = (sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+sumR(n-1)
    }
  }
}
var sum = Y(sumFn)

要怎么才能变成这种形式呢？这一步不是很明显。所以可能需要仔细观察一下。

我们只需要给 poorY 添加一个参数 sumFn，将最外部的 sumFn 作为参数传进来即可。

var sumFn = (sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+sumR(n-1)
    }
  }
}

// 为 poorY 添加一个参数 sumFn
var poorY = (sumFn) => {
   // poorY 函数内部不需要有任何变化
  var mkSumCreator = (sumFn) => (mkSum1) => {
    var sumR = (x) => mkSum1(mkSum1)(x)
    return sumFn(sumR)
  }
  var mkSum = mkSumCreator(sumFn)
  var w = f => f(f)
  return w(mkSum)
}

// sumFn 以参数的形式传进 poorY，而不是作为自由变量
var sum = poorY(sumFn)

这时候，千呼万唤的 Y组合子 终于要出来了，看见没有？！

因为 poorY 内部的 mkSumCreator 是直接调用的，所以可以把它简化一下，这样我们就得到真正的 Y组合子了。

var sumFn = (sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+sumR(n-1)
    }
  }
}

var y = (sumFn) => {
  // 去掉一层调用
  var mkSum = (mkSum1) => {
    var sumR = (x) => mkSum1(mkSum1)(x)
    return sumFn(sumR)
  }

  var w = f => f(f)
  return w(mkSum)
}

var sum = y(sumFn)

最后我们把多余的命名去掉，提取出 Y组合子：

var Y = (sumFn) => {
  var w = f => f(f)
  return w(mkSum1 => {
    var sumR = (x) => mkSum1(mkSum1)(x)
    return sumFn(sumR)
  })
}

var sum = Y((sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+sumR(n-1)
    }
  }
})

简化 Y组合子：

// 参数名替换
// w -> (f => f(f))
// mkSum1 -> b
// sumFn -> fn
var Y = fn => 
  (f => f(f))
  (b => fn( x => b(b)(x) ))

之前讲过 mkSum 和 mkSum1 其实并不需要严格区别。所以，为了更（故）加（作）简（神）化（秘），我们就把它们都替换成 f 吧。

最终 Y组合子：

var Y = fn => 
  (f => f(f))
  (f => fn( x => f(f)(x) ))

// 或者将 f => f(f) 展开
var Y = fn => 
  (f => fn( x => f(f)(x) ))
  (f => fn( x => f(f)(x) ))

细心的朋友应该注意到了，这个 Y 组合子生成的递归函数，只能处理一个参数，也就是 Y 组合子里面的 x 。所以我们可以修改一下，让 Y 组合子生成的递归函数不受参数限制。

var Y = fn => 
  (f => f(f))
  (f => fn( (...x) => f(f)(...x) ))

结尾

推导到此结束，看懂了么？如果没有的话，

可以参考下另一篇文章：https://zhuanlan.zhihu.com/p/20616683 (这篇文章讲得更加透彻)，

或者阅读下 《The Little Schemer》的第九章（本文就是基于这一章写出来的）。

最后要指出的是，在实际应用中，递归的实现并不是靠Y组合子实现的，而是先保存函数的引用（比如指针），然后在需要的时候再通过指针调用自身函数。这和我们的直觉是相符合。

所以，理解Y组合子并没有什么卵用，只是无聊找虐而已。╮(╯▽╰)╭