摘要：組合子是演算中的一個(gè)概念，是任意函數(shù)的不動(dòng)點(diǎn)，在函數(shù)式編程中主要作用是提供一種匿名函數(shù)的遞歸方式。組合子如下本文將盡量通俗易懂的以實(shí)現(xiàn)匿名函數(shù)遞歸為導(dǎo)向，推導(dǎo)出這一式子。若將替換為，將導(dǎo)致組合子中的作為的參數(shù)被立即求值。

Y 組合子是 lambda 演算中的一個(gè)概念，是任意函數(shù)的不動(dòng)點(diǎn)，在函數(shù)式編程中主要作用是 提供一種匿名函數(shù)的遞歸方式。

Y 組合子如下：

$$ λf.(λx.f(x x))(λx.f(x x)) $$

本文將盡量通俗易懂的以 實(shí)現(xiàn)匿名函數(shù)遞歸 為導(dǎo)向，推導(dǎo)出這一式子。

這部分通過(guò) js 函數(shù)介紹 lambda 表達(dá)式，如果已經(jīng)了解 lambda 演算 可以跳過(guò)這一部分。

了解一個(gè)新領(lǐng)域的最好方法是用已有知識(shí)進(jìn)行類(lèi)比。
我們可以把每一個(gè) lambda 表達(dá)式解釋為一個(gè) js 函數(shù)：

"λ" 字符可以看作 function 聲明，"."字符前為參數(shù)列表，"."字符后為函數(shù)體。

lambda 表達(dá)式不能被命名（賦值給變量），這也是為什么lambda演算需要引入 Y組合子的原因。

lambda 表達(dá)式只允許定義一個(gè)參數(shù)。

組合子對(duì)照 js 可以理解為：函數(shù)體內(nèi)，沒(méi)有使用外部變量。

不動(dòng)點(diǎn)是函數(shù)的一個(gè)特征：對(duì)于函數(shù) $f(x)$，如果有變量 ?$a$ 使得??$f(a)=a$ 成立，則稱(chēng) $a$ 是函數(shù) $f$ 上的一個(gè)不動(dòng)點(diǎn)。

遞歸就是函數(shù)不斷調(diào)用自身

一個(gè)最基本的調(diào)用自身的函數(shù)是這樣的：

var f = () => f();
f();
//> f()
//> f()
//> ...

但這個(gè)函數(shù)僅僅是不斷的調(diào)用自身，什么也沒(méi)做。

一個(gè)正常的遞歸函數(shù)應(yīng)該有一個(gè)狀態(tài)，每次調(diào)用不斷的遞進(jìn)狀態(tài)，最終可以通過(guò)判斷狀態(tài)結(jié)束遞歸：

var f = p => judge(p) ? f(step(p)) : value;

// 再加上“計(jì)算”的步驟，這樣這個(gè)函數(shù)才有價(jià)值：

var f = p => judge(p) ? calc(f(step(p)),p) : value;

一個(gè)具體的例子，計(jì)算階乘的函數(shù)：

var factorial = n => n ? factorial(n-1)*n : 1;

調(diào)用：

factorial(4);
//=> 24

由于不能給函數(shù)命名，我們需要把函數(shù)作為參數(shù)傳入一個(gè)高階函數(shù)。這樣，在高階函數(shù)中，就可以使用 參數(shù)名 來(lái)引用函數(shù)，相當(dāng)于變相地給函數(shù)命了名。

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

var invokeWithSelf = f => f(f);

當(dāng)這個(gè)函數(shù)傳入自身作為參數(shù)時(shí)

invokeWithSelf(invokeWithSelf);
//> (f=>f(f))(f=>f(f));
//> (f=>f(f))(f=>f(f));
//> ...

我們得到了一個(gè)匿名的無(wú)限遞歸函數(shù)，仿照上一節(jié)，我們可以把這個(gè)函數(shù)改造成可以使用的遞歸函數(shù)

//首先需要有一個(gè)參數(shù)來(lái)保存遞歸狀態(tài)
var func = f => p => f(f)(p);

//加上狀態(tài)改變和判斷
var func = f => p => judge(p) ? f(f)(step(p)) : value;

//增加計(jì)算
var func = f => p => judge(p) ? calc(f(f)(step(p)),p) : value;

具體例子，計(jì)算階乘的函數(shù)：

var func = f => n => n ? f(f)(n-1)*n : 1;

調(diào)用：

func(func)(4);
//> 24

匿名調(diào)用：

(f => n => n ? f(f)(n-1)*n : 1)(f => n => n ? f(f)(n-1)*n : 1)(4);
//> 24

現(xiàn)在我們得到了一個(gè)匿名的遞歸函數(shù)，不過(guò)它只能用來(lái)計(jì)算階乘。為了將其通用，我們希望將 函數(shù)的具體計(jì)算方式與其遞歸的形式剝離開(kāi)來(lái)。

對(duì)于剛才的函數(shù)func，我們嘗試一步步將它分解成 計(jì)算邏輯 和 遞歸邏輯 兩部分

var func = (f => n => n ? f(f)(n-1)*n : 1)(f => n => n ? f(f)(n-1)*n : 1);

//調(diào)用：
func(4);
//> 24

開(kāi)始化簡(jiǎn) func：

var func = n => {
    return (f => n => n ? f(f)(n-1)*n : 1)(f => n => n ? f(f)(n-1)*n : 1);
}

提取重復(fù)形式 f => n => n ? f(f)(n-1)*n : 1：

var func = n => {
    var fa = f => n => n ? f(f)(n-1)*n : 1;
    return fa(fa);
};

//改寫(xiě)形式
var func = n => {
    var fa = f => {
        return n => n ? f(f)(n-1)*n : 1;
    };
    return fa(fa);
};

可以看出，其主要遞歸邏輯來(lái)自 f(f), 我們將這一部分解耦：

var func = n => {
    var fa = f => {
        var fb = n => f(f)(n);
        return n => n ? fb(n-1)*n : 1;
    };
    return fa(fa);
};

可以看到 返回值 不再需要 fc 接收的參數(shù) f, 將返回值表達(dá)式具名, 以便提取出 fc, 分離邏輯：

var func = n => {
    var fa = f => {
        var fb = n => f(f)(n);
        var fc = n => n ? fb(n-1)*n : 1;
        return fc;
    };
    return fa(fa);
};

fc 還在依賴(lài) fb, 將 fb 作為參數(shù)傳入 fc, 解除 fc 對(duì) fb 的依賴(lài)：

var func = n => {
    var fa = f => {
        var fb = n => f(f)(n);
        var fc = fb => n => n ? fb(n-1)*n : 1;
        return fc(fb);
    };
    return fa(fa);
};

可以發(fā)現(xiàn) fc 是計(jì)算邏輯部分，將 fc 提取出 fa：

var func = n => {
    var fa = fc => f => {
        var fb = n => f(f)(n);
        return fc(fb);
    };
    var fc = fb => n => n ? fb(n-1)*n : 1;
    return fa(fc)(fa(fc));
};

構(gòu)造一個(gè)函數(shù) fd, 化簡(jiǎn)返回值的形式：

var func = n => {
    var fa = fc => f => {
        var fb = n => f(f)(n);
        return fc(fb);
    };
    var fc = fb => n => n ? fb(n-1)*n : 1;
    var fd = fa => fc => {
        return fa(fc)(fa(fc));
    }
    return fd(fa)(fc);
};

將 fa 帶入 fd, 得到遞歸邏輯部分：

var func = n => {
    var fc = fb => n => n ? fb(n-1)*n : 1;
    var fd = fc => {
        var fa = fc => f => {
            var fb = n => f(f)(n);
            return fc(fb);
        };
        return fa(fc)(fa(fc));
    }
    return fd(fc);
};

//化簡(jiǎn)fd
var func = n => {
    var fc = fb => n => n ? fb(n-1)*n : 1;
    var fd = fc => {
        var fa = f => {
            var fb = n => f(f)(n);
            return fc(fb);
        };
        return fa(fa);
    }
    return fd(fc);
};

//化簡(jiǎn)fd
var func = n => {
    var fc = fb => n => n ? fb(n-1)*n : 1;
    var fd = fc => (f => fc(n => f(f)(n)))(f => fc(n => f(f)(n)));
    return fd(fc);
};

可以看到，兩部分邏輯已經(jīng)分離，可以得到 javascript 中的 Y 組合子：

var fn = fc;
var Y = fd;

將參數(shù)名替換一下，得到 Y 組合子與計(jì)算邏輯 fn：

var fn = f => n => n ? f(n-1)*n : 1;
var Y = y => (x => y(n => x(x)(n)))(x => y(n => x(x)(n)));

調(diào)用測(cè)試：

Y(fn)(4);
//> 24

你可能注意到，剛才推導(dǎo)出的 Y 組合子形式與 其 λ 表達(dá)式的等價(jià)形式不一致

/*λ 表達(dá)式的等價(jià)形式*/
Y = y => (x => y(x(x)))(x => y(x(x)));

/*推導(dǎo)出的形式*/
Y = y => (x => y(n => x(x)(n)))(x => y(n => x(x)(n)));

對(duì)比不難發(fā)現(xiàn) n => x(x)(n) 應(yīng)化為 x(x)，并且嘗試直接使用等價(jià)形式時(shí)會(huì)發(fā)生爆棧

我們知道，上面的兩種形式幾乎是等價(jià)的，例如：

var print = str => console.log(str);

// 在一個(gè)參數(shù)的情況下，等價(jià)于：
var print = console.log;

但當(dāng)它們作為函數(shù)參數(shù)時(shí)，其實(shí)有著略微不同：

//接收一個(gè)函數(shù)，但不使用它
var y = xn => {
    console.log("run y");
    return false ? xn(1) : 0;
};

//接收任意一個(gè)參數(shù)，返回一個(gè)函數(shù)
var x = n => {
    console.log("run x");
    return n1 => n1;
};

//調(diào)用，將參數(shù)直接傳入
y(x(1));
//> "run x"
//> "run y"

//調(diào)用，將參數(shù)包裹在匿名函數(shù)中傳入
y((n1)=>x(1)(n1));
//> "run y"

可以看到，在 y(x(1)) 的過(guò)程中，根本沒(méi)有用到參數(shù) x(1) 的值，但程序不在乎這一點(diǎn)，首先求出了 x(1) 的值；
第二個(gè)表達(dá)式中參數(shù) x(1) 被“包裹”在一個(gè)匿名函數(shù)中，并沒(méi)有運(yùn)行。

對(duì)于函數(shù)參數(shù)的求值策略，不同的語(yǔ)言不相同：

在函數(shù)調(diào)用時(shí)，立即求值，稱(chēng)作“嚴(yán)格求值”(Eager evaluation), js / c++ / c# 均使用嚴(yán)格求值

在函數(shù)運(yùn)行時(shí)動(dòng)態(tài)地求值，稱(chēng)作“惰性求值”(Lazy evaluation), 以 Haskell 為代表的函數(shù)式編程語(yǔ)言默認(rèn)使用

javascript 中使用的是嚴(yán)格求值，而 lambda 表達(dá)式中使用的是惰性求值。

若將 n => x(x)(n) 替換為 x(x)，將導(dǎo)致 Y 組合子中的 x(x) 作為 y 的參數(shù)被立即求值。
由于右邊部分中 x(x) 是一個(gè)無(wú)限遞歸的的式子，對(duì)它求值會(huì)使它不斷地調(diào)用自身，最終導(dǎo)致堆棧溢出。

只進(jìn)行左邊部分的替換并不會(huì)導(dǎo)致無(wú)限調(diào)用：

Y = y => (x => y(n => x(x)(n)))(x => y(n => x(x)(n)));

//可化為
Y = y => (x => y(x(x))(x => y(n => x(x)(n)));

在計(jì)算這個(gè)式子時(shí)，會(huì)首先計(jì)算 參數(shù) y 的值
完成后在計(jì)算左邊的 x(x) 之前、會(huì)計(jì)算左邊部分中 x 參數(shù)的值
而左邊式子中 x 的值取決于右邊部分的結(jié)果，右邊返回值使左邊的 x(x) 不再是無(wú)限遞歸。

函數(shù)式編程的方法感覺(jué)著實(shí)有點(diǎn)燒腦，還沒(méi)怎么實(shí)操過(guò)。

不過(guò) js 真是厲害，什么編程方法都能用...

一直希望能夠找到一種符合人們思考方式（至少符合我自己）的編程方法，讓程序變得自然、易讀、易寫(xiě)。不斷嘗試中。