Цитата:
Цитата:
А значит вам нужно самим указать аргумент и это правильно...
function func(self, $params)
{
...
if (...) self($params);
}
И это использует имя функции только один раз, нет лишних переменных, есть strict mode и чистота функции. Вопрос только в том, как её запустить! |
Цитата:
Это даже покруче, чем eval) |
Цитата:
|
Цитата:
Цитата:
Рассмотрим рекурсивную функцию...
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, это именно то, что вы хотели! |
Функция 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 |
Цитата:
|
Цитата:
|
Malleys,
возможно и я когда нибудь пойму, что вы здесь написали ... :) :( :( :( |
Цитата:
здесь надо просто взять вызов Y(...) и размотать в обратную сторону, тогда будет понятно, что и как вызывается |
Цитата:
Цитата:
/* библиотека комбинаторов */
var Y =
f => (
g =>
x => f(g(g))(x)
)(
g =>
x => f(g(g))(x)
);
/* программа */
var qsort = sort => array => {
if(array.length <= 1) return array;
return [
...sort(array.filter(item => item < array[0])),
...array.filter(item => item === array[0]),
...sort(array.filter(item => item > array[0]))
];
};
alert(Y(qsort)([4,13,2,12,3,11,1,10,5,9,6,8,7]))
|
| Часовой пояс GMT +3, время: 06:17. |