Objective

I am trying to create a Round Robin algorithm ( ) in a pure functional way.

This function, is supposed to received an array like the following:

[
    [ 1, 2 ],
    [ 3, 4 ]
]

And produce the following output:

[ 1, 3, 2, 4 ]

Code

To achieve this, I decided to implement round robin recursively like the following:

const roundRobin = (arr, results) => {
    if (arr.length === 0) return results;

    const newResults = arr.reduce((acc, current) => {

        if (current.length > 0) {
            acc.results.push(current.shift());
            acc.arr.push(current);
        }
        return acc;

    }, { arr: [], results });

    return roundRobin(newResults.arr, newResults.results);
};

Here, I feel up an array of results, and I finish when I have nothing left to add to it. One would use this code like the following:

const array =     [
        [ 1, 2 ],
        [ 3, 4 ]
    ];

const result = roundRobin( array, [] );

Problem

In my code I am using reduce in my arr parameter to ensure I don't modify the original. However, if I print array before using roundRobin and after, the variable is changed ! I mutate it somehow!

Questions:

1. If I am using reduce, which is pure, how am I mutating my parameters?
2. Is there another pure/functional way of implementing roundRobin?

Objective

I am trying to create a Round Robin algorithm ( https://en.wikipedia.org/wiki/Round-robin_scheduling ) in a pure functional way.

This function, is supposed to received an array like the following:

[
    [ 1, 2 ],
    [ 3, 4 ]
]

And produce the following output:

[ 1, 3, 2, 4 ]

Code

To achieve this, I decided to implement round robin recursively like the following:

const roundRobin = (arr, results) => {
    if (arr.length === 0) return results;

    const newResults = arr.reduce((acc, current) => {

        if (current.length > 0) {
            acc.results.push(current.shift());
            acc.arr.push(current);
        }
        return acc;

    }, { arr: [], results });

    return roundRobin(newResults.arr, newResults.results);
};

Here, I feel up an array of results, and I finish when I have nothing left to add to it. One would use this code like the following:

const array =     [
        [ 1, 2 ],
        [ 3, 4 ]
    ];

const result = roundRobin( array, [] );

Problem

In my code I am using reduce in my arr parameter to ensure I don't modify the original. However, if I print array before using roundRobin and after, the variable is changed ! I mutate it somehow!

Questions:

1. If I am using reduce, which is pure, how am I mutating my parameters?
2. Is there another pure/functional way of implementing roundRobin?

• javascript
• functional-programming

• 2 shift() does mutate the inner arrays – Bergi Commented Nov 15, 2017 at 13:31
• I don't get your input format. Can you explain what the array of arrays means? – Bergi Commented Nov 15, 2017 at 13:32
• Is the tail recursion (with an output parameter result that gets mutated) on purpose? – Bergi Commented Nov 15, 2017 at 13:34

3 Answers 3

1. If I am using reduce, which is pure, how am I mutating my parameters?

Function parameters can't really be mutated; a strange thought – but I'm sure you meant the arguments supplied to your function are being mutated. And yeah, that's with .shift as others pointed out

And for what it's worth, .reduce isn't pure unless the user-supplied lambda is pure

2. Is there another pure/functional way of implementing roundRobin?

Yep

const isEmpty = xs =>
  xs.length === 0
  
const head = ( [ x , ...xs ] ) =>
  x
  
const tail = ( [ x , ...xs ] ) =>
  xs

const append = ( xs , x ) =>
  xs.concat ( [ x ] )
  
const roundRobin = ( [ x , ...xs ] , acc = [] ) =>
  x === undefined
    ? acc
    : isEmpty ( x )
      ? roundRobin ( xs , acc )
      : roundRobin ( append ( xs , tail ( x ) )
                   , append ( acc , head ( x ) )
                   )

const data =
  [ [ 1 , 4 , 7 , 9 ]
  , [ 2 , 5 ]
  , [ 3 , 6 , 8 , 10 , 11 , 12 ]
  ]
                   
console.log ( roundRobin ( data ) )
// => [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ]

console.log ( roundRobin ( [ [ 1 , 2 , 3 ] ] ) )
// => [ 1 , 2 , 3 ]

console.log ( roundRobin ( [] ) )
// => []

Array#shift is doing the mutating.

var array = [0, 1, 2, 3, 4];
array.shift(); // -> 0
array; // -> [1, 2, 3, 4];

The easiest way around that is to clone the array. Usually that can be done with Array#concat but since your arrays are nested (though simple) you can do this:

const roundRobin = (arr, results) => {
    arr = JSON.parse(JSON.stringify(arr));
    if (arr.length === 0) return results;
    // ...

If you're concerned that the global JSON makes the function impure, you can abstract that out.

const deepClone = (obj) => JSON.parse(JSON.stringify(obj));
roundRobin(deepClone(array), []);

Easy way to make immutable object in JS is to use Object.freeze.

I created your input array as:

const array1 = Object.freeze([
    Object.freeze([ 1, 2 ]),
    Object.freeze([ 3, 4 ])
])

Then, when I tried to call your function I got:

Uncaught TypeError: Cannot add/remove sealed array elements
at Array.shift (<anonymous>)
at arr.reduce (<anonymous>:7:38)
at Array.reduce (<anonymous>)
at roundRobin (<anonymous>:4:28)
at <anonymous>:6:17

You're using shift, which is mutating orignal array.

Replace it with Array.slice(0,1)[0] and it will start working.