Функция, преобразующая вложенный массив в однородный список

Условие

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

Пример:

flatten([1, [2, [3, 4]], 5]); // => [1, 2, 3, 4, 5]

Функция должна работать с любыми типами данных, содержащимися в массиве, и не изменять исходный массив.

Ответ

Обходите вложенные массивы слева направо, помещая только не-массивы в результат. Итеративный стек позволяет не зависеть от глубины стека рекурсии.

function flatten(input) {
  if (!Array.isArray(input)) throw new TypeError('Expected array');
  const result = [];
  const stack = [{ array: input, index: 0 }];
  const active = new Set([input]);
  while (stack.length) {
    const frame = stack[stack.length - 1];
    if (frame.index >= frame.array.length) {
      active.delete(frame.array);
      stack.pop();
      continue;
    }
    const value = frame.array[frame.index++];
    if (Array.isArray(value)) {
      if (active.has(value)) throw new TypeError('Cyclic array');
      active.add(value);
      stack.push({ array: value, index: 0 });
    } else result.push(value);
  }
  return result;
}

Исходные массивы не меняются; объекты сохраняются как ссылки, без глубокого копирования. Пустоты sparse-массива здесь превращаются в undefined. Время пропорционально числу посещённых элементов, вспомогательная память — глубине вложенности, кроме результата.