Functional Programming style growing array loop

Question

What is the smartest way to iterate over an array that grows during iteration in javascript? I want to iterate over all added elemets, even elements added during iterations. I'd like do to it in functional programming style.

For example see this code

let a = [
	'x',
  'y'
]

let limit = 4  // limit the test

for (let i=0; i<a.length; i++) {
	console.log(a[i])
    limit--
    if(limit>0){
      a.push(a[i]+'-') 
    }
}

console.log(a)

After execution got

[
  "x",
  "y",
  "x-",
  "y-",
  "x--"
]

But if I try with an alternative "funcional" mode like forEach the new added elements are not printed

let a = [
	'x',
  'y'
]

let limit = 4  // limit the test

a.forEach( (e) => {
    console.log(e)
    limit--
    if(limit>0){
      a.push(e+'-') 
    }
})

console.log(a)

Answer 1

As Rubens rightfully noticed, functional way assumes that your functions do not mutate source data, but rather transform it and return new values.

In the following example source array is kept untouched and transform iterates through it by calling itself recursively and passing updated arguments:

function transform(array, limit, acc = []) {
    if (limit === 0 || array.length === 0) {
        return acc;
    }

    const head = array[0];
    const tail = array.slice(1);
    return transform(tail.concat(head + "-"), limit - 1, acc.concat(head));
}

transform(["x", "y"], 5).forEach(x => console.log(x))

Resulting array is limited by the limit argument, limit = 5 means that only 5 elements will end up in the result.

If we look at the arguments that are passed to the transform function on each iteration, we would see that limit gets smaller while acc (short for accumulator) receives new elements:

transform(["x",   "y"],    5, [])
transform(["y",   "x-"],   4, ["x"])
transform(["x-",  "y-"],   3, ["x", "y"])
transform(["y-",  "x--"],  2, ["x", "y", "x-"])
transform(["x--", "y--"],  1, ["x", "y", "x-", "y-"])
transform(["y--", "x---"], 0, ["x", "y", "x-", "y-", "x--"])

When limit reaches zero, acc value is returned as a result. Note that no data gets mutated.

It worth mentioning that transform call is in a tail position and since ES6 optimizes tail calls (in strict mode), we don't have to worry about growing call stack.

Note also that the code above only illustrates the idea. It should be used with care as it might be very slow on large amounts of data because of sliceing and concating arrays on each iteration.

Update on tail call optimization: even though tail call optimization is a part of the ES6 specification, it is not widely supported by browsers, so you need to be cautious when using recursion. See compatibility table.

Answer 2

In a functional way, the best approach to do this is using Observables (reactive programing). This array can be turned into a "producer" (Observable) that emit values whenever this collection grows, so you can safely do whatever you want even if this collection is growing over the time. Maybe this is "over engineering" for just "log" some values, but depending on your real problem, it can be a good solution.

You can have a look on the docs here.

But if you look to your code, in functional programing, you're not going to change the current array (using the reference), but instead, create a entire new array. In functional programing the variables tends to being "read only", following the "immutability" concept. JS doesn't have natively yet, you can use libs for that tough. Anyway, I've made this code as an example of that:

function dashAccumulator(arr, times) {
  if(times) {
    const dashed = arr.map(val => `${val}-`);
    return [...arr, ...dashAccumulator(dashed, --times)];
  }
  else return arr;
}

const a = ['x', 'y'];
const iter = 4;
console.log(dashAccumulator(a, iter));

The map will create a new array and also, when returning, I'm creating another one based on the values of the map result and the "original" array in that context. This way you doesn't need to change any references and keep the same final result.

Answer 3

Using a generic loop and recur interface, we write stack-safe loops expressed in a functional style -

const recur = (...values) =>
  ({ recur, values })

const loop = f =>
{ let r = f ()
  while (r && r.recur === recur)
    r = f (...r.values)
  return r
}

const main = (limit = 10) =>
  loop                    // begin a loop with vars
    ( ( r = [ 'x', 'y' ]  // initial result
      , i = 0             // initial index
      ) =>
        i >= limit           // exit condition
          ? r .slice (0, i)  // return result
          : recur            // otherwise recur
              ( [ ...r, r[i] + '-' ]  // next result
              , i + 1                 // next index
              )
    )

console .log (main (10))
// ["x","y","x-","y-","x--","y--","x---","y---","x----","y----"]

We could easily make [ 'x', 'y' ] an input of the program, too -

const main = (init = [], limit = 10) =>
  loop
    ( ( r = [...init]    // <-- initial result
      , i = 0
      ) =>
        i >= limit
          ? r .slice (0, i)
          : recur
              ( [ ...r, r[i] + '-' ]
              , i + 1
              )
    )

main ([ 'a', 'b', 'c' ], 10)
// ["a","b","c","a-","b-","c-","a--","b--","c--","a---"]

Above, we used an index, i = 0, to perform lookups, r[i], while the loop is running, but this is just one way to solve the problem. To see loop and recur build up an array differently, we'll see them used in another scenario.

Let's imagine a game where you roll an N-sided die and the result, M, is less than N. If M is 0, gameover, otherwise record your roll and repeat the game with an M-sided die -

const rand = max =>
  Math .floor (Math .random () * max)

const play = (init = 0) =>
  loop                     // begin a loop with vars
    ( ( r = []             // initial result
      , max = init         // initial max
      , roll = rand (init) // initial roll
      ) =>
        roll === 0              // gameover condition
          ? [ ...r, roll ]      // return result
          : recur               // otherwise recur
              ( [ ...r, roll ]  // next result
              , roll            // next max
              , rand (roll)     // next roll
              )
    )

console .log (JSON .stringify (play (1000)))
// [688,416,215,12,5,1,0]

In this particular program, our mind is freed from thinking about array indexes or incrementing them. Above, we don't read from the result, r, as we build it. Instead we use another loop parameter, max, to encode the current roll limit. loop and recur are sufficiently generic to express a wide-variety of functional programs.

---

In both programs, spread arguments like [ ...r, r[i] + '-' ] or [ ...r, roll ] copy the result, r, in each step. Since r is initialised with a new array at the beginning of the loop, r = [...], we can use a mutating operation, Array.prototype.push, without risk of leaking a side-effect. This reduces runtime and memory footprint by a significant amount -

const push = (xs, x) =>
  ( xs .push (x) // <-- perform side-effect
  , xs           // <-- return value
  )

const play = (init = 0) =>
  loop
    ( ( r = []             // <-- new array
      , max = init
      , roll = rand (init)
      ) =>
        roll === 0
          ? push (r, roll)      // <-- mutate
          : recur
              ( push (r, roll)  // <-- mutate
              , roll
              , rand (roll)
              )
    )

Expand the snippet below to play the game with N = 1000 -

const recur = (...values) =>
  ({ recur, values })

const loop = f =>
{ let r = f ()
  while (r && r.recur === recur)
    r = f (...r.values)
  return r
}

const rand = max =>
  Math .floor (Math .random () * max)

const push = (xs, x) =>
  ( xs .push (x)
  , xs
  )

const play = (init = 0) =>
  loop
    ( ( r = []
      , max = init
      , roll = rand (init)
      ) =>
        roll === 0
          ? push (r, roll)
          : recur
              ( push (r, roll)
              , roll
              , rand (roll)
              )
    )

console .log (JSON .stringify (play (1000)))
// [688,416,215,12,5,1,0]