DEV Community

YCM Jason
YCM Jason

Posted on • Updated on

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

Top comments (5)

Collapse
 
markotaponen profile image
Marko Taponen

In order to understand recursion one must understand recursion.

Collapse
 
ycmjason profile image
YCM Jason

my favourite quote of all time!

Collapse
 
sebastianr1982 profile image
Sebastian Rapetti • Edited

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 • Edited

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

Collapse
 
ycmjason profile image
YCM Jason • Edited

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