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

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

Y 組合子如下：

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

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

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

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

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

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

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

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

不動點是函數(shù)的一個特征：對于函數(shù) $f(x)$，如果有變量 ?$a$ 使得??$f(a)=a$ 成立，則稱 $a$ 是函數(shù) $f$ 上的一個不動點。

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

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

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

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

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

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

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

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

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

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

調(diào)用：

factorial(4);
//=> 24

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

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

var invokeWithSelf = f => f(f);

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

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

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

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

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

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

具體例子，計算階乘的函數(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)在我們得到了一個匿名的遞歸函數(shù)，不過它只能用來計算階乘。為了將其通用，我們希望將 函數(shù)的具體計算方式與其遞歸的形式剝離開來。

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

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

開始化簡 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);
};

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

可以看出，其主要遞歸邏輯來自 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, 將返回值表達式具名, 以便提取出 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 還在依賴 fb, 將 fb 作為參數(shù)傳入 fc, 解除 fc 對 fb 的依賴：

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 是計算邏輯部分，將 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)造一個函數(shù) fd, 化簡返回值的形式：

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

//化簡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);
};

//化簡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 組合子與計算邏輯 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)用測試：

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

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

/*λ 表達式的等價形式*/
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)));

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

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

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

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

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

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

//接收任意一個參數(shù)，返回一個函數(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)) 的過程中，根本沒有用到參數(shù) x(1) 的值，但程序不在乎這一點，首先求出了 x(1) 的值；
第二個表達式中參數(shù) x(1) 被“包裹”在一個匿名函數(shù)中，并沒有運行。

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

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

在函數(shù)運行時動態(tài)地求值，稱作“惰性求值”(Lazy evaluation), 以 Haskell 為代表的函數(shù)式編程語言默認使用

javascript 中使用的是嚴格求值，而 lambda 表達式中使用的是惰性求值。

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

只進行左邊部分的替換并不會導(dǎo)致無限調(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)));

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

函數(shù)式編程的方法感覺著實有點燒腦，還沒怎么實操過。

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

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