Вопрос

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

  • Что такое Y-комбинатор?
  • Как работают комбинаторы?
  • Чем они хороши?
  • Полезны ли они в процедурных языках?
Это было полезно?

Решение

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

Другие советы

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-Combinator делает это, будучи функцией с постоянным именем, которая может вводить рекурсию.

// 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, завершив рекурсию.

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

Я взял это из 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 и y inline.

// 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 переменной.Можем ли мы это исправить?Что ж, умный парень по имени Haskell Curry имеет аккуратный трюк, если у вас есть хорошие функции более высокого порядка, вам нужны только функции 1 переменной.Доказательство того, что вы можете получить от функций 2 (или более в общем случае) до 1 переменной с чисто механическим трансформацией текста, как это:

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

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

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

// 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 линии, которые рекурсивно определяют факториал любой другой рекурсивной функцией, которую вы хотите.

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

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);
    };
});

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

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

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

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

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

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

Полное объяснение того, как Y творит чудеса, можно найти в связанная статья (не мной, кстати.)

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

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

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

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

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

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

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

Обычно вы можете заметить это из-за повторяющихся (λx.f (x x)).

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

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

Вот реализация Y-Combinator и функции Factorial на JavaScript (из статьи Дугласа Крокфорда, доступной по адресу: 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);

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

Я написал своего рода «руководство для идиотов» по ​​Y-Combinator как в Clojure, так и в Scheme, чтобы помочь себе разобраться с ним.На них повлиял материал из «Маленького интригана».

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

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

Оба руководства представляют собой код, перемежающийся комментариями, и их следует вырезать и вставлять в ваш любимый редактор.

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

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

forall f.  fix f  =  f (fix f)

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

               x  =  f x

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

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

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

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')

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

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

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

где v варьируется по переменным вместе с бета и эта-редукция правила

(λ 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

являются альфа-эквивалент.

Абстракция и применение — два единственных «языковых примитива» лямбда-исчисления, но они позволяют кодирование произвольно сложных данных и операций.

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

   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

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

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

Сокращение крайних левых подвыражений («голов») имеет приоритет. Аппликативный порядок нормализует аргументы перед заменой, нормальный порядок не.Эти две стратегии аналогичны нетерпеливой оценке, например.C и ленивая оценка, например.Хаскелл.

   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 комбинатор с фиксированной точкой

λ 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)

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

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

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-комбинатор работает только на языках с вызовом по имени.Если вы хотите использовать это в любом обычном языке вызова по значению, вам понадобится соответствующий z-комбинатор (y-комбинатор будет расходиться/бесконечный цикл).

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

От Дерьмовый к Меньше дряни

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

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

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

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

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

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

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

almost-factorial f = f

Фиксированная точка

Дело в том, что almost-factorial f = f означает f это фиксированная точка функции almost-factorial.

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

Три функции

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

Итак, подводя итог (упрощая, предполагая fr принимает только один параметр; x вырождается в x - 1, x - 2...в рекурсии):

  • Мы определяем основные расчеты как fn: def fn fr x = ...accumulate x with result from (fr (- x 1)), это почти полезный функция - хотя мы не можем использовать fn прямо на x, очень скоро пригодится.Это нерекурсивный fn использует функцию fr подсчитать его результат
  • fn fr = fr, fr является фиксированной точкой fn, fr это полезный функция, мы можем использовать fr на x чтобы получить наш результат
  • Y fn = fr, Y возвращает фиксированную точку функции, Y превращает наш почти полезный функция fn в полезный fr

Получение Y (не включено)

Я пропущу вывод Y и иди к пониманию Y.В посте Майка Вайнера много подробностей.

Форма Y

Y определяется как (в лямбда-исчисление формат):

Y f = λs.(f (s s)) λs.(f (s s))

Если мы заменим переменную s слева от функций мы получаем

Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)

Так что действительно, результат (Y f) является фиксированной точкой f.

Почему (Y f) работа?

В зависимости от подписи f, (Y f) может быть функцией любой арности, для упрощения предположим (Y f) принимает только один параметр, как наша функция факториал.

def fn fr x = accumulate x (fr (- x 1))

с fn fr = fr, мы продолжаем

=> accumulate x (fn fr (- x 1))
=> accumulate x (accumulate (- x 1) (fr (- x 2)))
=> accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))

рекурсивный расчет завершается, когда самый внутренний (fn fr 1) является базовым случаем и fn не использует fr в расчете.

Смотря на Y снова:

fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))

Так

fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x

На мой взгляд, волшебные части этой установки:

  • fn и fr зависят друг от друга: fr "обертывания" fn внутри, каждый раз fr используется для расчета x, он «порождает» («поднимает»?) fn и делегирует вычисления этому fn (переходя в себя fr и x);с другой стороны, fn зависит от fr и использует fr вычислить результат меньшей задачи x-1.
  • В то время fr используется для определения fn (когда fn использует fr в своей деятельности), реальная fr еще не определен.
  • Его fn который определяет реальную бизнес-логику.На основе fn, Y создает fr - вспомогательная функция в определенном виде - для облегчения расчета fn в рекурсивный образом.

Это помогло мне понять Y сейчас так, надеюсь, это поможет.

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

Вот ответы на оригинальные вопросы, составлено из статья (который ПОЛНОСТЬЮ стоит прочитать), упомянутый в ответ Николаса Манкузо, а также другие ответы:

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

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


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

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

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

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-комбинатор не имеет простого статического типа. .Это выходит за рамки данной статьи, поэтому я не буду упоминать об этом дальше.

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

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

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

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

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).

Я думаю, что лучший способ ответить на этот вопрос — выбрать язык, например 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-комбинатор.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top