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

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

Y 組合子如下：

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

本文將盡量通俗易懂的以 實現匿名函數遞歸 為導向，推導出這一式子。

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

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

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

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

lambda 表達式只允許定義一個參數。

組合子對照 js 可以理解為：函數體內，沒有使用外部變量。

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

遞歸就是函數不斷調用自身

一個最基本的調用自身的函數是這樣的：

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

但這個函數僅僅是不斷的調用自身，什么也沒做。

一個正常的遞歸函數應該有一個狀態，每次調用不斷的遞進狀態，最終可以通過判斷狀態結束遞歸：

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

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

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

一個具體的例子，計算階乘的函數：

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

調用：

factorial(4);
//=> 24

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

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

var invokeWithSelf = f => f(f);

當這個函數傳入自身作為參數時

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

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

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

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

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

具體例子，計算階乘的函數：

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

調用：

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

匿名調用：

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

現在我們得到了一個匿名的遞歸函數，不過它只能用來計算階乘。為了將其通用，我們希望將 函數的具體計算方式與其遞歸的形式剝離開來。

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

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

//調用：
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 => 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 接收的參數 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 作為參數傳入 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);
};

可以發現 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));
};

構造一個函數 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);
};

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

var fn = fc;
var Y = fd;

將參數名替換一下，得到 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)));

調用測試：

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

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

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

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

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

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

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

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

但當它們作為函數參數時，其實有著略微不同：

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

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

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

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

可以看到，在 y(x(1)) 的過程中，根本沒有用到參數 x(1) 的值，但程序不在乎這一點，首先求出了 x(1) 的值；
第二個表達式中參數 x(1) 被“包裹”在一個匿名函數中，并沒有運行。

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

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

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

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

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

只進行左邊部分的替換并不會導致無限調用：

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

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

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

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

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