Для корректной работы текстовым редакторам необходим root-доступ

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

Это применимо к языкам, которые поддерживают лямбда-функции . Характер лямбд на основе выражений обычно означает, что они не могут ссылаться на себя по имени. И обходить это путем объявления переменной, обращения к ней, а затем присвоения ей лямбды, чтобы завершить цикл самоссылки, является хрупким. Лямбда-переменная может быть скопирована, а исходная переменная переназначена, что нарушает самоссылку.

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

Ниже приведен пример того, как используется и работает Y-Combinator, в C #.

Использование Y-комбинатора предполагает «необычный» способ построения рекурсивной функции. Сначала вы должны написать свою функцию в виде фрагмента кода, который вызывает ранее существующую функцию, а не себя:

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

Затем вы превращаете это в функцию, которая принимает функцию для вызова и возвращает функцию это делает так. Это называется функционалом, потому что он берет одну функцию и выполняет с ней операцию, которая приводит к другой функции.

// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func, Func> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

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

// One-argument Y-Combinator.
public static Func Y(Func, Func> F)
{
  return
    t =>  // A function that...
      F(  // Calls the factorial creator, passing in...
        Y(F)  // The result of this same Y-combinator function call...
              // (Here is where the recursion is introduced.)
        )
      (t); // And passes the argument into the work function.
}

Вместо того, чтобы сам факториал вызывать, происходит то, что факториал вызывает генератор факториала (возвращаемый рекурсивным вызовом Y-Combinator). И в зависимости от текущего значения t функция, возвращаемая из генератора, либо снова вызовет генератор, с t - 1, либо просто вернет 1, завершая рекурсию.

Это сложно и загадочно, но все встряхивается во время выполнения, и ключом к его работе является «отложенное выполнение» и разбиение рекурсии на две функции. Внутренний F передается в качестве аргумента , который будет вызываться на следующей итерации, только при необходимости .