How to elegantly flatten a list

The problem

Given any list xs, where xs could contain other lists or any non-list values, we wish to extract all the values in xs. For example:

1. flatten([1, [3], [[6, 7], [[[]], 8]]]) => [1, 3, 6, 7, 8]
2. flatten([{a: 3}, 1, [[''], 2]]) => [{a: 3}, 1, '', 2]

Recursive solution

When we wish to derive a recursive solution, we must avoid thinking recursively. Never trace your code into the recursive calls! The correct approach is to assume that the function you want to define is already working on a smaller structure of the input, which in this case the smaller structure is obviously the tail of xs, i.e. xs.slice(1). This assumption is called the leap of faith.

So now if flatten(xs.slice(1)) will work correctly, how could we use this to construct the full correct answer of flatten(xs)? Now obviously we are missing xs[0]. xs[0] could either be a non-list element or another list.

If xs[0] is a non-list element, we simply add back xs[0] to the first place of flatten(xs.slice(1)), then we are done!

If xs[0] is another list, we take a leap of faith and recursively call flatten(xs[0]). Then we can concat flatten(xs[0]) to flatten(xs.slice(1)).

function flatten(xs){
  if(Array.isArray(xs[0])) return [...flatten(xs[0]), ...flatten(xs.slice(1))];
  else return [xs[0], ...flatten(xs.slice(1))];
}

Now what we miss is a base case. The smallest list that we can flatten must be [], and the answer is obviously [].

So the final code is

function flatten(xs){
  if(xs.length === 0) return [];

  if(Array.isArray(xs[0])) return [...flatten(xs[0]), ...flatten(xs.slice(1))];
  else return [xs[0], ...flatten(xs.slice(1))];
}

Comments

[Marko Taponen]

In order to understand recursion one must understand recursion.

[YCM Jason]

my favourite quote of all time!

[Sebastian Rapetti]

Hi!
PHP do not have native functions for flatten.
Link below, my php functions:
gist.github.com/s3b4stian/0e2e638a...

[Maroun Baydoun]

What do you think about my solution? Flatten an array in JavaScript

[YCM Jason]

It is interesting! There are a few points about your solution:

1. checking array should be done with Array.isArray() (here)
2. I think it would be better if you take the base case outside your reducer function.

If I were going to define flatten with reduce, I would have written something like the following:

function flatten(xs){
  if(xs.length === 0) return [];
  return xs.reduce((acc, x) => [...acc, ...(Array.isArray(x)? flatten(x):
 [x])], []);
}