摘要：高階函數(shù)函數(shù)式編程中，接受函數(shù)作為參數(shù)，或者返回一個函數(shù)作為結果的函數(shù)通常就被稱為高階函數(shù)。均屬于高階函數(shù)，高階函數(shù)并不神秘，我們日常編程也會用到。參考演算函數(shù)式編程指南入門康托爾哥德爾圖靈永恒的金色對角線原文函數(shù)與演算

造了一個輪子，根據(jù)GitHub項目地址，生成項目目錄樹，直觀的展現(xiàn)項目結構，以便于介紹項目。歡迎Star。

repository-tree

技術棧：

ES6

Vue.js

Webpack

Vuex

lodash

GitHub API

應用涉及到了展現(xiàn)目錄樹，實現(xiàn)方法不可或缺的一定是遞歸遍歷。進而開啟了我對lambda演算的探索發(fā)現(xiàn)之旅。

本次乘坐的是 斐波那契 號郵輪，下面會涉及到一些 JavaScript 函數(shù)式編程中的一些基本概念。如果出現(xiàn)眩暈、惡心（kan bu dong)等不良反應，想下船的旅客純屬正常。常旅客請安心乘坐。

函數(shù)式編程中，接受函數(shù)作為參數(shù)，或者返回一個函數(shù)作為結果的函數(shù)通常就被稱為高階函數(shù)。

map、filter、reduce 均屬于高階函數(shù)，高階函數(shù)并不神秘，我們日常編程也會用到。

ES6 中的 map 例子

const arr = [1, 2, 3, 4, 5, 6]

const powArr = arr.map(v => v * v)

console.log(powArr) // [ 1, 4, 9, 16, 25, 36 ]

尾調用（Tail Call）是函數(shù)式編程的一個重要概念，本身非常簡單，是指某個函數(shù)的最后一步是調用另一個函數(shù)。尾調用即是一個作為返回值輸出的高階函數(shù)。

例如：

function f(x) {
  return g(x);
}

函數(shù)f()在尾部調用了函數(shù)g()

尾調用的重要性在于它可以不在調用棧上面添加一個新的堆棧幀，而是更新它，如同迭代一般。

遞歸我們都不陌生，函數(shù)調用自身，稱為遞歸。如果尾調用自身，就稱為尾遞歸。通常被用于解釋遞歸的程序是計算階乘：

// ES5
function factorial(n) {
  return n === 1 ? 1 : n * factorial(n - 1);
}

factorial(6) // => 720

// ES6
const factorial = n => n === 1 ? 1 : n * factorial(n - 1)

factorial(6) // => 720

遞歸非常耗費內存，因為需要同時保存成千上百個調用記錄，很容易發(fā)生“棧溢出”錯誤（stack overflow）。但對于尾遞歸來說，由于只存在一個調用記錄，所以永遠不會發(fā)生“棧溢出”錯誤。對函數(shù)調用在尾位置的遞歸或互相遞歸的函數(shù)，由于函數(shù)自身調用次數(shù)很多，遞歸層級很深，尾遞歸優(yōu)化則使原本 O(n) 的調用?？臻g只需要 O(1)

尾遞歸因而具有兩個特征：

調用自身函數(shù)(Self-called)；

計算僅占用常量?？臻g(Stack Space)。

再看看尾遞歸優(yōu)化過的階乘函數(shù)：

// ES5
function factorial(n, total) {
  return n === 1 ? total : factorial(n - 1, n * total);
}

factorial(6, 1) // => 720

// ES6
const factorial = (n, total) => n === 1 ? total : factorial(n - 1, n * total)

factorial(6, 1) // => 720

在ES6中，只要使用尾遞歸，就不會發(fā)生棧溢出，相對節(jié)省內存。

上面的階乘函數(shù)factorial，尾遞歸優(yōu)化后的階乘函數(shù)使用到了total這個中間變量，為了做到遞歸實現(xiàn)，確保最后一步只調用自身，把這個中間變量改寫成函數(shù)的參數(shù)，這樣做是有缺點的，為什么計算6的階乘，還要傳入兩個變量6和1呢？解決方案就是柯里化。

柯里化（Currying），是把接受多個參數(shù)的函數(shù)變換成接受一個單一參數(shù)的函數(shù)，并且返回接受余下的參數(shù)而且返回結果的新函數(shù)的技術。

維基百科上的解釋稍微有點繞了，簡單來說，一個 currying 的函數(shù)只傳遞給函數(shù)一部分參數(shù)來調用它，讓它返回一個閉包函數(shù)去處理剩下的參數(shù)。

// 階乘尾遞歸優(yōu)化寫法
function currying(fn, n) {
  return function (m) {
    return fn.call(this, m, n);
  };
}

function tailFactorial(n, total) {
  if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

const factorial = currying(tailFactorial, 1);

factorial(6) // => 720

下面看下 ES6 中的 柯里化：

const fact = (n, total) => n === 1 ? total : fact(n - 1, n * total)

const currying = f => n => m => f(m, n)

const factorial = currying(fact)(1)

factorial(6) // => 720

上面代碼通過柯里化，將尾遞歸變?yōu)橹唤邮軉蝹€參數(shù)的 factorial，得到了想要的factorial(6) 獨參函數(shù)。

思考?，有木有更簡單的方法實現(xiàn)上面獨參尾遞歸栗子。當然有，利用ES6的函數(shù)新特性，函數(shù)默認值。

簡單化問題：

const fact = (n, total = 1) => n === 1 ? total : fact(n - 1, n * total)

factorial(6) // => 720

在 JavaScript 中，Lambda表達式可以表示匿名函數(shù)。

恒等函數(shù)在 JavaScript 中的栗子：

// ES5
var f = function (x) {
  return x;
};

// ES6
const f = x => x

用 lambda表達式 來寫是這樣子的：λx.x

現(xiàn)在試著用lambda表達式寫出遞歸（匿名函數(shù)遞歸），使用具有遞歸效果的lambda表達式，將lambda表達式作為參數(shù)之一傳入其自身。

// ES5
function factorial(f, n) {
  return n === 1 ? 1 : n * f(f, n - 1)
}

factorial(factorial, 6) // => 720

// ES6
const factorial = (f, n) => n === 1 ? 1 : n * f(f, n - 1)

factorial(factorial, 6) // => 720

是的，這么做還是太難看了，沒人希望寫一個階乘函數(shù)還要傳入其他參數(shù)。解決方案仍然是柯里化。尾調用優(yōu)化后的Lambda表達式遞歸：

const fact = (f, n ,total = 1) => n === 1 ? total : f(f, n - 1, n * total)

const currying = f => n => m => f(f, m ,n)

const factorial = currying(fact)()

factorial(6) // => 720

最終達到了目的，得到了獨參函數(shù)factorial。

在Lambda演算中的所有函數(shù)都是匿名的，它們沒有名稱，它們只接受一個輸入變量，即獨參函數(shù)。

構建一個高階函數(shù)，它接受一個函數(shù)作為參數(shù)，并讓這個函數(shù)將自身作為參數(shù)調用其自身:

const invokeWithSelf = f => f(f)

用Lambda演算寫出遞歸栗子：

const fact = f => (total = 1) => n => n === 1 ? total : f(f)(n * total)(n - 1)

const factorial = fact(fact)()

factorial(6) // => 720

什么是Y組合子？

Y = λf.(λx.f(xx))(λx.f(xx))

η-變換后的寫法：

Y = λf.(λx.f(λv.x(x)(v)))(λx.f(λv.x(x)(v)))

用ES6箭頭函數(shù)寫出lambda演算Y組合子

const Y = f =>
    (x => f(v => x(x)(v)))
    (x => f(v => x(x)(v)))

const fact = f => (total = 1) => n => n === 1 ? total : f(f)(n * total)(n - 1)

const factorial = fact(fact)()

factorial(6) // => 720

上面代碼有一種模式被重復了三次， f(f) 兩次， fact(fact) 一次。為了讓代碼更加 DRY ，嘗試把 f(f) 解耦，當作參數(shù)傳遞。

const fact = f => 
  (g => (total = 1) => n => n === 1 ? total : g(n * total)(n - 1))(f(f))
  
const factorial = fact(fact)()

factorial(6) // => Maximum call stack size exceeded

當然上面代碼運行結果會棧溢出，因為 JavaScript 中參數(shù)是 按值傳遞 的，形參必須先求值再作為實參傳入函數(shù)，f(f) 作為參數(shù)傳遞時，會無限遞歸調用自身，導致棧溢出。這時候就需要用到 lambda 演算中的 η-變換。其原理是用到了惰性求值。

什么是η-變換？如果兩個函數(shù)對于任意的輸入都能產生相同的行為（即返回相同的結果），那么可以認為這兩個函數(shù)是相等的。

lambda演算中有效的η-變換：f = λx.(fx)

JavaScript中的η-變換：f = x => f(x)

根據(jù)η-變換，f(f) 作為函數(shù)代入，等價于 x => f(f)(x)

const fact = x => (f => (total = 1) => n => n === 1 ? total : f(n * total)(n - 1))(v => x(x)(v))

const factorial = fact(fact)()

factorial(6) // => 720

也許你也已經(jīng)發(fā)現(xiàn)f => (total = 1) => n => n === 1 ? total : f(n * total)(n - 1)這就是柯里化后的遞歸方法。抽離出 fact 方法。

const fact = f => (total = 1) => n => n === 1 ? total : f(n * total)(n - 1)

const factorial = (x => fact((v => x(x)(v))))(x => fact((v => x(x)(v))))()

factorial(6) // => 720

將具名 fact 函數(shù)變?yōu)槟涿瘮?shù)，構建一個工廠函數(shù) Y，將 fact 函數(shù)作為參數(shù)傳入。

const fact = f => (total = 1) => n => n === 1 ? total : f(n * total)(n - 1)

const Y = f => (x => f(v => x(x)(v)))
               (x => f(v => x(x)(v))) // 瞧，這不就是黑魔法Y組合子嘛

const factorial = Y(fact)()

factorial(6) // => 720

用Y組合子實現(xiàn)的匿名遞歸函數(shù)，它不僅適用于階乘函數(shù)的遞歸處理，任意遞歸工廠函數(shù)經(jīng)過Y函數(shù)后，都能得到真正的遞歸函數(shù)。

在數(shù)學上，斐波那契數(shù)列是以遞歸的方法定義的：

用文字來說：就是斐波那契數(shù)列由0和1開始，之后的斐波那契系數(shù)就由之前的兩數(shù)加和。

0,1,1,2,3,5,8,13,21,34,55,89,144,233......

用JavaScript遞歸實現(xiàn)：

// 非尾遞歸
function fibonacci (n) {
  if ( n <= 1 ) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci(6) // 13

使用尾調用優(yōu)化的斐波那契數(shù)列

// 尾遞歸寫法
function fibonacci (n , before , after) {
  if( n <= 1 ) return before;
  return fibonacci (n - 1, after, before + after);
}

fibonacci(6, 1, 2) // 13

使用lambda表達式的斐波那契數(shù)列

// ES6 lambda calculus
const Y = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)))

const fibonacci = Y(
  f => (n) => n <= 1 ? 1 : f(n - 1) + f(n - 2)
)

fibonacci(6) // 13

在生活中，德羅斯特效應（Droste effect）是遞歸的一種視覺形式，指一張圖片部分與整張圖片相同，一張有德羅斯特效應的圖片，在其中會有一小部分是和整張圖片類似。 而這小部分的圖片中，又會有一小部分是和整張圖片類似，以此類推，……。德羅斯特效應的名稱是由于荷蘭著名廠牌德羅斯特（Droste） 可可粉的包裝盒，包裝盒上的圖案是一位護士拿著一個有杯子及紙盒的托盤，而杯子及紙盒上的圖案和整張圖片相同

我在做repository-tree項目的過程中學習到了很多之前沒有接觸過的東西，這也是我的初衷，想到各種各樣的idea，去想辦法實現(xiàn)它，過程中自然會提升自己的見識。以此篇博文激勵自己繼續(xù)學習下去。

Lambda演算

JS 函數(shù)式編程指南

《ECMAScript 6 入門》

康托爾、哥德爾、圖靈——永恒的金色對角線

ES6函數(shù)與Lambda演算