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

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

Я объясню, что я пробовал ниже, но TL;DR: Если у меня нет оптимизации хвостового вызова, каков функциональный способ реализации в цикле?

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

Создание функции "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 и убедиться, что я держу все в чистоте.

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

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

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

Ответ 1

Пример в 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

Ответ 2

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

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

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

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

Объект Encoded

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

Ответ 3

См. также unfold, который (из документов Ramda)

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

Ответ 4

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