Problems with recursion and cyclic infinity.
BTW the best solution is array.flat(10);
10 is recursion depth. See bottom of answer for details on the new Array
prototypes.
Call stack overflow
Your code is not protected from call stack overflow,
As amard's answer correctly pointed out recursion is dangerous as the call stack depth is unknowable from within javaScript, (and is a major flaw in the language until we get proper tail calls). Superbly elegant answer BTW +1 (surprised it does not have more up votes)
Unfortunately his answer does, flatten in place, all contained arrays which may have consequences elsewhere, nor does it protect against cyclic references.
Stack overflow from cyclic references
Example of a cyclic reference.
var a = [];
var b = [a];
a.push(b);
flatten(a); // will throw or call stack overflow or worse if
// a or b were large arrays crash the page with our of
// memory error.
Cyclic references must always be considered when using recursion or recursive like solutions to iterate over an unknown data set. There is no time or memory that can handle an infinite loop.
Cyclic safe solutions
- Do as
Array.prototype.flat
does and use a depth
argument to limit recursion depth
- Track flattened arrays using a
Set
- Use type coercion,
String.split
, Array.map
and Number
if items only number like or arrays.
The one liner
Array.toString
flattens an array to a string, items separated by a ,
comma. As coercion is automatic in JavaScript such transformations must be protected against cyclic references.
Method : First the array is converted to a string, you could use .toString
but can be forced via a sting contact operator +
. Then just split the new string at ","
to convert back to array, and if needed convert the array of strings back to numbers with map(Number)
const arr = [1,2,3,[1,2,[4,5],3,4],2];
arr.push([1,2,3,[arr]]); // create cyclic ref
// one liner flatten array of numbers (or number like items)
const flat = ("" + arr).split(",").map(Number);
Using a Set
to remember flatten items.
The following flattenSafe
uses Set
to track flattened arrays, also to reduce overall memory us by pushing to a single result array rather than create arrays each recursion to be return for addition to the previous iterations array.
Example snippet includes the above oneline method as well.
//==========================================================
// Cyclic data to test on
const a = [1,2,3,4,5,[6,[110,123]]];
// create an array the contains a reference to array a
const b = [[7,8,9],[10,12,13,14,[21,22,a]]];
// create a cyclic reference in a by push b.
a.push(b);
//==========================================================
// Test data cyclic using the most ugly way NOTE this is only
// situation and not a valid test, don't use it in production
// code.
try { JSON.stringify(a); log("failed") } catch(e) { log("Cyclic JSON.stringify Throws : " + e.message) }
//==========================================================
// flatten using toString
const flat = (""+a).split(",").map(Number);
//==========================================================
// recursive cyclic safe flatten
function flattenSafe(arr) {
if (Array.isArray(arr)) {
const usedArrays = new Set(); // Note dont add array here
usedArrays.add(arr); // mark incoming array as used
const resArr = [];
(function flatten(arr) {
for (const item of arr) {
if (Array.isArray(item)) {
if (! usedArrays.has(item) ) { // check this item has not been touched
usedArrays.add(item); // add to used Set
flatten(item);
}
} else {
resArr.push(item);
}
}
})(arr);
return resArr;
}
return arr;
}
const safeFlat = flattenSafe(a);
//==========================================================
// Show results
log("Flat using string " + flat.join("-"));
log("Flat flattenSafe " + safeFlat.join("="));
// Join flattens so you should use console to examine results
// On snippet console looks bad so I used above.
// console.log(flat);
// console.log(safeFlat);
function log(str) { document.body.innerHTML += str + "</br>" }
Avoid recursion using a stack.
You can also avoid recursion using a while loop and a stack to hold arrays and array indexes.
For each item push to flat array unless that item is an array,if so push to the current array and index to stack. Ref the new array as the current and reset index to 0 and iterate each item with same rules. Pop from stack when array index past end and continue until stack is empty, Use Set to test for cyclic arrays as in above example.
New to javascript, and after a long debate about the naming* we finally have Array.flat and Array.flatMap. The latter applies a transform function to each item that is flattened.
Used as
([1,2,[1,2]]).flat(); // default depth 1
([1,2,[1,2,[1,2]]]).flat(2); // depth 2
* Common libraries use of flatten
meant it would break the net and flat is not commonly used as a verb (Verb in music. C flat to lower by a semitone, or language, flat that surface) and for a while it looked like it may have been Array.smoosh
Warning on performance testing re - webNeat's answer
The tests results are off by 2 orders, should be around
- JSON method 5289ms.
- Loop method 23ms.
Always run the function several 100 or 1000 times before you start timing, so you don't test the time the optimizer is using.
Always use a global soak. Functions that do not effect external state*1 are simply not run, this is the most basic optimization the optimizer can do. (A soak has its state changed by an unknowable result of the test function.) A function that produces the same result independent of arguments will have the result cached. A function that produces the same result for the same input each time can have the result cached and thus falsifies performance tests)
*1 Note State used to mean browser state not just the JS context.
Order of execution can effect timing, randomize your tests and use a statistical mean to estimate the results of many tests.
NOTE do to an ongoing and unresolved security issue performance.now
can not be trusted to give anything above a 0.1-0.2ms accuracy.