small medium large xlarge

• (Harder) Write a function `flatten(list)` that takes a list that may contain any number of sublists, and those sublists may contain sublists, to any depth. It returns the elements of these lists as a flat list.

``````iex> MyList.flatten([ 1, [ 2, 3, [4] ], 5, [[[6]]]])
[1,2,3,4,5,6]
``````

Hint: You may have to use `Enum.reverse` to get your result in the correct order.

A Possible Solution</summary>

```# The simplest version is probably to use list concatenation. However,
# this version ends up rebuilding the list at each step
defmodule UsingConcat do
def flatten([]), do: []
def flatten([ head | tail ]), do: flatten(head) ++ flatten(tail)
end

# This version is more efficient, as it picks successive head values
# from a list, adding them to `result`. It is also tail recursive.
# The trick is that we have to unnest the head if the head itself is a
# list.

defmodule MyList do

def flatten(list), do: _flatten(list, [])

defp _flatten([], result), do: Enum.reverse(result)

# The following two function heads deal with the head
# being a list
defp _flatten([ [ h | [] ] | tail], result) do
_flatten([ h | tail], result)
end

defp _flatten([ [ h | t ] | tail], result) do
_flatten([ h, t | tail], result)
end

# Otherwise the head is not, and we can collect it
defp _flatten([ head | tail ], result) do
_flatten(tail, [ head | result ])
end

end

IO.inspect MyList.flatten([ 1, [ 2, 3, [4] ], 5, [[[6]]]])

# José Valim came up with a different implementation. It is interesting
# to spend some time with this, because it breaks down the problem
# a little differently. Rather that extract individual elements
# to built the result list, it treats the original list more like
# a tree, flattening subtrees on the right and merging the results
# into a tree that itself gets flattened. It is tider, and I prefer
# it to my solution.

defmodule JVList do
def flatten(list), do: do_flatten(list, [])

def do_flatten([h|t], tail) when is_list(h) do
do_flatten(h, do_flatten(t, tail))
end

def do_flatten([h|t], tail) do
[h|do_flatten(t, tail)]
end

def do_flatten([], tail) do
tail
end
end
```

</details>

Mine wound up close to José Valim’s:

``````def flatten(list), do: :lists.reverse(_flatten(list, []))

defp _flatten(_collection=[], acc), do: acc

end

defp _flatten([head|tail], acc) do
end
``````

Here’s mine. I don’t know if it’s any slower or faster.

``````module MyList do
def flatten([]), do: []
end
end
``````

Mine came out identical to Chris’ solution. It is interesting how the solution is similar to Jose’s but still approaches the list from left to right (requiring the reverse). Jose’s solution does a depth-first tree traversal to build the accumulator from right to left (not requiring a reverse). Jose’s approach is quite clever.

Here is my solution. It came out close to Dave’s this time:

``````defmodule MyList do
def flatten(list) do
_flatten(list, [])
end

defp _flatten([], result) do Enum.reverse(result) end
_flatten(head ++ tail, result)
end
defp _flatten([head|tail], result) do
end
end
``````

My solution came out being the same as José Valim’s: accumulate tree nodes in the order they are visited.

```defmodule MyList do
def flatten(list, acc \\ [])
def flatten([], acc), do: acc
def flatten([h|t], acc) when is_list(h), do: flatten(h, flatten(t, acc))
def flatten([h|t], acc), do: [h | flatten(t, acc)]
end
```
``````defmodule MyList do
def flatten(collection) do
Enum.reduce(collection, [], &(_flatten_build/2))
end

else
end
end

defp _flatten_build(element, acc) do
result = _flatten(element)
if is_list(result) do
acc ++ result
else
acc ++ [element]
end
end
end
``````
``````defmodule MyList do
def flatten([head | tail]) when is_list(head), do: flatten(head) ++ flatten(tail)
def flatten([head | tail]) when is_number(head), do: [head] ++ flatten(tail)
def flatten([]), do: []
end
``````

This approach doesn’t need an accumulator or reversal.

``````defmodule MyList do
def flatten(l),do:  _flatten(l,[])|> Enum.reverse
defp _flatten([],a),do: a
defp _flatten([h|t],a) when is_list(h), do: _flatten(t,_flatten(h,a))
defp _flatten([h|t],a), do: _flatten(t,[h|a])
end
``````

I struggled to achieve this solution. I think this solution eliminates the nested empty collections like the List.flatten function does.

```defmodule Enums do
def flatten(col) do
flatten_(col, [])
end
defp flatten_([], acc), do: acc
defp flatten_([head = [_h|_t]|tail], acc) do
flatten_(head, []) ++ flatten_(tail, acc)
end
defp flatten_([[]|tail], acc) do
flatten_(tail, acc)
end
defp flatten_([head|tail], acc) do
end
end
```

In Jose’s solution the following

``````  def do_flatten([h|t], tail) do
[h|do_flatten(t, tail)]
end
``````

can be optimized like this:

``````  def do_flatten(l, tail) do
[l|tail]
end
``````

because at this point `tail` is already flattened.

I believe the second solution offered up by Dave (reproduced here) has an error where it doesn’t flatten the head item if it’s a nested empty list.

So you get:

MyList.flatten([[], [], [[[[[[[[1]]]]]]]], [ 2, 3, [4] ], 5, [[[6]]]])

[[], [], 1, 2, 3, 4, 5, 6]

Here’s the original code.

``````defmodule MyList do

def flatten(list), do: _flatten(list, [])

defp _flatten([], result), do: Enum.reverse(result)

# The following two function heads deal with the head
# being a list
defp _flatten([ [ h | [] ] | tail], result) do
_flatten([ h | tail], result)
end

defp _flatten([ [ h | t ] | tail], result) do
_flatten([ h, t | tail], result)
end

# Otherwise the head is not, and we can collect it
defp _flatten([ head | tail ], result) do
_flatten(tail, [ head | result ])
end

end
``````

Here’s my stab at a version that addresses the bug:

``````
def flatten(nested_lists), do: reverse(_flatten(nested_lists, []))

defp _flatten([], acc), do: acc
defp _flatten([[]|tail], acc), do: _flatten(tail, acc)
defp _flatten([[head|tail]|outer_tail], acc), do: _flatten([head, tail | outer_tail], acc)

``````
I originally used ++ to join tail and outer_tail in the 3rd _flatten function, which I felt was inefficient. On comparing with Dave’s solution, I much preferred his use of [h, t tail] :-)

Not the meaning of the exercise to solve it this way maybe but:

``````defmodule MyList do
def flatten(list) do
to_char_list RegEx.replace(~r{[\[\]]}, to_string(list), "")
end
end

IO.inspectMyList.flatten([1, 2, [[[5, 9]], [3]]])
``````

Here’s mine:

```def MyList
def flatten([]), do: []
def flatten([h|t]) when is_list(h), do: flatten(h) ++ flatten(t)
def flatten([h|t]), do: [h] ++ flatten(t)
end
```

I don’t understand why José’s solution needed to have helper functions. Can anybody enlighten me? Maybe I’m missing something important.

Alex: Probably old habits of functional programmers die hard! ;)

Here is mine (meaning basically Jose’s):

``````
def flatten_2(list), do: _flatten_2(list, []) |> Enum.reverse
defp _flatten_2([], result), do: result
defp _flatten_2([head|tail], result), do: _flatten_2(tail, _flatten_2(head, result))
defp _flatten_2(item, result), do: [item | result]

``````

Do you know why we need a guard? Here was my thinking:

Ok, we are going to do this recursively with an accumulator. (Functional programming “standard”.)

So, the 1st function clause is obvious.

Now, lets do the normal head/tail thing and .. wait! If the 2nd clause succeeds then whatever it was sent must be a list, so the 3rd clause can just take the item/element – assumed to be a not-list – and add it to the list! Cool!

So, back to the 2nd clause, we call recursively with the tail (again, functional programming “standard” …) and the accumulator is .. a recursive call with the head!

That makes sense.

Can anyone explain this comment?

```# The simplest version is probably to use list concatenation. However,
# this version ends up rebuilding the list at each step
```

I don’t understand why it rebuilds the list each step (compared to other solutions)

Thanks

EDIT:
After looking around I think I know how to explain it.

```# this creates a new list with head that links to the list
# returned in the call
[ head | recursive_call(tail) ]

# this creates a completely new list and copies all items,
# returned from the function, to it
```

The main reason is that to append an element to the end of a list would change it but not if it’s added to the beginning.
Here’s a simple example:

```list1 = [2, 3]
# list 1 'points' to the element with value 2

list2 = [1 | list1]
# list 2 'points' to the element with value 1 but list 1
# still starts at 2

[    1,     2, 3]
#    ^      ^
#  list2   list1

# if instead we do
list3 = list2 ++ [4]

# we should end up with 2 lists:
[    1,     2, 3]
#    ^      ^
#  list2   list1

[    1, 2, 3, 4 ]
#    ^
#  list3
```

and here’s a simple way to measure the difference (a lot!):

```defmodule Benchmark do

def measure(function) do
function |> :timer.tc |> elem(0) |> Kernel./(1000000)
end

end

defmodule TestPerformance do

def upto_reverse(n), do: _upto_reverse(n) |> Enum.reverse
defp _upto_reverse(0), do: []
defp _upto_reverse(n), do: [n | _upto_reverse(n - 1)]

def upto(0), do: []
def upto(n), do: upto(n - 1) ++ [n]

end

Benchmark.measure(fn -> TestPerformance.upto_reverse(100000) end) # fast
Benchmark.measure(fn -> TestPerformance.upto(100000) end) # sloooooow
```
``````def flatten(l) when is_list(l) do _flatten(l, []) |> Enum.reverse end
defp _flatten([], c) do c end
defp _flatten([h|t], c) when is_list(h) do _flatten(t, _flatten(h, c)) end
defp _flatten([h|t], c) do _flatten(t, [h|c]) end
``````

My solution, don’t know if it’s faster or slower.

``````def flatten([]), do: []

def flatten([head | tail]) do
else
[ head ] ++ flatten(tail)
end
end
``````

Many thanks to Diogo Neves for explaining the performance hit on list append.

My first solution looked like Quentin Crain’s solution, but I realized that you can get rid of the Enum#reverse if you call the ‘inner’ recursion with tail instead of head:

``````  def flatten(list) when is_list(list), do: do_flatten(list, [])
defp do_flatten([], acc), do: acc
defp do_flatten([h | t], acc), do: do_flatten(h, do_flatten(t, acc))
defp do_flatten(elem, acc), do: [elem | acc]
``````

My solution

```# This is an exercise to implement the List.flatten function.

# 1st version: it doesn't work, because I use an old function in a guard clause. I may fix this bug with some macro later.

defmodule MyList do
def exist_list([]), do: false
def exist_list([ head | tail ]) do
true
else
exist_list(tail)
end
end

def flatten(list) when exist_list(list) == false, do: list
def flatten([ head | tail ]) do
else
[ head | flatten(tail) ]
end
end
end

# 2nd version: it is simpler and it works fine.
defmodule MyList do
def flatten([]), do: []
def flatten([ head | tail ]) do
else
[ head | flatten(tail) ]
end
end
end
```

I attempted with the same philosophy as JValim above, but I didn’t realize how to carry the remainder tail over. Looking at solution above, I am like “duh”

Here was my original:

``````  def flatten([]), do: []
def flatten([elem | tail]) when is_list(elem) == false, do: [elem | flatten(tail)]
``````

A solution that is partially tail recursion, and without `++` (which could be slow).

``````defmodule MyList do
def flatten([]), do: []

def flatten([[] | rest]) do
flatten(rest)
end

def flatten([[head | tail] | rest]) do
flatten([head | [tail | rest]])
end

def flatten([head | rest]) do
end
end
``````

My solution:

``````def flatten([]), do: []

def flatten([_ | _] = list), do: _flatten(list, [])

defp _flatten([], flattened_list), do: flattened_list

defp _flatten([head | tail], flattened_list) do
end

defp _flatten(x, flattened_list), do: [ x | flattened_list ]
``````
``````defmodule Enumy do

def flatinu([]), do: []
def flatinu([head | tail]) when (is_list(head) == true ) do