[Malleys]

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

Мы можем перевести нашу функцию betterRecursive в формальный комбинатор, Y-комбинатор. Чтобы было понятней, давайте сначала представим рекурсивную функцию:

const isEven =
  n =>
    (n === 0) || !isEven(n - 1);

Функция, которая принимается функцией betterRecursive

const _isEven =
  (myself, n) =>
    (n === 0) || !myself(n - 1);

Увы, сейчас она принимает два параметра. Можно исправить, применив каррирование...

const __isEven =
  myself =>
    n =>
      (n === 0) || !myself(n - 1);

Вместо того, чтобы принимать два параметра (myself и n), теперь эта функция, которая принимает один параметр myself и возвращает функцию, которая принимает другой параметр n.

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

const Y =
  fn =>
    (
      maker =>
        (...args) =>
          fn(maker(maker), ...args)
    )(
      maker =>
        (...args) =>
          fn(maker(maker), ...args)
    );

Далее мы видим, что (...args) => fn(maker(maker), ...args) недопустимо, мы не используем деструктуризацию аргументов и применение полученного путём деструкткризации массива параметров к другой функции. Во-первых, мы изменяем ...args на arg, поскольку разрешен только один параметр:

const Y =
  fn =>
    (
      maker =>
        arg => fn(maker(maker), arg)
    )(
      maker =>
        arg => fn(maker(maker), arg)
    );

fn(maker(maker), arg) также не допускается, мы не передаем два параметра любой функции. Вместо этого мы передаем один параметр, получаем функцию обратно и передаем второй параметр этой функции....

const Y =
  fn =>
    (
      maker =>
        arg => fn(maker(maker))(arg)
    )(
      maker =>
        arg => fn(maker(maker))(arg)
    );

Или с более краткими именами, вариант, который упоминался ранее...

const Y =
	f => (
		g =>
			x => f(g(g))(x)
	)(
		g =>
			x => f(g(g))(x)
	);

Давай попробуем:

const Y =
	f => (
		g =>
			x => f(g(g))(x)
	)(
		g =>
			x => f(g(g))(x)
	);
	
alert(Y(
	myself =>
		n =>
			(n === 0) || !myself(n - 1)
)(1962));

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

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

Также вы можете использовать https://www.npmjs.com/package/y-combinator