Как заменить циклы while функциональной альтернативой программирования без оптимизации хвостового вызова?

Question

Как заменить циклы while функциональной альтернативой программирования без оптимизации хвостового вызова?

Я экспериментирую с более функциональным стилем в моем JavaScript; поэтому я заменил для циклов с помощью служебных функций, таких как отображение и уменьшение. Тем не менее, я не нашел функциональной замены для циклов while, поскольку оптимизация хвостового вызова обычно недоступна для JavaScript. (Из того, что я понимаю, ES6 предотвращает переполнение стековых вызовов, но не оптимизирует их производительность.)

Ниже я объясню, что я попробовал, но TLDR: если у меня нет оптимизации хвостового вызова, каков функциональный способ реализации циклов while?

Что я пробовал:

Создание функции полезности while:

function while(func, test, data) {
  const newData = func(data);
  if(test(newData)) {
    return newData;
  } else {
    return while(func, test, newData);
  }
}

Поскольку оптимизация хвостового вызова недоступна, я мог бы переписать это как:

function while(func, test, data) {
  let newData = *copy the data somehow*
  while(test(newData)) {
    newData = func(newData);
  }
  return newData;
}

Однако в этот момент мне кажется, что я сделал свой код более сложным / запутанным для всех, кто его использует, так как мне приходится искать полезную функцию. Единственное практическое преимущество, которое я вижу, состоит в том, что оно заставляет меня сделать цикл чистым; но кажется, что было бы проще просто использовать обычный цикл while и следить за тем, чтобы все было чисто.

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

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

Итак, после всего этого, мой общий вопрос: если мне нужен цикл while, я программирую в функциональном стиле, и у меня нет доступа к оптимизации хвостовых вызовов, то какая стратегия лучше?

64

javascript recursion while-loop functional-programming tail-call-optimization

Источник

user7206559 24 апр '17 в 15:24

3 ответа

Решение

Лучше `loop`/`recur` шаблон

Есть две вещи, которые мне не нравятся в loop/recurшаблон, описанный в принятом ответе. Обратите внимание, что мне действительно нравится идея, лежащая в основеloop/recurшаблон. Однако мне не нравится, как это реализовано. Итак, давайте сначала посмотрим, как я бы это реализовал.

// Recur ::a -> Result a b
const Recur = (...args) => ({ recur: true, args });

// Return :: b-> Result a b
const Return = value => ({ recur: false, value });

// loop :: (a -> Result a b) -> a -> b
const loop = func => (...args) => {
    let result = func(...args);
    while (result.recur) result = func(...result.args);
    return result.value;
};

// repeat :: (Int, a -> a, a) -> a
const repeat = loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)));

console.time("loop/recur/return");
console.log(repeat(1e6, x => x + 1, 0));
console.timeEnd("loop/recur/return");

Сравните это с loop/recur шаблон, описанный в вышеупомянутом ответе.

// recur ::a -> Recur a
const recur = (...args) => ({ recur, args });

// loop :: (a? -> Recur a ∪ b) -> b
const loop = func => {
    let result = func();
    while (result && result.recur === recur) result = func(...result.args);
    return result;
};

// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((m = n, r = x) => m === 0 ? r : recur(m - 1, f(r)));

console.time("loop/recur");
console.log(repeat(1e6, x => x + 1, 0));
console.timeEnd("loop/recur");

Если вы заметили, подпись типа второго loopфункция использует параметры по умолчанию (т.е.a?) и немаркированные союзы (т.е.Recur a ∪ b). Обе эти возможности противоречат парадигме функционального программирования.

Проблема с параметрами по умолчанию

В loop/recurшаблон в вышеупомянутом ответе использует параметры по умолчанию для предоставления начальных аргументов функции. Я считаю, что это злоупотребление параметрами по умолчанию. Вы можете так же легко предоставить начальные аргументы, используя мою версиюloop.

// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((n, x) => n === 0 ? Return(x) : Recur(n - 1, f(x)))(n, x);

// or more readable
const repeat = (n, f, x) => {
    const repeatF = loop((n, x) => n === 0 ? Return(x) : Recur(n - 1, f(x)));
    return repeatF(n, x);
};

Более того, он позволяет преобразовывать eta, когда все аргументы переданы.

// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)))(n, f, x);

// can be η-converted to
const repeat = loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)));

Используя версию loopс параметрами по умолчанию не позволяет конвертировать eta. Кроме того, он заставляет вас переименовывать параметры, потому что вы не можете писать(n = n, x = x) => ... в JavaScript.

Проблема с немаркированными союзами

Нетегированные союзы плохи, потому что они стирают важную информацию, то есть информацию о том, откуда пришли данные. Например, потому что мойResult тип помечен я могу различить Return(Recur(0)) от Recur(0).

С другой стороны, поскольку правосторонний вариант Recur a ∪ b не помечен, если b специализируется на Recur a, т.е. если тип специализируется на Recur a ∪ Recur a, то невозможно определить, Recur a пришел с левой или с правой стороны.

Одна критика может заключаться в том, что b никогда не будет специализироваться на Recur a, а значит, не имеет значения, что bбез тегов. Вот простой контрпример этой критике.

// recur ::a -> Recur a
const recur = (...args) => ({ recur, args });

// loop :: (a? -> Recur a ∪ b) -> b
const loop = func => {
    let result = func();
    while (result && result.recur === recur) result = func(...result.args);
    return result;
};

// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((m = n, r = x) => m === 0 ? r : recur(m - 1, f(r)));

// infinite loop
console.log(repeat(1, x => recur(1, x), "wow, such hack, much loop"));

// unreachable code
console.log("repeat wasn't hacked");

Сравните это с моей версией repeat который является пуленепробиваемым.

// Recur ::a -> Result a b
const Recur = (...args) => ({ recur: true, args });

// Return :: b-> Result a b
const Return = value => ({ recur: false, value });

// loop :: (a -> Result a b) -> a -> b
const loop = func => (...args) => {
    let result = func(...args);
    while (result.recur) result = func(...result.args);
    return result.value;
};

// repeat :: (Int, a -> a, a) -> a
const repeat = loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)));

// finite loop
console.log(repeat(1, x => Recur(1, x), "wow, such hack, much loop"));

// reachable code
console.log("repeat wasn't hacked");

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

Вывод

Процитирую дзен Python.

Явное лучше, чем неявное.

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

В `Trampoline` монада

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

В Trampoline монада - более могущественная кузина Loop монада, которая является loopфункция преобразована в монаду. Итак, начнем с пониманияLoopмонада. Тогда мы увидим основную проблемуLoop монада и как Trampoline монаду можно использовать для решения этой проблемы.

// Recur ::a -> Result a b
const Recur = (...args) => ({ recur: true, args });

// Return :: b-> Result a b
const Return = value => ({ recur: false, value });

// Loop :: (a -> Result a b) -> a -> Loop b
const Loop = func => (...args) => ({ func, args });

// runLoop :: Loop a -> a
const runLoop = ({ func, args }) => {
    let result = func(...args);
    while (result.recur) result = func(...result.args);
    return result.value;
};

// pure ::a -> Loop a
const pure = Loop(Return);

// bind :: (Loop a, a -> Loop b) -> Loop b
const bind = (loop, next) => Loop(({ first, loop: { func, args } }) => {
    const result = func(...args);
    if (result.recur) return Recur({ first, loop: { func, args: result.args } });
    if (first) return Recur({ first: false, loop: next(result.value) });
    return result;
})({ first: true, loop });

// ack :: (Int, Int) -> Loop Int
const ack = (m, n) => {
    if (m === 0) return pure(n + 1);
    if (n === 0) return ack(m - 1, 1);
    return bind(ack(m, n - 1), n => ack(m - 1, n));
};

console.log(runLoop(ack(3, 4)));

Обратите внимание, что loop был разделен на Loop и runLoopфункция. Структура данных, возвращаемаяLoop это монада, а pure а также bindфункции реализуют его монадический интерфейс. Мы используемpure а также bindфункции для написания простой реализации функции Аккермана.

К сожалению, ack не безопасна для стека, потому что она рекурсивно вызывает себя, пока не достигнет pureценность. Вместо этого мы хотели быack вернуть Recurкак структура данных для его индуктивных случаев. Однако,Recur значения имеют тип Result вместо того Loop. Эта проблема решаетсяTrampoline монада.

// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return ::a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// pure ::a -> Trampoline a
const pure = Return;

// bind :: (Trampoline a, a -> Trampoline b) -> Trampoline b
const bind = (first, next) => first.bounce ?
    Bounce(args => bind(first.func(...args), next))(first.args) :
    next(first.value);

// ack :: (Int, Int) -> Trampoline Int
const ack = Bounce((m, n) => {
    if (m === 0) return pure(n + 1);
    if (n === 0) return ack(m - 1, 1);
    return bind(ack(m, n - 1), n => ack(m - 1, n));
});

console.log(trampoline(ack(3, 4)));

В Trampoline тип данных - это комбинация Loop а также Result. ВLoop а также Recur конструкторы данных объединены в единый Bounceконструктор данных. ВrunLoop функция была упрощена и переименована в trampoline. Вpure а также bindфункции также были упрощены. По факту,pure просто Return. Наконец, мы применяемBounce к исходной реализации ack функция.

Еще одно преимущество Trampolineв том, что его можно использовать для определения взаимно рекурсивных функций, безопасных для стека. Например, вот реализация функций женской и мужской последовательности Hofstadter.

// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return ::a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// pure ::a -> Trampoline a
const pure = Return;

// bind :: (Trampoline a, a -> Trampoline b) -> Trampoline b
const bind = (first, next) => first.bounce ?
    Bounce(args => bind(first.func(...args), next))(first.args) :
    next(first.value);

// female :: Int -> Trampoline Int
const female = Bounce(n => n === 0 ? pure(1) :
    bind(female(n - 1), f =>
        bind(male(f), m =>
            pure(n - m))));

// male :: Int -> Trampoline Int
const male = Bounce(n => n === 0 ? pure(0) :
    bind(male(n - 1), m =>
        bind(female(m), f =>
            pure(n - f))));

console.log(Array.from({ length: 21 }, (_, n) => trampoline(female(n))).join(" "));
console.log(Array.from({ length: 21 }, (_, n) => trampoline(male(n))).join(" "));

Основная проблема при написании монадического кода - это ад обратного вызова. Однако это можно решить с помощью генераторов.

// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return ::a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// pure ::a -> Trampoline a
const pure = Return;

// bind :: (Trampoline a, a -> Trampoline b) -> Trampoline b
const bind = (first, next) => first.bounce ?
    Bounce(args => bind(first.func(...args), next))(first.args) :
    next(first.value);

// bounce :: (a -> Generator (Trampoline b)) -> a -> Trampoline b
const bounce = func => Bounce((...args) => {
    const gen = func(...args);

    const next = data => {
        const { value, done } = gen.next(data);
        return done ? value : bind(value, next);
    };

    return next(undefined);
});

// female :: Int -> Trampoline Int
const female = bounce(function* (n) {
    return pure(n ? n - (yield male(yield female(n - 1))) : 1);
});

// male :: Int -> Trampoline Int
const male = bounce(function* (n) {
    return pure(n ? n - (yield female(yield male(n - 1))) : 0);
});

console.log(Array.from({ length: 21 }, (_, n) => trampoline(female(n))).join(" "));
console.log(Array.from({ length: 21 }, (_, n) => trampoline(male(n))).join(" "));

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

Вывод

Если вы хотите писать косвенно или взаимно рекурсивные функции, безопасные для стека, или монадические функции, безопасные для стека, используйте Trampolineмонада. Если вы хотите писать немонадические, напрямую рекурсивные, безопасные для стека функции, используйтеloop/recur/return шаблон.

13

Источник

user783743 20 ноя '19 в 11:35

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

Чтобы преобразовать хвостовую рекурсивную функцию в безопасную для стека версию, мы должны рассмотреть два случая:

базовый вариант
рекурсивный случай

Мы должны сделать выбор, и это хорошо сочетается с помеченными профсоюзами. Тем не менее, Javascript не имеет такого типа данных, поэтому мы должны либо создать его, либо вернуться к Object кодировок.

Кодированный объект

// simulate a tagged union with two Object types

const Loop = x =>
  ({value: x, done: false});
  
const Done = x =>
  ({value: x, done: true});

// trampoline

const tailRec = f => (...args) => {
  let step = Loop(args);

  do {
    step = f(Loop, Done, step.value);
  } while (!step.done);

  return step.value;
};

// stack-safe function

const repeat = n => f => x =>
  tailRec((Loop, Done, [m, y]) => m === 0
    ? Done(y)
    : Loop([m - 1, f(y)])) (n, x);

// run...

const inc = n =>
  n + 1;

console.time();
console.log(repeat(1e6) (inc) (0));
console.timeEnd();

Функция закодирована

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

// type/data constructor

const Type = Tcons => (tag, Dcons) => {
  const t = new Tcons();
  t.run = cases => Dcons(cases);
  t.tag = tag;
  return t;
};

// tagged union specific for the case

const Step = Type(function Step() {});

const Done = x =>
  Step("Done", cases => cases.Done(x));
  
const Loop = args =>
  Step("Loop", cases => cases.Loop(args));

// trampoline

const tailRec = f => (...args) => {
  let step = Loop(args);

  do {
    step = f(step);
  } while (step.tag === "Loop");

  return step.run({Done: id});
};

// stack-safe function

const repeat = n => f => x => 
  tailRec(step => step.run({
    Loop: ([m, y]) => m === 0 ? Done(y) : Loop([m - 1, f(y)]),
    Done: y => Done(y)
  })) (n, x);

// run...

const inc = n => n + 1;
const id = x => x;

console.log(repeat(1e6) (inc) (0));

2

Источник

user6445533 25 апр '17 в 18:51

Смотрите также развернуть который (из Рамда документов)

Создает список из начального значения. Принимает функцию итератора, которая возвращает либо false, чтобы остановить итерацию, либо массив длины 2, содержащий значение, добавляемое в результирующий список, и начальное число, которое будет использоваться при следующем вызове функции итератора.

var r = n => f => x => x > n ? false : [x, f(x)];
var repeatUntilGreaterThan = n => f => R.unfold(r(n)(f), 1);
console.log(repeatUntilGreaterThan(10)(x => x + 1));

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.22.1/ramda.min.js"></script>

1

Источник

user21424 11 янв '18 в 11:52

Я много думал об этом вопросе. Недавно я натолкнулся на необходимость функционального цикла while.

Мне кажется, что единственное, что на самом деле хочет этот вопрос, - это способ встроить цикл while. Есть способ сделать это с помощью замыкания.

"some string "+(a=>{
   while(comparison){
      // run code
   }
   return result;
})(somearray)+" some more"

В качестве альтернативы, если то, что вы хотите, является чем-то, что цепляет массив, тогда вы можете использовать метод Reduce.

somearray.reduce((r,o,i,a)=>{
   while(comparison){
      // run code
   }
   a.splice(1); // This would ensure only one call.
   return result;
},[])+" some more"

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

0

Источник

user836392 19 дек '18 в 16:49

Другие вопросы по тегам javascript recursion while-loop functional-programming tail-call-optimization

user633183 24 апр '17 в 19:32 2017-04-24 19:32 · Accepted Answer · 2017-04-24 19:32

Пример в JavaScript

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

const repeat = n => f => x =>
  n === 0 ? x : repeat (n - 1) (f) (f(x))
  
console.log(repeat(1e3) (x => x + 1) (0)) // 1000
console.log(repeat(1e5) (x => x + 1) (0)) // Error: Uncaught RangeError: Maximum call stack size exceeded

Батуты

Мы можем обойти это ограничение, изменив способ написания повторения, но только немного. Вместо того, чтобы возвращать значение напрямую или сразу же, мы вернем один из наших двух типов батутов, Bounce или же Done, Тогда мы будем использовать наши trampoline функция для обработки цикла.

// trampoline
const Bounce = (f,x) => ({ isBounce: true, f, x })

const Done = x => ({ isBounce: false, x })

const trampoline = ({ isBounce, f, x }) => {
  while (isBounce)
    ({ isBounce, f, x } = f(x))
  return x
}

// our revised repeat function, now stack-safe
const repeat = n => f => x =>
  n === 0 ? Done(x) : Bounce(repeat (n - 1) (f), f(x))


// apply trampoline to the result of an ordinary call repeat
let result = trampoline(repeat(1e6) (x => x + 1) (0))

// no more stack overflow
console.log(result) // 1000000

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

// aux helper hides trampoline implementation detail
// runs about 2x as fast
const repeat = n => f => x => {
  const aux = (n, x) =>
    n === 0 ? Done(x) : Bounce(x => aux (n - 1, x), f (x))
  return trampoline (aux (n, x))
}

Clojure стиле loop / recur

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

Clojure создает специализированный батутный интерфейс, который использует пару функций, loop а также recur - эта тандемная пара поддается удивительно элегантному выражению программы

Ох, и это действительно быстро

const recur = (...args) =>
  ({ type: recur, args })
  
const loop = f =>
  {
    let acc = f ()
    while (acc && acc.type === recur)
      acc = f (...acc.args)
    return acc
  }

const repeat = $n => $f => $x =>
  loop ((n = $n, f = $f, x = $x) =>
    n === 0
      ? x
      : recur (n - 1, f, f (x)))
 
console.time ('loop/recur')
console.log (repeat (1e6) (x => x + 1) (0)) // 1000000
console.timeEnd ('loop/recur')              // 24 ms

Продолжение монады

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

// trampoline
const Bounce = (f,x) => ({ isBounce: true, f, x })

const trampoline = t => {
  while (t && t.isBounce)
    t = t.f(t.x)
  return t
}

// Continuation monad; stack-safe implementation
const Cont = f => ({
  _runCont: f,
  chain: g =>
    Cont(k =>
      Bounce(f, x =>
        Bounce(g(x)._runCont, k)))
})

Cont.of = x => Cont(k => k(x))

const runCont = (m,k) =>
  trampoline(Bounce(m._runCont, k))

// repeat now leaks no implementation detail that a trampoline is used
const repeat = n => f => x => {
  const aux = (n,x) =>
    n === 0 ? Cont.of(x) : Cont.of(f(x)).chain(x => aux(n - 1, x))
  return runCont(aux(n,x), x => x)
}

// looks like any other function, still stack-safe
console.log(repeat(1e5) (x => x + 1) (0))

Y комбинатор

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

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

const bounce = f => (...xs) =>
  ({ isBounce: true, f, xs })

const trampoline = t => {
  while (t && t.isBounce)
    t = t.f(...t.xs)
  return t
}

// stack-safe Y combinator
const Y = f => {
  const safeY = f =>
    bounce((...xs) => f (safeY (f), ...xs))
  return (...xs) =>
    trampoline (safeY (f) (...xs))
}

// recur safely to your heart's content
const repeat = Y ((recur, n, f, x) =>
  n === 0
    ? x
    : recur (n - 1, f, f (x)))
  
console.log(repeat (1e5, x => x + 1, 0)) // 10000

Практичность с while петля

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

Для всех намерений и целей это repeat Функция работает идентично приведенным выше, за исключением того, что эта функция примерно в один-два раза быстрее (за исключением loop / recur решение). Черт возьми, это, пожалуй, намного легче читать.

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

const repeat = n => f => x => {
  let m = n
  while (true) {
    if (m === 0)
      return x
    else
      (m = m - 1, x = f (x))
  }
}

const gadzillionTimes = repeat(1e8)

const add1 = x => x + 1

const result = gadzillionTimes (add1) (0)

console.log(result) // 100000000

setTimeout НЕ является решением проблемы переполнения стека

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

Некоторые люди нашли сайт для вопросов и ответов, который поддерживает эту ужасную стратегию.

Какие наши repeat будет выглядеть как использование setTimeout - обратите внимание, это также определено в стиле передачи продолжения - то есть мы должны вызвать repeat с обратным вызовом (k) чтобы получить окончательное значение

// do NOT implement recursion using setTimeout
const repeat = n => f => x => k =>
  n === 0
    ? k (x)
    : setTimeout (x => repeat (n - 1) (f) (x) (k), 0, f (x))
    
// be patient, this one takes about 5 seconds, even for just 1000 recursions
repeat (1e3) (x => x + 1) (0) (console.log)

// comment the next line out for absolute madness
// 10,000 recursions will take ~1 MINUTE to complete
// paradoxically, direct recursion can compute this in a few milliseconds
// setTimeout is NOT a fix for the problem
// -----------------------------------------------------------------------------
// repeat (1e4) (x => x + 1) (0) (console.log)

Я не могу не подчеркнуть, насколько это плохо. Четное 1e5 бежать так долго, что я бросил пытаться измерить это. Я не включаю это в тесты ниже, потому что это слишком медленно, чтобы даже считаться жизнеспособным подходом.

обещания

Обещания имеют возможность цепочки вычислений и безопасны в стеке. Тем не менее, достижение стека безопасно repeat Использование Promises означает, что нам придется отказаться от нашего синхронного возвращаемого значения, так же, как мы использовали setTimeout, Я представляю это как "решение", потому что оно решает проблему, в отличие от setTimeout, но в некотором смысле это очень просто по сравнению с батутом или продолжением монады. Как вы можете себе представить, производительность немного плохая, но далеко не такая плохая, как setTimeout пример выше

Стоит отметить, что в этом решении детали реализации Promise полностью скрыты от вызывающей стороны. Одиночное продолжение предоставляется в качестве 4-го аргумента и вызывается, когда вычисление завершено.

const repeat = n => f => x => k =>
  n === 0
    ? Promise.resolve(x).then(k)
    : Promise.resolve(f(x)).then(x => repeat (n - 1) (f) (x) (k))
    
// be patient ...
repeat (1e6) (x => x + 1) (0) (x => console.log('done', x))

Ориентиры

Серьезно, while Цикл намного быстрее - почти в 100 раз быстрее (при сравнении лучшего и худшего - но не включает асинхронные ответы: setTimeout а также Promise)

// sync
// -----------------------------------------------------------------------------
// repeat implemented with basic trampoline
console.time('A')
console.log(tramprepeat(1e6) (x => x + 1) (0))
console.timeEnd('A')
// 1000000
// A 114 ms

// repeat implemented with basic trampoline and aux helper
console.time('B')
console.log(auxrepeat(1e6) (x => x + 1) (0))
console.timeEnd('B')
// 1000000
// B 64 ms

// repeat implemented with cont monad
console.time('C')
console.log(contrepeat(1e6) (x => x + 1) (0))
console.timeEnd('C')
// 1000000
// C 33 ms

// repeat implemented with Y
console.time('Y')
console.log(yrepeat(1e6) (x => x + 1) (0))
console.timeEnd('Y')
// 1000000
// Y 544 ms

// repeat implemented with while loop
console.time('D')
console.log(whilerepeat(1e6) (x => x + 1) (0))
console.timeEnd('D')
// 1000000
// D 4 ms

// async
// -----------------------------------------------------------------------------

// repeat implemented with Promise
console.time('E')
promiserepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('E')
// 1000000
// E 2224 ms

// repeat implemented with setTimeout; FAILED
console.time('F')
timeoutrepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('F')
// ...
// too slow; didn't finish after 3 minutes

Каменный век JavaScript

Вышеупомянутые методы демонстрируются с использованием новых синтаксисов ES6, но вы можете реализовать батут в самой ранней версии JavaScript - для этого требуется только while и функции первого класса

Ниже мы используем javascript каменного века, чтобы продемонстрировать, что бесконечная рекурсия возможна и эффективна без необходимости жертвовать синхронным возвращаемым значением - 100000000 рекурсий менее чем за 6 секунд - это существенная разница по сравнению с setTimeout который может сделать только 1000 рекурсий за одно и то же время.

function trampoline (t) {
  while (t && t.isBounce)
    t = t.f (t.x);
  return t.x;
}

function bounce (f, x) {
  return { isBounce: true, f: f, x: x };
}

function done (x) {
  return { isBounce: false, x: x };
}

function repeat (n, f, x) {
  function aux (n, x) {
    if (n === 0)
      return done (x);
    else 
      return bounce (function (x) { return aux (n - 1, x); }, f (x));
  }
  return trampoline (aux (n, x));
}

console.time('JS1 100K');
console.log (repeat (1e5, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100K');
// 100000
// JS1 100K: 15ms

console.time('JS1 100M');
console.log (repeat (1e8, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100M');
// 100000000
// JS1 100K: 5999ms

Неблокирующая бесконечная рекурсия с использованием каменного века JavaScript

Если по какой-то причине вы хотите неблокирующую (асинхронную) бесконечную рекурсию, мы можем положиться на setTimeout отложить один кадр в начале вычисления. Эта программа также использует javascript каменного века и вычисляет 100000000 рекурсий менее чем за 8 секунд, но на этот раз неблокирующим образом.

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

В современной программе, учитывая обещания, мы заменили бы setTimeout призыв к одному обещанию.

function donek (k, x) {
  return { isBounce: false, k: k, x: x };
}

function bouncek (f, x) {
  return { isBounce: true, f: f, x: x };
}

function trampolinek (t) {
  // setTimeout is called ONCE at the start of the computation
  // NOT once per recursion
  return setTimeout(function () {
    while (t && t.isBounce) {
      t = t.f (t.x);
    }
    return t.k (t.x);
  }, 0);
}

// stack-safe infinite recursion, non-blocking, 100,000,000 recursions in under 8 seconds
// now repeatk expects a 4th-argument callback which is called with the asynchronously computed result
function repeatk (n, f, x, k) {
  function aux (n, x) {
    if (n === 0)
      return donek (k, x);
    else
      return bouncek (function (x) { return aux (n - 1, x); }, f (x));
  }
  return trampolinek (aux (n, x));
}

console.log('non-blocking line 1')
console.time('non-blocking JS1')
repeatk (1e8, function (x) { return x + 1; }, 0, function (result) {
  console.log('non-blocking line 3', result)
  console.timeEnd('non-blocking JS1')
})
console.log('non-blocking line 2')

// non-blocking line 1
// non-blocking line 2
// [ synchronous program stops here ]
// [ below this line, asynchronous program continues ]
// non-blocking line 3 100000000
// non-blocking JS1: 7762ms

Как заменить циклы while функциональной альтернативой программирования без оптимизации хвостового вызова?

3 ответа

Лучше loop/recur шаблон

Проблема с параметрами по умолчанию

Проблема с немаркированными союзами

Вывод

В Trampoline монада

Вывод

Лучше `loop`/`recur` шаблон

В `Trampoline` монада