>>188966
Торговцы кодом недоумевают.
Y-комбинатор - это иконичная реализация комбинатора неподвижной точки для лямбда-исчисления.
(здесь и далее все скобочки явные, чтобы не смущать более краткими нотациями)
Главное свойство комбинатора неподвижной точки - это:
Y(F) = F(Y(F))
В лямбда-исчислении например это будет
Y = λf.(λx.f(x(x))) (λx.f(x(x)))
В синтаксисах более распространённых языков это будет что-то типа
Y = f => (x => f(x(x)))(x => f(x(x)))
Это позволяет получить рекурсию не ссылаясь ни на какие глобальные имена, благодоря комбинатору функция получает сама себя (в обёртке из комбинатора) как свой аргумент.
Однако если язык всегда строго вычисляет аргументы функций, это приведёт либо к переполнению стека, либо к бесконечному циклу.
Существует так же строгая версия, которая явно индицирует аргумент F и позволяет избежать его вычисления когда не нужно, называется Z-комбинатором:
Z(F(v)) = F(Z(F))(v)
В лямбда-исчислении это выражется как
Z = λf.(λx.f(λv.(x(x))(v))) (λx.f(λv.(x(x))(v)))
И в общеиспользуемых языках:
Z = f => (x => f(v => (x(x))(v)))(x => f(v => (x(x))(v)))
В языках со строгой типизацией и без поддержки бесконечных типов, может так же потребоваться определить вспомогательный тип, который инкапсулирует вызов функции.
В плане API однако они идентичны -- и Y и Z комбинаторы оба реализуют интерфейс комбинатора неподвижной точки, который принимает функцию, которая принимает саму себя (обёрнутую в комбинатор) и свои аргументы и возвращает результат каких-то операций с опциональным применениям себя в обёртке из комбинатора на следующую итерацию аргументов.
Например, реализация факториала (дабы не вдаваться ещё и в church-кодировки чисел и булевых выражений -- их нативная поддержка берётся как данность):
fact = f => (n => n <= 0 ? 1 : n * f(n - 1))
// Y(fact)(5) == 120 // если язык ленивый, иначе упадёт или зависнет
Z(fact)(5) == 120
Здесь fact принимает себя в обёртке из комбинатора (f) и возвращает функцию, которая принимает один аргумент n, далее если n вышел за пределы краевого условия (для факториала n == 0 для целых положительных чисел), вовзвращает просто 1. В противном случае применяет себя в обёртке на (n - 1), для исходного аргумента из 5 это раскрывается в
(5 * (4 * (3 * (2 * (1 * (1))))))
^ здесь у нас получилось f(1 - 1) и дальше рекурсия не пошла, потому что n <= 0, вернулся просто 1.
Имя fact только показать что Y и Z в ленивом языке поведут себя одинаково, это имя не нужно, как впрочем и Y и Z тоже, всё можно записать целиком как
(f => (x => f(v => (x(x))(v)))(x => f(v => (x(x))(v))))(f => (n => n <= 0 ? 1 : n * f(n - 1)))(5) == 120
С вас 127 септимов.