yc_example.js

test10();

// 一般階乘
function test1() {
    console.log(fact(5));
    function fact(n) {
        return n < 2 ? 1 : n * fact(n-1);
    }
}

// 做一次currying
function test2() {
    console.log(fact()(5));
    function fact() {
        return function(n) {
            return n < 2 ? 1 : n * fact()(n-1);
        };
    }
}

// 外層帶遞迴函數當作參數，在呼叫時傳入自己
function test3() {
    console.log(fact(fact)(5));
    function fact(fact) {
        return function(n) {
            return n < 2 ? 1 : n * fact(fact)(n-1);
        };
    }
}

// 內部就可以不依賴函數名稱，只要在呼叫時把自己傳入
function test4() {
    console.log(fact(fact)(5));
    function fact(x) {
        return function(n) {
            return n < 2 ? 1 : n * x(x)(n-1);
        };
    }
}

// 把呼叫時傳入自己的動作移到外部函數處理
// 這樣就可以用一個函數來產生遞迴的匿名函數
function test5() {
    console.log(Y(function(x) {
        return function(n) {
            return n < 2 ? 1 : n * x(x)(n-1);
        };
    })(5));
    function Y(f) {
        return f(f);
    }
}

// 把Y改寫成 Y 組合子的形式，去掉(x)
// 對傳給 Y 的函數來說，就是讓傳入的x是原本的x(x)
// 這步跳有點多，需要額外推導
function test6() {
    let fi = Y(fact);
    console.log(fi(5));
    // 要執行的函數，結構跟原本的差距不會太大，而且可以用匿名函數的方式傳給Y
    function fact(x) {
        return function(n) {
            return n < 2 ? 1 : n * x(n-1);
        };
    }
    function Y(f) {
        return function(x) {
            // 建立遞迴
            return x(x);
        }(function(x) {
            // 遞迴的是一個包裝取值函數
            return f(function(n) {
                return x(x)(n);
            });
        });
    }
}

// 嘗試用mutual recurrsion
function test7() {
    let fi = Ys(fact1, fact2);
    console.log(fi(5));
    // 兩個函數互遞迴，假設遞迴的函數用參數傳入
    function fact1(x) {
        return function(n) {
            return n < 2 ? 1 : n * x(n-1);
        };
    }
    function fact2(x) {
        return function(n) {
            return n < 2 ? 1 : n * x(n-1);
        };
    }
    // 懶得currying，能用先
    function Ys(f, g) {
        return function(x, y) {
            return x(y, x);
        }(function(x, y) {
            return f(function(n) {
                return x(y, x)(n);
            });
        }, function(x, y) {
            return g(function(n) {
                return x(y, x)(n);
            });
        });
    }
}

// 用真正的互遞迴例子驗證
function test8() {
    let fi = Ys(function(even) {
        return function(n) {
            if(n < 2) return 'odd';
            else return even(n-1);
        };
    }, function(odd) {
        return function(n) {
            if(n < 2) return 'even';
            else return odd(n-1);
        };
    });
    console.log(6, fi(6));
    console.log(7, fi(7));
    function Ys(f, g) {
        return function(x, y) {
            return x(y, x);
        }(function(x, y) {
            return f(function(n) {
                return x(y, x)(n);
            });
        }, function(x, y) {
            return g(function(n) {
                return x(y, x)(n);
            });
        });
    }
}

function test9() {
    let fi = Ys(function(even) {
        return function(n) {
            if(n < 2) return 'odd';
            else return even(n-1);
        };
    })(function(odd) {
        return function(n) {
            if(n < 2) return 'even';
            else return odd(n-1);
        };
    });
    console.log(6, fi(6));
    console.log(7, fi(7));
    function Ys(f) {
        return function(g) {
            return function(x) {
                return function(y) {
                    return x(y)(x);
                };
            }(function(x) {
                return function(y) {
                    return f(function(n) {
                        return x(y)(x)(n);
                    });
                };
            })(function(x) {
                return function(y) {
                    return g(function(n) {
                        return x(y)(x)(n);
                    });
                };
            });
        }
    }
}

function test10() {
    let Ys = f=>g=>(x=>y=>x(y)(x))(x=>y=>f(n=>x(y)(x)(n)))(x=>y=>g(n=>x(y)(x)(n)));
    let fi = Ys(function(even) {
        return function(n) {
            if(n < 2) return 'odd';
            else return even(n-1);
        };
    })(function(odd) {
        return function(n) {
            if(n < 2) return 'even';
            else return odd(n-1);
        };
    });
    console.log(6, fi(6));
    console.log(7, fi(7));
}