Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

RoundRobin functional approach - why does my function have side effects?

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?
like image 460
Flame_Phoenix Avatar asked Nov 15 '17 13:11

Flame_Phoenix


2 Answers

  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

  1. 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 ( [] ) )
// => []
like image 177
Mulan Avatar answered Sep 29 '22 14:09

Mulan


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), []);
like image 29
James Long Avatar answered Sep 29 '22 13:09

James Long