# How to elegantly flatten a list

### Jason Yu Oct 4 '17

# 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:

`flatten([1, [3], [[6, 7], [[[]], 8]]]) => [1, 3, 6, 7, 8]`

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

In order to understand recursion one must understand recursion.

my favourite quote of all time!

Hi!

PHP do not have native functions for flatten.

Link below, my php functions:

gist.github.com/s3b4stian/0e2e638a...

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

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

`Array.isArray()`

(here)`reducer`

function.If I were going to define

`flatten`

with reduce, I would have written something like the following: