Given an arbitrarily and deeply nested List of Integers, this code snippet will recursively "flatten" the found Integers into a single List.

readme.mdown

RFlatten

Overview

Objective

Flatten a list (i.e., array) of arbitrarily nested dimensions (e.g., depth, length) of Integers into a single list containing all found Integers.

Limitations

For the purposes of this example, the solution will only sort Integer elements and will provide a warning when other elements are passed to the module.

Example Inputs

Given the following inputs:

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

We would expect the following result:

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

Note: For our purposes, empty lists are fully reduced, not translated to an equivalent nil value such as 0.

Solution

RFlatten in Elixir

The solution can be found in the r_flatten.exs file contained in this Gist. This file defines the main module, RFlatten, which will recursively handle inputs until the solution (i.e., a 1-depth list containing all Integers) has been achieved.

Tests

Tests are found in r_flatten_unit_tests.exs and can be run using the command:

elixir r_flatten_test.exs

Using Interactively

To pass an arbitrary list to the r_flatten use Elixir's interactive shell (i.e., iex):

iex r_flatten.exs

And then after the interactive shell loads:

RFlatten.call([1, [2], [3, 4, [5]], 6, []])
=> [1, 2, 3, 4, 5, 6]

r_flatten.exs

defmodule RFlatten do
  @moduledoc """
  RFlatten will take an list of Integers of an arbitrary length and depth of
  nesting and produce a single list containing only those Integers found.
  """

  @doc """
  The main recursion call allows for us to split the list into it's first
  element (i.e., head) and the remainder of the problem (i.e., tail). We then
  recurse through until we hit an element (i.e., call(element)) or the end of
  the list; in which tail will be an empty list passed to call([])
  See: http://bit.ly/2CbVSpC
  """
  def call([head | tail]), do: call(head) ++ call(tail)

  @doc """
  Base Case: Empty List
  Once the empty list is encountered, this will return and stop recursing.
  Note: Must be above the element base case or will just pass as the element.
  """
  def call([]), do: []

  @doc """
  Base Case: Element
  Given that the provided element is an Integer, we return the element singly
  nested so it can be concatenated in our main recursive call.
  Note: Removing the `when is_integer(element)` will flatten lists of any type.
  """
  def call(element) when is_integer(element), do: [element]
end

r_flatten_test.exs

# Load RFlatten directly as we are not using Mix to manage dependencies.
Code.load_file("r_flatten.exs")

# Setup ExUnit to manage our unit tests for RFlatten.
ExUnit.start()

# Developer Note:
# For the purpose of these tests, we use the word "nested" to refer to a list
# contained within another list (e.g., [n, [m]]). For multiple levels of nesting
# we will sometimes refer to a "depth" of the nested list/elements:
# * A list of depth 1 signifies it has a list within a list.
# * A list of depth 2 signifies it has a list within a list within a list.
# * A list of depth n signifies it has a list containing an n-1 depth list.
defmodule RFlattenTest do
  @moduledoc """
  Unit tests for RFlatten covering our "gold standard" (example in the README),
  a strong set of edge cases (various depth, length), and some unsupported use
  cases which will help other developers understand the limitations of RFlatten.
  """
  use ExUnit.Case

  # Our first test ensures that RFlatten works as we describe in the README.
  test "when flattening the documented example list" do
    assert RFlatten.call([1, [2], [3, 4, [5]], 6, []]) == [1, 2, 3, 4, 5, 6]
  end

  # Now, we move onto more base case examples (e.g., empty list, [1], []):
  test "with empty list (no Integers, no nested lists)" do
    assert RFlatten.call([]) == []
  end

  test "with list containing one Integer" do
    assert RFlatten.call([1]) == [1]
  end

  test "with list containing three Integers" do
    assert RFlatten.call([1, 2, 3]) == [1, 2, 3]
  end

  test "with list containing two Integers and a nested list (with Integer)" do
    assert RFlatten.call([1, 2, [3]]) == [1, 2, 3]
  end

  test "with list with four elements and a single- and double-nested lists"  do
    assert RFlatten.call([1, [2], [[3]]]) == [1, 2, 3]
  end

  # Some more complex examples:
  test "when given the input: [1, [2, [3, [4]]]]" do
    ex_list = [1, [2, [3, [4]]]]
    assert RFlatten.call(ex_list) == [1, 2, 3, 4]
  end

  test "when given the input: [[[[1], 2], 3, 4], 5]" do
    ex_list = [[[[1], 2], 3, 4], 5]
    assert RFlatten.call(ex_list) == [1, 2, 3, 4, 5]
  end

  test "when given the input: [[[[[[[]]]]]]]" do
    ex_list = [[[[[[[]]]]]]]
    assert RFlatten.call(ex_list) == []
  end

  # Finally, document some of the limitations of this system.
  # The current specification is only focused on Integers; and therefore we
  # show how RFlatten will handle strings, symbols, and other types.
  # Note: Could also be written as RFlatten.call("string") to hit base case.
  #
  # See: https://elixir-lang.org/getting-started/basic-types.html
  test "when containing a String, should raise a FunctionClauseError" do
    assert_raise FunctionClauseError, fn ->
      RFlatten.call(["Hello, world!"])
    end
  end

  test "when containing an Atom (Symbol), should raise a FunctionClauseError" do
    assert_raise FunctionClauseError, fn ->
      assert RFlatten.call([:x])
    end
  end

  test "when containing an Boolean, should raise a FunctionClauseError" do
    assert_raise FunctionClauseError, fn ->
      assert RFlatten.call([true])
    end
  end

  test "when containing a Tuple, should raise a FunctionClauseError" do
    assert_raise FunctionClauseError, fn ->
      assert RFlatten.call([{1}])
    end
  end

  test "when containing nil, should raise a FunctionClauseError" do
    assert_raise FunctionClauseError, fn ->
      assert RFlatten.call([nil])
    end
  end

  # However, it should handle Integers in hexadecimal correctly.
  test "when containing an Integer represented in hexadecimal notation" do
    # 31 represented in hexadecimal notation is 0x1F.
    assert RFlatten.call([0x1F]) == [0x1F]
    assert RFlatten.call([0x1F]) == [31]
  end

  # Many types
  test "when given a List containing an Integer, String, and Symbol." do
    assert_raise FunctionClauseError, fn ->
      assert RFlatten.call([1, "2", :three])
    end
  end
end