Что такое Y-комбинатор?

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

  • что такое Y-комбинатор?
  • как работают комбинаторы?
  • для чего они хороши?
  • полезны ли они в процедурных языках?
18 356
theory functional-programming computer-science combinators definition

18 ответов:

Если вы готовы к длительному чтению,Майк Ванье имеет большой объяснение. Короче говоря, это позволяет реализовать рекурсию на языке, который не обязательно поддерживает ее изначально.

186

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

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

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

Ниже приведен пример использования и работы y-комбинатора в 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<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

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

// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> 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, завершая рекурсию.

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

274

Я снял это с http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html это объяснение я написал несколько лет назад.

Я буду использовать JavaScript в этом примере, но многие другие языки также будут работать.

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

ну Шаг 1 должен сказать, что мы могли бы сделать это легко, если мы немного обманули. Используя функции 2 переменных и назначение мы можем, по крайней мере, избежать необходимости использовать назначение для настройки рекурсии.

// Here's the function that we want to recurse.
X = function (recurse, n) {
  if (0 == n)
    return 1;
  else
    return n * recurse(recurse, n - 1);
};

// This will get X to recurse.
Y = function (builder, n) {
  return builder(builder, n);
};

// Here it is in action.
Y(
  X,
  5
);

теперь давайте посмотрим, если мы можем обмануть меньше. Ну, во-первых, мы используем задание, но нам это не нужно. Мы можем просто написать X и Год линейный.

// No assignment this time.
function (builder, n) {
  return builder(builder, n);
}(
  function (recurse, n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse, n - 1);
  },
  5
);

но мы используем функции 2 переменных, чтобы получить функцию 1 переменная. Мы можем это исправить? Ну умный парень по имени Хаскелл Карри имеет аккуратный трюк, если у вас есть хороший более высокий порядок функции тогда вам нужны только функции 1 переменной. Этот доказательство заключается в том, что вы можете получить из функции 2 (или больше в общий случай) переменные до 1 переменной с чисто механическое преобразование текста, как это:

// Original
F = function (i, j) {
  ...
};
F(i,j);

// Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);

где ... остается именно то тот же. (Этот трюк называется "карринг" в честь своего изобретателя. Язык Haskell также является назван в честь Хаскелла Карри. Файл, который под бесполезные мелочи.) Теперь просто примените эту трансформацию везде, и мы получим наша окончательная версия.

// The dreaded Y-combinator in action!
function (builder) { return function (n) {
  return builder(builder)(n);
}}(
  function (recurse) { return function (n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse)(n - 1);
  }})(
  5
);

не стесняйтесь попробовать его. alert () это возвращение, привязать его к кнопке, что угодно. Этот код вычисляет факториалы, рекурсивно, без использования назначение, объявления или функции 2 переменных. (Но попытка проследить, как это работает, скорее всего, сделает ваш голова идет кругом. И вручая его, без вывода, просто слегка переформатировал приведет к коду, который обязательно озадачит и запутает.)

вы можете заменить 4 строки, которые рекурсивно определяют факториал с любая другая рекурсивная функция, которую вы хотите.

96

интересно, есть ли смысл пытаться построить это с нуля. Давай посмотрим. Вот базовая рекурсивная факторная функция:

function factorial(n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

давайте рефакторинг и создадим новую функцию под названием fact который возвращает анонимную факторно-вычислительную функцию вместо выполнения самого вычисления:

function fact() {
    return function(n) {
        return n == 0 ? 1 : n * fact()(n - 1);
    };
}

var factorial = fact();

это немного странно, но в этом нет ничего плохого. Мы просто генерируем новую факторную функцию на каждом шаге.

рекурсия на этом этапе все еще довольно явная. Элемент fact функция должна знать свое собственное имя. Давайте параметризуем рекурсивный вызов:

function fact(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
}

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

это здорово, но recurser все еще нужно знать свое собственное имя. Давайте параметризуем и это:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

теперь, вместо того, чтобы позвонить recurser(recurser) непосредственно, давайте создадим функцию-оболочку, которая возвращает свой результат:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

теперь мы можем избавиться от recurser имя в целом; это просто аргумент для внутренней функции Y, которую можно заменить самой функцией:

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

единственное внешнее имя, на которое все еще ссылаются, -fact, но теперь должно быть ясно, что это тоже легко параметризовано, создавая полное, общее решение:

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y(function(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
});
77

большинство ответов выше описывают, что такое Y-комбинатор и но не то, что он на.

комбинаторы с фиксированной точкой используются, чтобы показать, что лямбда-исчисление и turing complete. Это очень важный результат в теории вычислений и обеспечивает теоретическую основу для функциональное программирование.

изучение комбинаторов с фиксированной точкой также помогло мне действительно разберитесь в функциональном программировании. Однако я никогда не находил для них никакого применения в реальном программировании.

43

Y-комбинатор В JavaScript:

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  });
};

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120

Edit: Я многому учусь, глядя на код, но это немного трудно проглотить без какого - либо фона-извините за это. С некоторыми общими знаниями, представленными другими ответами, вы можете начать разбирать то, что происходит.

функция Y является "y-комбинатором". Теперь взгляните на var factorial линии, где используется Y-это. Обратите внимание, что вы передаете ему функцию, которая имеет параметр (в этом например, recurse), который также используется позже во внутренней функции. Имя параметра в основном становится именем внутренней функции, позволяющей ей выполнять рекурсивный вызов (поскольку она использует recurse() в его определении.) Y-комбинатор выполняет магию связывания иначе анонимной внутренней функции с именем параметра функции, переданной Y.

для полного объяснения того, как Y делает магию, проверьте связанные статьи (не мной кстати.)

22

для программистов, которые не сталкивались с функциональным программированием в глубине, и не хотят начинать сейчас, но слегка любопытны:

Y combinator-это формула, которая позволяет реализовать рекурсию в ситуации, когда функции не могут иметь имен, но могут передаваться как аргументы, использоваться как возвращаемые значения и определяться в других функциях.

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

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

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

в случае, если вам нужно идентифицировать его в полицейской линейке, это выглядит так:

Y = λf.(λx.f (x x)) (λx.f (x x))

вы обычно можете обнаружить его из-за повторения (λx.f (x x)).

The λ символы-это греческая буква лямбда, которая дает лямбда-исчислению свое название, и есть много (λx.t) термины стиля, потому что именно так выглядит лямбда-исчисление.

15

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

12

вот реализация JavaScript Y-комбинатора и факторной функции (из статьи Дугласа Крокфорда, доступной по адресу:http://javascript.crockford.com/little.html).

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);
6

Y-комбинатор-это другое название для конденсатора потока.

6

Я написал своего рода" руководство идиотов " к y-комбинатору как в Clojure, так и в Scheme, чтобы помочь себе справиться с этим. На них влияет материал в "маленьком Интригане"

В Схеме: https://gist.github.com/z5h/238891

или Clojure: https://gist.github.com/z5h/5102747

оба учебника-это код с вкраплениями комментариев и должны быть вырезаны и вставлены в ваш любимый редактор.

5

Y-комбинатор реализует анонимную рекурсию. Так что вместо

function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

можно сделать

function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

конечно, Y-комбинатор работает только в языках call-by-name. Если вы хотите использовать это в любом обычном языке call-by-value, то вам понадобится связанный z-комбинатор (y-комбинатор будет расходиться/бесконечный цикл).

4

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

3

этот оператор может упростить вашу жизнь:

var Y = function(f) {
    return (function(g) {
        return g(g);
    })(function(h) {
        return function() {
            return f.apply(h(h), arguments);
        };
    });
};

тогда вы избегаете дополнительной функции:

var fac = Y(function(n) {
    return n == 0 ? 1 : n * this(n - 1);
});

наконец, вы называете fac(5).

3

анонимная рекурсия

комбинатор с фиксированной точкой является функцией более высокого порядка fix что по определению соответствует эквивалентности

forall f.  fix f  =  f (fix f)

fix f представляет собой решение x к уравнению с фиксированной точкой

               x  =  f x

факториал натурального числа можно доказать с помощью

fact 0 = 1
fact n = n * fact (n - 1)

используя fix, произвольные конструктивные доказательства над общими / μ-рекурсивными функциями могут быть получены без nonymous собственной референциальности.

fact n = (fix fact') n

здесь

fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)

такое, что

   fact 3
=  (fix fact') 3
=  fact' (fix fact') 3
=  if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
=  3 * (fix fact') 2
=  3 * fact' (fix fact') 2
=  3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
=  3 * 2 * (fix fact') 1
=  3 * 2 * fact' (fix fact') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
=  3 * 2 * 1 * (fix fact') 0
=  3 * 2 * 1 * fact' (fix fact') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
=  3 * 2 * 1 * 1
=  6

это формальное доказательство того, что

fact 3  =  6

методически использует эквивалентность комбинатора с фиксированной точкой для переписывает

fix fact'  ->  fact' (fix fact')

лямбда-исчисление

The нетипизированное лямбда-исчисление формализм состоит в контекстно-свободной грамматики

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

здесь v диапазоны по переменным, вместе с помощью бета и снижение eta правила

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

бета-редукция заменяет все свободные вхождения переменной x в теле абстракции ("функции")B по выражению ("аргумент")E. Сокращение Eta устраняет избыточную абстракцию. Это иногда опущено из формализма. Ан неприводимых выражение, к которому не применяется правило сокращения, находится в нормальный или канонический форма.

λ x y. E

является сокращением для

λ x. λ y. E

(многомерность абстракции),

E F G

является сокращением для

(E F) G

(применение левой ассоциативности),

λ x. x

и

λ y. y

are Альфа-эквивалент.

абстракция и применение - это два единственных "языковых примитива" лямбда-исчисления, но они позволяют кодирование of произвольно сложные данные и операции.

церковные цифры являются кодировкой натуральных чисел, подобных Пеано-аксиоматическим натуралам.

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

формальное доказательство того, что

1 + 2  =  3

используя правило перезаписи бета-сокращения:

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

комбинаторы

в лямбда-исчислении, комбинаторы абстракции, которые не содержат свободных переменных. Самое простое:I, личность комбинатор

λ x. x

изоморфна функции идентичности

id x = x

такие комбинаторы являются примитивными операторами комбинатора конкременты как лыжная система.

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

бета-сокращение не сильно нормализуя; не все приводимые выражения, "редексы", сходятся к нормальной форме при бета-редукции. Простой пример-дивергентное применение Омеги ω комбинатор

λ x. x x

к себе:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

приоритет отдается уменьшению крайних левых подвыражений ("головок"). Аппликативного порядка!--66--> нормализует аргументы перед заменой, нормальный заказ нет. Эти две стратегии аналогичны нетерпеливой оценке, например C, и ленивой оценке, например Haskell.

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

расходится при нетерпеливом уменьшении бета-версии аппликативного порядка

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

так как в строго семантика

forall f.  f _|_  =  _|_

но сходится под ленивым бета-сокращением нормального порядка

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

если выражение имеет нормальную форму, бета-редукция нормального порядка найдет его.

Y

важным свойством!--46-->комбинатор с фиксированной точкой

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

дано

   Y g
=  (λ f. (λ x. f (x x)) (λ x. f (x x))) g
=  (λ x. g (x x)) (λ x. g (x x))           =  Y g
=  g ((λ x. g (x x)) (λ x. g (x x)))       =  g (Y g)
=  g (g ((λ x. g (x x)) (λ x. g (x x))))   =  g (g (Y g))
. . .                                      . . .

эквивалентности

Y g  =  g (Y g)

изоморфна к

fix f  =  f (fix f)

нетипизированное лямбда-исчисление может кодировать произвольные конструктивные доказательства над общими / μ-рекурсивными функциями.

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

(задержка умножения, слияние)

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

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

бета-редукция нормального порядка делает непротяженное нетипизированное лямбда-исчисление Тьюринг-полным перепишите систему.

в Haskell комбинатор с фиксированной точкой может быть элегантно реализован

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

лень Хаскелла нормализуется до конечности до того, как все подвыражения были оценены.

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])
2

как новичок в комбинаторах, я нашел статья Майка Ванье (спасибо Николаю Манкузо), чтобы быть действительно полезным. Я хотел бы написать резюме, помимо документирования моего понимания, если бы это могло помочь некоторым другим, я был бы очень рад.

с херовый to Меньше Дерьмовый

используя факториал в качестве примера, мы используем следующее almost-factorial функция для вычисления факториала числа x:

def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))

в псевдокоде выше,almost-factorial исполняет функции f и (almost-factorial Карри, так что это можно рассматривать как принимая в функции f и возвращает функцию 1-arity).

, когда almost-factorial вычисляет факториал x, он делегирует вычисление факториала для x - 1, чтобы функция f и накапливает этот результат с x (в этом случае он умножает результат (x-1) на икс.)

это можно рассматривать как almost-factorial принимает херовый версия факторной функции (которая может вычисляться только до числа x - 1) и возвращает a меньше-дерьмовый версия факториала (который вычисляет до числа x). Как в этой форме:

almost-factorial crappy-f = less-crappy-f

если мы неоднократно передаем меньше-дерьмовый версия для факторного almost-factorial, мы в конечном итоге получим нашу желаемую факторную функцию f. Где это может быть рассматривается как:

almost-factorial f = f

Fix-point

дело в том, что almost-factorial f = f означает f - это fix-point функции almost-factorial.

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

три функции

обобщить, у нас есть нерекурсивныйпрактически-полезным функции fn на полезноеfr

наследование Y (не входит в комплект)

я пропущу вывод Y и перейти к пониманию Y. У поста Майка Вайнера есть много деталей.

виде Y

Y определяется как (in лямбда-исчисление

1

вот ответы на оригинальные вопросы, составленного от статьи (что в целом стоит прочитать) упоминается в ответ Николаса Манкузо, а также другие ответы:

что такое Y-комбинатор?

Y-комбинатор-это "функционал" (или функция более высокого порядка-функция, которая работает с другими функциями), которая принимает один аргумент, который не является функцией рекурсивный, и возвращает версию функции, которая является рекурсивной.

несколько рекурсивно =), но более глубокое определение:

комбинатор - это просто лямбда-выражение без свободных переменных.
Свободная переменная - это переменная, которая не является связанной переменной.
связанная переменная-переменная, которая содержится внутри тела лямбда-выражения, которое имеет имя этой переменной в качестве одного из своих аргументов.

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

Y-комбинатор является комбинатором с фиксированной точкой.

фиксированная точка функции-это элемент домена функции, который отображается на себя с помощью функция.
то есть, c является фиксированной точкой функции f(x) Если f(c) = c
это значит f(f(...f(c)...)) = fn(c) = c

как работают комбинаторы?

ниже примерах предполагается сильный + динамический команды:

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

Y = λf.(λx.f(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))

это означает, что для данной функции f (не-рекурсивной функции), соответствующая рекурсивная функция может быть получена сначала путем вычисления λx.f(x x), а затем применить это лямбда-выражение к себе.

строгий (аппликативный порядок) Y-комбинатор:
это определение относится к языкам со строгим (также: нетерпеливый, жадный) оценка-стратегия оценки, в которой выражение оценивается, как только оно привязано к переменной.

Y = λf.(λx.f(λy.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) y)))

он такой же, как ленивый в его природе, он просто имеет лишний λ обертки для задержки оценки тела лямбды. Я спросил еще вопрос, несколько связанных с этой темой.

для чего они хороши?

украли заимствовано из ответ Крис Аммерман: Y-комбинатор обобщает рекурсию, абстрагируя ее реализацию и тем самым отделяя ее от реальной работы рассматриваемой функции.

несмотря на то, что Y-combinator имеет некоторые практические приложения, это в основном теоретическая концепция, понимание которой расширит ваше общее видение и, вероятно, повысит ваши аналитические и навыки разработчика.

они полезны в процедурном языки?

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

и отметил Крис Аммерман: большинство процедурных языков имеет статическую типизацию.

так что ответ на этот вопрос-не совсем.

1

Я думаю, что лучший способ ответить на это выбрать язык, как JavaScript:

function factorial(num)
{
    // If the number is less than 0, reject it.
    if (num < 0) {
        return -1;
    }
    // If the number is 0, its factorial is 1.
    else if (num == 0) {
        return 1;
    }
    // Otherwise, call this recursive procedure again.
    else {
        return (num * factorial(num - 1));
    }
}

теперь перепишите его так, чтобы он не использовал имя функции внутри функции, но все равно вызывал ее рекурсивно.

единственное место имя функции factorial должно быть видно на сайте вызова.

подсказка: вы не можете использовать имена функций, но вы можете использовать имена параметров.

работайте над проблемой. Не смотри туда. Как только вы его решите, вы поймет, какую задачу решает y-комбинатор.

0