Получение Y-комбинатора в 7 простых шагов

Y-комбинатор это метод реализации механизма рекурсии в языке программирования который не поддерживает его изначально (на самом деле, он используется больше для осуществления программирования мозгов). Однако требуется, чтобы язык поддерживал анонимные функции.

Я выбрал JavaScript для получения Y-комбинатора, начиная с определения рекурсивной функции факториала, используя пошаговые преобразования над исходной функцией.

Шаг 1

На начальном этапе используем встроенный механизм рекурсии JavaScript.

var fact = function (n) {
    if (n < 2) return 1;
    return n * fact(n - 1);
};

Шаг 2

Чтобы было простейшей вещью для получения базовой рекурсии? Мы могли бы определить функцию которая получает себя в качестве аргументы и вызывает этот аргумент с тем же аргументом. Конечно, это бесконечный цикл, и это вызовет переполнение стека.

(function (f) {
    f(f);
})(function (f) {
    f(f);
});

Давайте используем образец выше для нашей функции факториала. Существует однако небольшая разница. Функция факториала получает аргумент который пока неизвестен, так что мы хотим вернуть функцию которая принимает этот аргумент. Эта функция может быть использована для вычисления факториалов. Также, это то, что делает нашу реализацию не результатом бесконечного цикла.

var fact = (function (f) {
    return function (n) {
        // termination condition
        if (n < 2) return 1;

        // because f returns a function, we have a double function call.
        return n * f(f)(n - 1);
    };
})(function (f) {
    return function (n) {
        // termination condition
        if (n < 2) return 1;

        // because f returns a function, we have a double function call.
        return n * f(f)(n - 1);
    };
});

Шаг 3

На данный момент у нас есть некоторое уродливое дублирование. Давайте спрячем его в некоторой вспомогательной функции recur

var recur = function (f) {
    return f(f);
};

var fact = recur(function (f) {
    return function (n) {
        if (n < 2) return 1;

        // because f returns a function, we have a double function call.
        return n * f(f)(n - 1);
    };
});

Шаг 4

Проблемой версии выше является двойной вызов функции. Мы хотим его ликвидировать, так чтобы реализовать факториал аналогично с рекурсивной версией. Как мы можем это сделать?

Мы можем использовать вспомогательную функцию которая принимает числовой аргумент и выполняет двойной вызов. Фокус в том чтобы оставить эту вспомогательную функцию в некоторой среде где f видна, так чтобы g могла вызвать f.

var recur = function (f) {
    return f(f);
};

var fact = recur(function (f) {
    var g = function (n) {
        return f(f)(n);
    };

    return function (n) {
        if (n < 2) return 1;

        // no more double call, g is a function which takes a numeric arg
        return n * g(n - 1);
    };
});

Шаг 5

Работа выше хороша но определение содержит так много беспорядочного кода. Мы может скрыть его подальше внутри еще одной вспомогательной функции, оставляя почти только определение факториала.

var recur = function (f) {
    return f(f);
};

var wrap = function (h) {
    return recur(function (f) {
        var g = function (n) {
            return f(f)(n);
        };

        return h(g);
    });
};

var fact = wrap(function (g) {
    return function (n) {
        if (n < 2) return 1;
        return n * g(n - 1);
    };
});

Шаг 6

Давайте встроим определение g внутри wrap так как мы вызываем это только однажды.

var recur = function (f) {
    return f(f);
};

var wrap = function (h) {
    return recur(function (f) {
        return h(function (n) {
            return f(f)(n);
        });
    });
};

var fact = wrap(function (g) {
    return function (n) {
        if (n < 2) return 1;
        return n * g(n - 1);
    };
});

Шаг 7

Теперь если мы также встроим определение функции recur внутри wrap то мы закончим вместе с известным Y-комбинатором.

var Y = function (h) {
    return (function (f) {
        return f(f);
    })(function (f) {
        return h(function (n) {
            return f(f)(n);
        });
    });
};

var fact = Y(function (g) {
    return function (n) {
        if (n < 2) return 1;
        return n * g(n - 1);
    };
});

Конец

Я надеюсь, что вам понравилось.