loading...

How to elegantly flatten a list

ycmjason profile image Jason Yu ・2 min read

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

Discussion

pic
Editor guide
Collapse
markotaponen profile image
Marko Taponen

In order to understand recursion one must understand recursion.

Collapse
ycmjason profile image
Jason Yu Author

my favourite quote of all time!

Collapse
sebastianr1982 profile image
Sebastian Rapetti

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

Collapse
maroun_baydoun profile image
Maroun Baydoun

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

Collapse
ycmjason profile image
Jason Yu Author

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])], []);
}