How to elegantly flatten a list

YCM Jason - Oct 4 '17 - - Dev Community

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))];
}
Enter fullscreen mode Exit fullscreen mode

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))];
}
Enter fullscreen mode Exit fullscreen mode
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Terabox Video Player