關(guān)于Y組合子

Y組合子是lambda演算的一部分秉扑，屬于存粹理論上的東西。

因為lambda演算不能定義名字气忠，但是遞歸是需要通過名字來調(diào)用函數(shù)本身的邻储。那么如何構(gòu)建一個匿名遞歸函數(shù)呢？這就是Y組合子需要解決的問題旧噪。

舉個簡單的例子吨娜，一個普通的遞歸函數(shù)：

// 利用遞歸計算 n+(n-1)+(n-2)+...+1+0
var sum = (n) => {
  if (n===0) {
    return 0
  } else {
    // 通過“sum”標(biāo)志函數(shù)本身，調(diào)用自身實現(xiàn)遞歸
    return n+sum(n-1)
  }
}

有沒有某種神奇的力量（Y組合子）淘钟，把遞歸函數(shù)變成下面的形式：

// Y 就是 Y組合子宦赠，sumR 表示 sum recursion
var sum = Y((sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      // 通過調(diào)用傳進(jìn)來的參數(shù)實現(xiàn)遞歸
      // sumR 代表 sum recursion
      return n+sumR(n-1)
    }
  }
})

從而在不引用自身而實現(xiàn)遞歸呢。

這就是今天我們需要做的事情米母。把這個神奇力量找出來勾扭。

推導(dǎo)過程

由于推導(dǎo)過程比較難理解，所以將這個過程分成兩個部分铁瞒。

第一部分妙色，對一個普通函數(shù)進(jìn)行一系列演變，推導(dǎo)出一個能實現(xiàn)遞歸的函數(shù)慧耍。

第二部分身辨，對這個遞歸的函數(shù)做等價的轉(zhuǎn)換，從這個遞歸函數(shù)中提取出 Y組合子芍碧。

第一部分

因為不能在函數(shù)中引用自身煌珊，所以我們先定義幾個函數(shù)

// eternity 函數(shù)，是個執(zhí)行之后無限循環(huán)的函數(shù)泌豆。所以最好別去執(zhí)行定庵。
// 在這里用 console.error 代替無限循環(huán)，以防手賤執(zhí)行了。蔬浙。
var eternity = () => {
  // while(true) {}
  console.error('you are in eternity')
}

// sum0 函數(shù)猪落，只能處理參數(shù)為 0 的情況，傳其他參數(shù)的話它會瘋掉敛滋，進(jìn)入無限循環(huán)许布。兴革。
var sum0 = (n) => {
  if (n===0) {
    return 0
  } else {
    return n+eternity()
  }
}

// sum1 函數(shù)绎晃，只能處理參數(shù)為 0, 1 的情況
var sum1 = (n) => {
  if (n===0) {
    return 0
  } else {
    return n+sum0(n-1)
  }
}

// sum2 函數(shù)，只能處理參數(shù)為 0, 1, 2 的情況
var sum2 = (n) => {
  if (n===0) {
    return 0
  } else {
    return n+sum1(n-1)
  }
}

假如可以這樣一直定義下去杂曲，我們就能定義能過處理足夠大的 n 的函數(shù)庶艾。

觀察上面的 sum0，sum1擎勘，sum2 發(fā)現(xiàn)它們有很多相似的地方咱揍，很自然想到需要定義一個 mkSum 來生成。

// 生成 sumN 函數(shù)
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)

這樣看起來就順眼很多對不(→_→)

接下來關(guān)鍵的地方要來了棚饵，注意集中力了(￣0 ￣)y

因為 eternity 函數(shù)是永遠(yuǎn)不能執(zhí)行的煤裙，既然如此，我干嘛不換成其他函數(shù)呢噪漾。換什么函數(shù)都是一樣的硼砰，那我就把

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)))

仔細(xì)看看上面的三個函數(shù)定義诈胜，看出來什么了么豹障？

沒錯！這三個函數(shù)全部由 mkSum 組合而成的＝剐佟血公！ Σ(っ °Д °;)っ

仔細(xì)觀察，每次當(dāng) sum 要處理的 n 變成 n+1 的時候缓熟，只需要把最里面的 mkSum 變成 mkSum(mkSum) 就行了累魔。

只要吧 sum0 最里面的mkSum 替換成 mkSum(mkSum) ，就是 sum1 了荚虚。同理薛夜， sum1 最里面的 mkSum 替換成 mkSum(mkSum) ，就成了 sum2 版述。

怎么樣梯澜，是不是嗅到一點遞歸的氣息啦。最關(guān)鍵的就是怎么在需要的時候把 mkSum 轉(zhuǎn)成 mkSum(mkSum)。

如果可以做到這點晚伙，我們就能實現(xiàn)遞歸了吮龄。(ΦωΦ)

接下來放慢腳步，讓我們看下 sum0咆疗，因為在 sum0 中漓帚，傳給 mkSum 的參數(shù)就是它自身。那我們不妨改下 mkSum 的參數(shù)名午磁。為了區(qū)別 mkSum尝抖，我們改成 mkSum1（其實不區(qū)別也可以）。

// 改成參數(shù)名 mkSum1 提醒我們傳進(jìn)來的參數(shù)就是 mkSum
var mkSum = (mkSum1) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+mkSum1(n-1)
    }
  }
}

var sum0 = mkSum(mkSum)

之前已經(jīng)提到迅皇，推導(dǎo)思想的關(guān)鍵就是在需要的時候昧辽，把 mkSum 轉(zhuǎn)成 mkSum(mkSum)。

那什么時候是需要的時候呢登颓？沒錯搅荞，就是遞歸函數(shù)在想要調(diào)用自身的時候！框咙。

所以咕痛，我們把 mkSum 改造成下面的樣子??：

// 請注視這個函數(shù)至少一分鐘。好好參悟喇嘱。(￣ω￣)
var mkSum = (mkSum1) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      // 姨媽大茉贡！就是這里！婉称！把 mkSum 改成 mkSum(mkSum)
      return n+mkSum1(mkSum1)(n-1)
    }
  }
}

// 已經(jīng)實現(xiàn)遞歸块仆，所以 sum0 已經(jīng)變成 sum 了
var sum = mkSum(mkSum)

這里就是推導(dǎo)過程中最關(guān)鍵最難理解的地方了，到這一步王暗，已經(jīng)實現(xiàn)遞歸的效果了悔据，sum 已經(jīng)完美可運行。

接下來的就是在對 mkSum 函數(shù)進(jìn)行等價的轉(zhuǎn)換俗壹，從而抽象出真正的Y組合子科汗，但請務(wù)必弄懂上面的部分才繼續(xù)看下面的內(nèi)容。

第二部分

抽象出真正的Y組合子

一個小方法

在下面的推導(dǎo)之前绷雏，為了讓大家更好理解下面的內(nèi)容头滔，先寫個小方法，下面的推導(dǎo)中很多地方都用的了涎显。

那就是如何把函數(shù)中的某些內(nèi)容提取出來作為參數(shù)坤检。

var d = 1, e = 2
// 原函數(shù)
var a = c => {
  var b = d + e
  return b + c
}

// 變換形式，將 b 提取出來變成參數(shù)形式期吓，和上面的原函數(shù)等價
var aCreator = b => c => b+c
var a = aCteator(d+e)

a(10)

在接下來的內(nèi)容中早歇，凡是涉及到提取某某變成參數(shù)形式的說法，都是利用這種方法。

首先箭跳，我們簡單轉(zhuǎn)換下 mkSum 函數(shù)的形式晨另，把 mkSum1(mkSum1) 提取出來變成參數(shù)形式。

var mkSum = (mkSum1) => {
  var sumR = mkSum1(mkSum1)
  
  // sumFn 不就是傳給 Y組合子 的參數(shù)么谱姓？借尿！
  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)

很簡單的提取屉来，用這個函數(shù)試下執(zhí)行 sum(3) 試試路翻？

啊咧？奶躯？剛剛明明還很正常的啊帚桩，怎么突然就爆棧了？(｀谇°Д°)

具體的原因就不解釋了，自己好好想想就能得出答案了莫瞬。

為了解決爆棧的問題儡蔓，mkSum1(mkSum1) 外面裹一層函數(shù)就可以了。

var mkSum = (mkSum1) => {
  // 外面裹一層匿名函數(shù)疼邀，解決棧溢出問題
  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提取出來變成參數(shù)形式：

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) 變成了 函數(shù)w
var sum = w(mkSum)

我們再把sumFn提取到mkSum外面變成參數(shù)形式：

// 被提取出來的 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 已經(jīng)變成形參了
}
var mkSum = mkSumCreator(sumFn)

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

再外面包一層函數(shù)喂江，作為 Y組合子的原型

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

// 將所有元素包在一個函數(shù)中，這個函數(shù)就是 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)

要怎么才能變成這種形式呢获询？這一步不是很明顯。所以可能需要仔細(xì)觀察一下拐袜。

我們只需要給 poorY 添加一個參數(shù) sumFn吉嚣，將最外部的 sumFn 作為參數(shù)傳進(jìn)來即可。

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

// 為 poorY 添加一個參數(shù) sumFn
var poorY = (sumFn) => {
   // poorY 函數(shù)內(nèi)部不需要有任何變化
  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 以參數(shù)的形式傳進(jìn) poorY蹬铺，而不是作為自由變量
var sum = poorY(sumFn)

這時候尝哆，千呼萬喚的 Y組合子 終于要出來了，看見沒有甜攀？秋泄！

因為 poorY 內(nèi)部的 mkSumCreator 是直接調(diào)用的，所以可以把它簡化一下规阀，這樣我們就得到真正的 Y組合子了恒序。

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

var y = (sumFn) => {
  // 去掉一層調(diào)用
  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組合子：

// 參數(shù)名替換
// w -> (f => f(f))
// mkSum1 -> b
// sumFn -> fn
var Y = fn => 
  (f => f(f))
  (b => fn( x => b(b)(x) ))

之前講過 mkSum 和 mkSum1 其實并不需要嚴(yán)格區(qū)別谁撼。所以歧胁，為了更（故）加（作）簡（神）化（秘），我們就把它們都替換成 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) ))

細(xì)心的朋友應(yīng)該注意到了与帆，這個 Y 組合子生成的遞歸函數(shù)了赌，只能處理一個參數(shù)，也就是 Y 組合子里面的 x 玄糟。所以我們可以修改一下勿她，讓 Y 組合子生成的遞歸函數(shù)不受參數(shù)限制。

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

結(jié)尾

推導(dǎo)到此結(jié)束阵翎，看懂了么逢并？如果沒有的話，

可以參考下另一篇文章：https://zhuanlan.zhihu.com/p/20616683 (這篇文章講得更加透徹)郭卫，

或者閱讀下 《The Little Schemer》的第九章（本文就是基于這一章寫出來的）砍聊。

最后要指出的是，在實際應(yīng)用中贰军，遞歸的實現(xiàn)并不是靠Y組合子實現(xiàn)的玻蝌，而是先保存函數(shù)的引用（比如指針），然后在需要的時候再通過指針調(diào)用自身函數(shù)词疼。這和我們的直覺是相符合俯树。

所以，理解Y組合子并沒有什么卵用贰盗，只是無聊找虐而已许饿。╮(╯▽╰)╭