Что такое Y-комбинатор? [закрыто]

392

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

  • Что такое Y-комбинатор?
  • Как работают комбинаторы?
  • Для чего они хороши?
  • Полезны ли они на процедурных языках?
Крис Аммерман
источник
12
Небольшой совет: если вы изучаете функциональные языки, как я, лучше оставляйте комбинаторы, пока вы не освоитесь с ними, иначе это дорога к безумию ...
Игорь Зевака
3
Должен улыбнуться серьезности
1
Я написал короткую суть, поделившись своим пониманием Y Combinator: gist.github.com/houtianze/b274e4b975a28fe08aee681699c3f7d0 Я объяснил (насколько я понимаю), как «Y Combinator выполняет рекурсивную функцию»
ibic
1
Как этот вопрос "слишком широкий"?
Рей Миясака

Ответы:

201

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

Николас Манкузо
источник
14
Это немного больше, чем ссылка; это ссылка с очень кратким изложением . Более краткое резюме будет оценено.
Мартин Питерс
2
Это просто ссылка, но она не может быть лучше, чем эта. Этот ответ заслуживает (add1 голоса) без базовых условий для выхода; ака бесконечная рекурсия.
Явар
7
@ Андрей Макфи: Я не прокомментировал усилия, я прокомментировал качество. В целом политика переполнения стека заключается в том, что ответы должны быть автономными и содержать ссылки на дополнительную информацию.
Йорген Фог
1
@ galdre прав. Это отличная ссылка, но это просто ссылка. Это также было упомянуто в 3 других ответах ниже, но только в качестве подтверждающего документа, поскольку они все хорошие объяснения самостоятельно. Этот ответ также даже не пытается ответить на вопросы ОП.
Тораритте
290

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

Крис Аммерман
источник
5
Почему вы должны называть это «Y» и параметр «F»! Они просто теряются в аргументах типа!
Брайан Хенк
3
В Haskell вы можете использовать рекурсию абстракции с помощью:, fix :: (a -> a) -> aи, aв свою очередь, может быть функцией столько аргументов, сколько вам нужно. Это означает, что статическая типизация на самом деле не делает это громоздким.
Пикер
12
Согласно описанию Майка Ванье, ваше определение Y на самом деле не является комбинатором, потому что оно рекурсивное. В разделе «Исключение (большей части) явной рекурсии (ленивая версия)» он имеет ленивую схему, эквивалентную вашему коду C #, но объясняет в пункте 2: «Это не комбинатор, потому что Y в теле определения является свободной переменной, которая ограничивается только после того, как определение завершено ... "Я думаю, что классная вещь о Y-комбинаторах состоит в том, что они производят рекурсию, оценивая фиксированную точку функции. Таким образом, они не нуждаются в явной рекурсии.
GrantJ
@GrantJ Вы делаете хорошую мысль. Прошло пару лет с тех пор, как я опубликовал этот ответ. Просматривая пост Ваньера, я вижу, что написал Y, но не Y-Combinator. Я скоро прочитаю его пост и посмотрю, смогу ли я опубликовать исправление. Моя интуиция предупреждает меня, что строгая статическая типизация C # может предотвратить это в конце концов, но я посмотрю, что я могу сделать.
Крис Аммерман
1
@WayneBurkett Это довольно распространенная практика в математике.
YoTengoUnLCD
102

Я поднял это с 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 в строке.

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

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

// 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 (), которые возвращают, привязывают к кнопке, что угодно. Этот код вычисляет факториалы рекурсивно, без использования присваивания, объявлений или функций двух переменных. (Но попытка проследить, как это работает, может привести к тому, что ваша голова закружится. А передача ее без деривации, только слегка переформатированная, приведет к коду, который наверняка сбьет с толку и запутает.)

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

btilly
источник
Хорошее объяснение. Почему ты написал function (n) { return builder(builder)(n);}вместо builder(builder)?
v7d8dpo4
@ v7d8dpo4 Потому что я превращал функцию от 2 переменных в функцию более высокого порядка для одной переменной с помощью каррирования.
Btilly
Это причина, по которой нам нужны закрытия?
TheChetan
1
@TheChetan Замыкания позволяют нам привязывать индивидуальное поведение к вызову анонимной функции. Это просто еще одна техника абстракции.
Btilly
85

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

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);
    };
});
Wayne
источник
Аналогичное объяснение в JavaScript: igstan.ro/posts/…
Pops
1
Вы потеряли меня, когда вы представили функцию recurser. Ни малейшего понятия, что он делает или почему.
Мёрре
2
Мы пытаемся создать общее рекурсивное решение для функций, которые не являются явно рекурсивными. Эта recurserфункция - первый шаг к этой цели, потому что она дает нам рекурсивную версию, factкоторая никогда не ссылается на себя по имени.
Уэйн
@WayneBurkett Могу ли я переписать Y комбинатор , как это: function Y(recurse) { return recurse(recurse); } let factorial = Y(creator => value => { return value == 0 ? 1 : value * creator(creator)(value - 1); });. И вот как я переварить это (не уверен, если это правильно): не явно ссылаясь на функцию (не допускается как комбинатор ), мы можем использовать две частично примененные / карри функции (функция создателя и функция вычисления), с какие мы можем создавать лямбда / анонимные функции, которые достигают рекурсии без необходимости имени для функции вычисления?
neevek
50

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

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

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

Йорген Фог
источник
24

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

Zach
источник
6
Javascript не нужен Y-комбинатор сделать анонимную рекурсию , потому что вы можете получить доступ к текущей функции с arguments.callee (см en.wikipedia.org/wiki/... )
xitrium
6
arguments.calleeне допускается в строгом режиме: developer.mozilla.org/en/JavaScript/…
dave1010
2
Вы все равно можете дать любой функции имя, и если это выражение функции, то это имя известно только внутри самой функции. (function fact(n){ return n <= 1? 1 : n * fact(n-1); })(5)
Esailija
1
кроме как в IE. kangax.github.io/nfe
VoronoiPotato
18

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

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

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

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

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

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

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

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

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

Эль Зорко
источник
это должен быть принятый ответ. Кстати, с U x = x x, Y = U . (. U)(злоупотребляя Haskell-подобной записи). IOW, с правильными комбинаторами Y = BU(CBU). Таким образом, Yf = U (f . U) = (f . U) (f . U) = f (U (f . U)) = f ((f . U) (f . U)).
Уилл Несс
13

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

Комбинатор с фиксированной точкой - это функция высшего порядка, 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

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

λ x. x x

к себе:

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

Сокращение крайних левых подвыражений («головы») является приоритетным. Аппликативный порядок нормализует аргументы перед заменой, нормальный порядок - нет. Эти две стратегии аналогичны активной оценке, например, 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

Существенное свойство комбинатора с 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)

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

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


источник
4
Хотя я ценю тщательность ответа, он никоим образом не подходит для программиста с небольшим математическим образованием после первого переноса строки.
Джаред Смит
4
@ jared-smith Ответ призван рассказать дополнительную историю Вонкайя о понятиях CS / математика, лежащих в основе Y-комбинатора. Я думаю, что, возможно, наилучшие возможные аналогии с известными концепциями были проведены уже другими авторами. Лично мне всегда нравилось сталкиваться с истинным происхождением, радикальной новизной идеи, а не с приятной аналогией. Я нахожу наиболее широкие аналогии неуместными и запутанными.
1
Привет, личность комбинатор λ x . x, как ты сегодня?
MaiaVictor
Мне нравится этот ответ больше всего . Это просто очистило все мои вопросы!
Студент
11

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

Алесь Хакл
источник
6

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

Y-Combinator - другое название конденсатора потока.

Джон Дэвис
источник
4
очень смешно. :) молодые (э) могут не узнать ссылку.
Уилл Несс
2
ха - ха! Да, молодой (я) все еще может понять ...
Я думал, что это было реально, и я оказался здесь. youtube.com/watch?v=HyWqxkaQpPw Недавняя статья futurism.com/scientists-made-real-life-flux-capacitor
Пила Thinkar Nay Htoo
Я думаю, что этот ответ может быть особенно запутанным для не говорящих по-английски. Можно было бы посвятить некоторое время пониманию этого утверждения, прежде чем (или никогда) не понять, что это юмористическая ссылка на популярную культуру. (Мне это нравится, я бы просто почувствовал себя плохо, если бы ответил на это и обнаружил, что кому-то это не понравилось)
Майк
5

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

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

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

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

z5h
источник
5

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

От дрянного к менее дрянному

Используя факториал в качестве примера, мы используем следующую 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

Fix-точка

Тот факт, что 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является полезным Funciton, мы можем использовать 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в книге, привел меня к этому посту.

Дапенг Ли
источник
5

Здесь приведены ответы на оригинальные вопросы , составленные из статьи (которую ВСЕГО стоит прочитать), упомянутой в ответе Николаса Манкузо , а также другие ответы:

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

Полезны ли они на процедурных языках?

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

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

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


источник
4

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 комбинатор может работать с передачей по значению и ленивым вычислением.
Quelklef
3

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

Томас Вагнер
источник
3

Оператор 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).

Шины
источник
0

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

zumalifeguard
источник
1
Вы уверены, что это не создает больше проблем, чем решает?
Noctis Skytower
1
Noctis, вы можете уточнить свой вопрос? Вы спрашиваете, создает ли сама концепция y-комбинатор больше проблем, чем решает, или вы говорите конкретно о том, что я решил продемонстрировать, в частности, с использованием JavaScript, или о моей конкретной реализации или моей рекомендации изучить его, открыв его как Я описал?
zumalifeguard