Функциональный подход RoundRobin - почему у моей функции есть побочные эффекты?

Question

Задача

Я пытаюсь создать алгоритм Round Robin ( https://en.wikipedia.org/wiki/Round-robin_scheduling) чисто функциональным способом.

Предполагается, что эта функция получила массив, подобный следующему:

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

И произвести следующий вывод:

[ 1, 3, 2, 4 ]

Код

Чтобы добиться этого, я решил рекурсивно реализовать циклический перебор следующим образом:

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

Здесь я чувствую массив результатов и заканчиваю, когда мне нечего добавить к нему. Можно использовать этот код следующим образом:

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

const result = roundRobin( array, [] );

проблема

В моем коде я использую reduce в моем arr параметр, чтобы убедиться, что я не изменяю оригинал. Однако, если я распечатаю массив до использования roundRobin и после, переменная изменится! Я как-то мутирую!

Вопросы:

1. Если я использую Reduce, который является чистым, как я изменяю свои параметры?
2. Есть ли другой чистый / функциональный способ реализации roundRobin?

Answer 1

1. Если я использую Reduce, который является чистым, как я изменяю свои параметры?

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

И за что это стоит, .reduce не является чистым, если пользовательская лямбда не является чистой

2. Есть ли другой чистый / функциональный способ реализации roundRobin?

Ага

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 ( [] ) )
// => []

Answer 2

Массив #shift выполняет мутацию.

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

Самый простой способ обойти это клонировать массив. Обычно это можно сделать с помощью Array#concat, но поскольку ваши массивы являются вложенными (хотя и простыми), вы можете сделать это:

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

Если вы обеспокоены тем, что глобальный JSON делает функцию нечистой, вы можете абстрагироваться от этого.

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

Answer 3

Простой способ сделать неизменяемый объект в JS - это использовать Object.freeze,

Я создал ваш входной массив как:

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

Затем, когда я попытался вызвать вашу функцию, я получил:

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

Вы используете shift, который является мутирующим оригинальным массивом.

Замени это Array.slice(0,1)[0] и это начнет работать.