Recursively flatten a list in Elixir

readme.md

You can run the tests with elixir flatten_test.exs:

$ elixir flatten_test.exs 

FlattenTest
  * test nested array 2 (0.00ms)
  * test empty array (0.00ms)
  * test nested array 3 (0.00ms)
  * test nested array 1 (0.00ms)
  * test one element (0.00ms)
  * test non-nested array (0.00ms)
  * test nested array 4 (0.00ms)


Finished in 0.04 seconds (0.04s on load, 0.00s on tests)
7 tests, 0 failures

Randomized with seed 969009

flatten.exs

defmodule Flatten do
  @doc """
  Flattens a list by recursively flattening the head and tail of the list
  """
  def flatten([head | tail]), do: flatten(head) ++ flatten(tail)
  def flatten([]), do: []
  def flatten(element), do: [element]
end

flatten_test.exs

Code.load_file("flatten.exs", __DIR__)

ExUnit.start
ExUnit.configure trace: true

defmodule FlattenTest do
  use ExUnit.Case

  test "empty array" do
    assert Flatten.flatten([]) == []
  end

  test "one element" do
    assert Flatten.flatten([1]) == [1]
  end

  test "non-nested array" do
    assert Flatten.flatten([1, 2, 3]) == [1, 2, 3]
  end

  test "nested array 1" do
    assert Flatten.flatten([[1, 2, [3]], 4]) == [1, 2, 3, 4]
  end

  test "nested array 2" do
    assert Flatten.flatten([[1], [2, [3]], [4, 5]]) == [1, 2, 3, 4, 5]
  end

  test "nested array 3" do
    assert Flatten.flatten([1, [2, [3, [4, [5]]]]]) == [1, 2, 3, 4, 5]
  end

  test "nested array 4" do
    assert Flatten.flatten([[[[[1], 2], 3], 4], 5]) == [1, 2, 3, 4, 5]
  end

end

While this works, it relies on the list concatenation operator ++, which is really slow, and relies on copying the entire list every time it is called.

A better approach would be to implement the flattening using the cons [head | tail] operator:

defmodule Util do
  @doc """
  Flattens nested lists

  ## Examples
    iex> Util.flatten_nested([1, [2, [3, 4], 5], 6])
    [1, 2, 3, 4, 5, 6]
  """
  def flatten_nested(list, acc \\ []),
    do: flatten_nested_rev(list, acc) |> Enum.reverse()

  @doc """
  Flattens nested lists, and returns a reversed list

  ## Examples
    iex> Util.flatten_nested_rev([1, [2, [3, 4], 5], 6])
    [6, 5, 4, 3, 2, 1]
  """
  def flatten_nested_rev(list, acc \\ [])

  def flatten_nested_rev([], acc) do
    acc
  end

  def flatten_nested_rev([list | rest], acc) when is_list(list) do
    flatten_nested_rev(rest, flatten_nested_rev(list, acc))
  end

  def flatten_nested_rev([element | rest], acc) do
    flatten_nested_rev(rest, [element | acc])
  end
end

The above may overflow the stack.
See tail recursion version that I wrote: https://gist.github.com/heri16/e726ee7f335d2ca61bbbb016e6b884e1