|
Сообщение от drwhite
|
|
в моем примере "self" — это псевдокод, ссылка на функцию, аналог __FUNCTION__ в пхп. Неужто в JS нет такой возможности? Не верю)
|
В JS это arguments.callee, но вы не можете это использовать!
|
Сообщение от рони
|
|
для меня Y-комбинатор, выглядит как вместо имени функции будем использовать имя функции
|
Как раз-таки функция вообще может быть анонимной... Y-комбинатор делает возможной рекурсию, не требуя объявления переменных. Можно даже сделать анонимную функцию рекурсивной (что может быть полезно при использовании стрелочных функции)
Рассмотрим рекурсивную функцию...
const factorial = x => {
if (x === 1)
return 1;
else
return x * factorial(x - 1);
}
alert(factorial(5));
Она сейчас не удовлетворяет понятию чистоты функции, поскольку её результат зависит не только от входных параметров.
Но мы можем отделить рекурсивную функцию от самой себя. Вместо того, чтобы вызывать функцию по имени, мы можем организовать передачу рекурсивной функции в качестве параметра. Мы начинаем с того, что перепишем функцию, чтобы взять себя в качестве параметра, а также передать себя в качестве параметра.
(myself, x) => {
if (x === 1)
return 1;
else
return x * myself(myself, x - 1);
}
Эта функция работает только со своими аргументами.
Для функции, написанной в такой форме, можно написать такую функцию recursive, которая превратит нашу функцию в рекурсивную функцию.
const recursive = fn => (...args) => fn(fn, ...args);
const factorial = recursive(
(myself, x) => {
if (x === 1)
return 1;
else
return x * myself(myself, x - 1);
}
);
alert(factorial(5));
Поскольку теперь рекурсивная функция отделена от самой себя, мы можем сделать что-то вроде запоминания её значении:
const recursive = fn => (...args) => fn(fn, ...args);
const memoized = (fn, keymaker = JSON.stringify) => {
const cache = {};
return function(...args) {
const key = keymaker.call(this, args);
return cache[key] || (cache[key] = fn.apply(this, args));
}
};
const skipFirst = ([_, ...values]) => JSON.stringify(values);
const factorial = recursive(
memoized(
(myself, x) => {
if (x === 1)
return 1;
else
return x * myself(myself, x - 1);
},
skipFirst
)
);
alert(factorial(5));
Запоминание нашей рекурсивной функцей не требует каких-либо изменений в её коде. Это можно легко использовать в другом месте, если нужно.
Почему recursive нуждается в улучшении?
recursive — полезная функция, но у неё есть недостаток: в дополнение к переписыванию наших функций, чтобы взять себя в качестве параметра, мы также должны переписать их, чтобы они передавались сами собой. Итак, в дополнение к этому...
(myself, x) => ...
Мы также должны написать это...
myself(myself, x-1)
Если первое указывает, что используется, то последнее ерунда!
Нам нужна такая функция, как recursive, но она должна поддерживать функции, вызывающие себя так myself(x-1).
Давайте представим, что именно мы хотим. С recursive мы пишем:
const factorial = recursive(
(myself, x) => {
if (x === 1)
return 1;
else
return x * myself(myself, x - 1);
}
);
Нам нужен лучший рекурсивный комбинатор (ниже обозначен как ???), который позволит нам написать...
const factorial = ???(
(myself, x) => {
if (x === 1)
return 1;
else
return x * myself(x - 1);
}
);
Давайте сделаем!
Прежде чем мы начнем, есть несколько правил, которым мы должны следовать, если мы хотим переделать recursive в улучшенный комбинатор. Каждый комбинатор обладает следующими свойствами:
- Это функция.
- Он может использовать только свои параметры или ранее определенные комбинаторы, которые имеют такие же свойства. Это означает, что он не может ссылаться на не-комбинаторы — такие как константы, обычные функции или объекты из глобального пространства имен.
- Он не может быть объявлением именованной функции или выражением именованной функции.
- Он не может создать выражение с именованной функцией.
- Он не может объявлять никаких переменных и констант, кроме того, что получено через параметры.
- Он может вызывать функцию в своей реализации.
- В комбинаторной логике все комбинаторы принимают ровно один параметр, как и все функции, которые создают комбинаторы.
- Комбинаторная логика также избегает деструктуризации аргументов и применения полученного путём деструкткризации массива параметров к другой функции.
Давайте начнём с нашего объявленного выше комбинатора...
const recursive = fn => (...args) => fn(fn, ...args);
Во-первых, назовём его betterRecursive
const betterRecursive =
fn =>
(...args) =>
fn(fn, ...args);
Во-вторых, обозначим изменение, которое хотим сделать...
const betterRecursive =
fn =>
(...args) =>
fn(?, ...args);
Мы заменили fn на ? Почему? Потому что наша функция fn выглядит следующим образом: (myself, arg0, arg1, ..., argn) => .... Но мы хотим опустить myself, что выглядит следующим образом: (arg0, arg1, ..., argn) => .... Значит, это не может быть fn.
Но что тогда?
Давайте подумаем о функции recursive. Что она делает? Она принимает функцию (myself, arg0, arg1, ..., argn) => ... и возвращает функцию, которая выглядит следующим образом (arg0, arg1, ..., argn) => ....
Функция recursive — не подходит, но давайте предположим, что такая подходящяя функция существует. Мы назовем её maker, потому что она делает функцию, которую мы хотим.
Значит далее, шаг третий, мы заменим ? на maker(??). Мы знаем, что maker(??) делает функцию, которую мы хотим, но мы ещё не знаем, что мы должны передать ей:
const betterRecursive =
fn =>
(...args) =>
fn(maker(??), ...args);
Нужно выяснить откуда мы получаем maker и какие параметры мы передаем ему.
Поскольку выше мы договорились, что комбинатор не может объявлять никаких переменных и констант, кроме того, что получено через параметры, то становится ясно, что maker должен быть получен через аргумент, но тогда возникает вопрос с каким ??? вызывали такую функцию.
const betterRecursive =
fn => (
maker =>
(...args) =>
fn(maker(??), ...args)
)(???)
maker — это функция, которая принимает один или несколько параметров и возвращает функцию, которая выглядит следующим образом (...args) => fn(maker(??), ...args). Это функция, которую мы хотим передать функции fn как myself. Также как и в функции recursive, тут мы видим в коде выше такую функцию maker => (...args) => fn(maker(??), ...args), которая принимает один параметр (maker) и возвращает функцию, которая выглядит как (...args) => fn(maker(??), ...args)!
const betterRecursive =
fn => (
maker =>
(...args) =>
fn(maker(??), ...args)
)(
maker =>
(...args) =>
fn(maker(??), ...args)
)
Функция maker принимает один или несколько параметров и возвращает функцию, которая выглядит как (...args) => fn(maker(??), ...args)
maker => (...args) => fn(maker(??), ...args) — это функция, которая принимает один параметр (maker) и возвращает функцию, которая выглядит следующим образом (...args) => fn(maker(??), ...args).
Отсюда вывод — maker принимает один параметр maker и возвращает функцию, которая выглядит следующим образом (...args) => fn(maker(??), ...args). Поэтому выражение, которое нам нужно — maker(maker), а значит ?? является не более чем функцией maker!
const betterRecursive =
fn => (
maker =>
(...args) =>
fn(maker(maker), ...args)
)(
maker =>
(...args) =>
fn(maker(maker), ...args)
)
Давайте проверим...
const betterRecursive =
fn => (
maker =>
(...args) =>
fn(maker(maker), ...args)
)(
maker =>
(...args) =>
fn(maker(maker), ...args)
);
const factorial = betterRecursive(
(myself, x) => {
if (x === 1)
return 1;
else
return x * myself(x - 1);
}
);
alert(factorial(5));
Вуаля! Рабочая betterRecursive!
drwhite, это именно то, что вы хотели!
