摘要：高階函數(shù)函數(shù)式編程中，接受函數(shù)作為參數(shù)，或者返回一個(gè)函數(shù)作為結(jié)果的函數(shù)通常就被稱為高階函數(shù)。均屬于高階函數(shù)，高階函數(shù)并不神秘，我們?nèi)粘＞幊桃矔?huì)用到。參考演算函數(shù)式編程指南入門康托爾哥德爾圖靈永恒的金色對(duì)角線原文函數(shù)與演算

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

repository-tree

技術(shù)棧：

ES6

Vue.js

Webpack

Vuex

lodash

GitHub API

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

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

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

map、filter、reduce 均屬于高階函數(shù)，高階函數(shù)并不神秘，我們?nèi)粘＞幊桃矔?huì)用到。

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 ]

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

例如：

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

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

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

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

// 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èi)內(nèi)存，因?yàn)樾枰瑫r(shí)保存成千上百個(gè)調(diào)用記錄，很容易發(fā)生“棧溢出”錯(cuò)誤（stack overflow）。但對(duì)于尾遞歸來說，由于只存在一個(gè)調(diào)用記錄，所以永遠(yuǎn)不會(huì)發(fā)生“棧溢出”錯(cuò)誤。對(duì)函數(shù)調(diào)用在尾位置的遞歸或互相遞歸的函數(shù)，由于函數(shù)自身調(diào)用次數(shù)很多，遞歸層級(jí)很深，尾遞歸優(yōu)化則使原本 O(n) 的調(diào)用棧空間只需要 O(1)

尾遞歸因而具有兩個(gè)特征：

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

計(jì)算僅占用常量棧空間(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中，只要使用尾遞歸，就不會(huì)發(fā)生棧溢出，相對(duì)節(jié)省內(nèi)存。

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

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

維基百科上的解釋稍微有點(diǎn)繞了，簡單來說，一個(gè) currying 的函數(shù)只傳遞給函數(shù)一部分參數(shù)來調(diào)用它，讓它返回一個(gè)閉包函數(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)橹唤邮軉蝹€(gè)參數(shù)的 factorial，得到了想要的factorial(6) 獨(dú)參函數(shù)。

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

簡單化問題：

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

factorial(6) // => 720

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

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

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

// ES6
const f = x => x

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

現(xiàn)在試著用lambda表達(dá)式寫出遞歸（匿名函數(shù)遞歸），使用具有遞歸效果的lambda表達(dá)式，將lambda表達(dá)式作為參數(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

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

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

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

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

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

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(f) 兩次， fact(fact) 一次。為了讓代碼更加 DRY ，嘗試把 f(f) 解耦，當(dāng)作參數(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

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

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

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

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

根據(jù)η-變換，f(f) 作為函數(shù)代入，等價(jià)于 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ù)，構(gòu)建一個(gè)工廠函數(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組合子實(shí)現(xiàn)的匿名遞歸函數(shù)，它不僅適用于階乘函數(shù)的遞歸處理，任意遞歸工廠函數(shù)經(jīng)過Y函數(shù)后，都能得到真正的遞歸函數(shù)。

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

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

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

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

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

fibonacci(6) // 13

使用尾調(diào)用優(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表達(dá)式的斐波那契數(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

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

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

Lambda演算

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

《ECMAScript 6 入門》

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

ES6函數(shù)與Lambda演算