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

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

repository-tree

技術棧：

ES6

Vue.js

Webpack

Vuex

lodash

GitHub API

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

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

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

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

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）是函數式編程的一個重要概念，本身非常簡單，是指某個函數的最后一步是調用另一個函數。尾調用即是一個作為返回值輸出的高階函數。

例如：

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

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

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

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

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

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

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

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

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

再看看尾遞歸優化過的階乘函數：

// 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中，只要使用尾遞歸，就不會發生棧溢出，相對節省內存。

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

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

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

// 階乘尾遞歸優化寫法
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

上面代碼通過柯里化，將尾遞歸變為只接受單個參數的 factorial，得到了想要的factorial(6) 獨參函數。

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

簡單化問題：

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

factorial(6) // => 720

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

恒等函數在 JavaScript 中的栗子：

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

// ES6
const f = x => x

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

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

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

是的，這么做還是太難看了，沒人希望寫一個階乘函數還要傳入其他參數。解決方案仍然是柯里化。尾調用優化后的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

最終達到了目的，得到了獨參函數factorial。

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

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

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箭頭函數寫出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) 解耦，當作參數傳遞。

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 中參數是 按值傳遞 的，形參必須先求值再作為實參傳入函數，f(f) 作為參數傳遞時，會無限遞歸調用自身，導致棧溢出。這時候就需要用到 lambda 演算中的 η-變換。其原理是用到了惰性求值。

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

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

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

根據η-變換，f(f) 作為函數代入，等價于 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

也許你也已經發現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 函數變為匿名函數，構建一個工廠函數 Y，將 fact 函數作為參數傳入。

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組合子實現的匿名遞歸函數，它不僅適用于階乘函數的遞歸處理，任意遞歸工廠函數經過Y函數后，都能得到真正的遞歸函數。

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

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

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

用JavaScript遞歸實現：

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

fibonacci(6) // 13

使用尾調用優化的斐波那契數列

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

fibonacci(6, 1, 2) // 13

使用lambda表達式的斐波那契數列

// 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，去想辦法實現它，過程中自然會提升自己的見識。以此篇博文激勵自己繼續學習下去。

Lambda演算

JS 函數式編程指南

《ECMAScript 6 入門》

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

ES6函數與Lambda演算