How do I replace while loops with a functional pro

Question

I am experimenting with a more functional style in my JavaScript; therefore, I have replaced for loops with utility functions such as map and reduce. However, I have not found a functional replacement for while loops since tail call optimization is generally not available for JavaScript. (From what I understand ES6 prevents tail calls from overflowing the stack but does not optimize their performance.)

I explain what I have tried below, but the TLDR is: If I don't have tail call optimization, what is the functional way to implement while loops?

What I have tried:

Creating a "while" utility function:

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

Since tail call optimization isn't available I could rewrite this as:

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

However at this point it feels like I have made my code more complicated/confusing for anyone else who uses it, since I have to lug around a custom utility function. The only practical advantage that I see is that it forces me to make the loop pure; but it seems like it would be more straightforward to just use a regular while loop and make sure that I keep everything pure.

I also tried to figure out a way to create a generator function that mimics the effects of recursion/looping and then iterate over it using a utility function like find or reduce. However, I haven't figured out an readable way to do that yet.

Finally, replacing for loops with utility functions makes it more apparent what I am trying to accomplish (e.g. do a thing to each element, check if each element passes a test, etc.). However, it seems to me that a while loop already expresses what I am trying to accomplish (e.g. iterate until we find a prime number, iterate until the answer is sufficiently optimized, etc.).

So after all this, my overall question is: If I need a while loop, I am programming in a functional style, and I don't have access to tail call optimization, then what is the best strategy.

Answer 1

I've been thinking about this question a lot. Recently I came across the need for a functional while loop.

It seems to me like the only thing this question really wants is a way to inline a while loop. There IS a way to do that using a closure.

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

Alternatively, if what you want is something that chains off an array, than you can use the reduce method.

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

None of this actually turns our while loop at its core into a function. But it does allow us the use of an inline loop. And I just wanted to share this with anyone who this might help.

Answer 2

Programming in the sense of the functional paradigm means that we are guided by types to express our algorithms.

To transform a tail recursive function into a stack-safe version we have to consider two cases:

• base case
• recursive case

We have to make a choice and this goes well with tagged unions. However, Javascript doesn't have such a data type so either we have to create one or fall back to Object encodings.

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

Function Encoded

Alternatively, we can create a real tagged union with a function encoding. Now our style is much closer to mature functional languages:

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

Answer 3

An example in JavaScript

Here's an example using JavaScript. Currently, most browsers do not support tail call optimisation and therefore the following snippet will fail

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

---

Trampolines

We can work around this limitation by changing the way we write repeat, but only slightly. Instead of returning a value directly or immediately recurring, we will return one of our two trampoline types, Bounce or Done. Then we will use our trampoline function to handle the loop.

// 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

Currying slows things down a little bit too, but we can remedy that using an auxiliary function for the recursion. This is nice too because it hides the trampoline implementation detail and does not expect the caller to bounce the return value. This runs about twice as fast as the above 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-style loop/recur

Trampolines are nice and all but it's kind of annoying to have to have to worry about calling trampoline on your function's return value. We saw the alternative was to use an auxiliary helper, but c'mon that's kind of annoying, too. I'm sure some of you aren't too keen about the Bounce and Done wrappers, too.

Clojure creates a specialised trampoline interface that uses a pair of functions, loop and recur – this tandem pair lends itself to a remarkably elegant expression of a program

Oh and it's really fast, too

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

The continuation monad

This is one of my favourite topics tho, so we're gonna see what this looks like with the Continuation monad. We'll also go one step further and hide the trampoline implementation detail inside of our repeat function using an auxiliary function (aux) so that the caller doesn't have to worry about bouncing the return value each time

// 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 combinator

The Y combinator is my spirit combinator; this answer would be incomplete without giving it some place amongst the other techniques. Most implementations of the Y combinator however, are not stack-safe and will overflow if the user-supplied function recurs too many times. Since this answer is all about preserving stack-safe behaviour, of course we'll implement Y in a safe way – again, relying on our trusty trampoline.

Y demonstrates the ability to extend easy-to-use, stack-safe, synchronous infinite recursion without cluttering up your function.

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

---

Practicality with while loop

But let's be honest: that's a lot of ceremony when we're overlooking one of the more obvious potential solutions: use a for or while loop, but hide it behind a functional interface

For all intents and purposes, this repeat function works identically to the ones provided above – except this one is about one or two gadzillion times faster (with exception to the loop/recur solution). Heck, it's arguably a lot easier to read too.

Granted, this function is perhaps a contrived example – not all recursive functions can be converted to a for or while loop so easily, but in such a scenario where it's possible, it's probably best to just do it like this. Save the trampolines and continuations for heavy lifting when a simple loop won't do.

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 is NOT a solution to the stack overflow problem

OK, so it does work, but only paradoxically. If your dataset is small, you don't need setTimeout because there will be no stack overflow. If your dataset is large and you use setTimeout as a safe recursion mechanism, not only do you make it impossible to synchronously return a value from your function, it will be so F slow you won't even want to use your function

Some people have found an interview Q&A prep site that encourages this dreadful strategy

What our repeat would look like using setTimeout – notice it's also defined in continuation passing style – ie, we must call repeat with a callback (k) to get the final value

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

I can't stress enough how bad this is. Even 1e5 takes so long to run that I gave up trying to measure it. I'm not including this in the benchmarks below because it's just too slow to even be considered a viable approach.

---

Promises

Promises have the ability to chain computations and are stack safe. However, achieving a stack-safe repeat using Promises means we'll have to give up our synchronous return value, the same way we did using setTimeout. I'm providing this as a "solution" because it does solve the problem, unlike setTimeout, but in a way that's very simple compared to the trampoline or continuation monad. As you might imagine though, the performance is somewhat bad, but nowhere near as bad as the setTimeout example above

Worth noting in this solution, the Promise implementation detail is completely hidden from the caller. A single continuation is provided as a 4th argument and its called when the computation is complete.

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))

---

Benchmarks

Seriously, the while loop is a lot faster - like almost 100x faster (when comparing best to worst – but not including async answers: setTimeout and 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

---

Stone Age JavaScript

The above techniques are demonstrated using newer ES6 syntaxes, but you could implement a trampoline in the earliest possible version of JavaScript – it only requires while and first class functions

Below, we use stone age javascript to demonstrate infinite recursion is possible and performant without necessarily sacrificing a synchronous return value – 100,000,000 recursions in under 6 seconds - this is a dramatic difference compared to setTimeout which can only 1,000 recursions in the same amount of time.

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

Non-blocking infinite recursion using stone age JavaScript

If, for some reason, you want non-blocking (asynchronous) infinite recursion, we can rely on setTimeout to defer a single frame at the start of the computation. This program also uses stone age javascript and computes 100,000,000 recursions in under 8 seconds, but this time in a non-blocking way.

This demonstrates that there's nothing special about having a non-blocking requirement. A while loop and first-class functions are still the only fundamental requirement to achieve stack-safe recursion without sacrificing performance

In a modern program, given Promises, we would substitute the setTimeout call for a single Promise.

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

Answer 4

See also unfold which (from Ramda docs)

Builds a list from a seed value. Accepts an iterator function, which returns either false to stop iteration or an array of length 2 containing the value to add to the resulting list and the seed to be used in the next call to the iterator function.

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>