Today I Learned

Playing with Lists and Recursion in Elixir - Flatten a list exercise

While reading Dave Thomas's book, Programming Elixir, I stumbled upon an exercise.

You're supposed to write a flatten(list) function that takes a list as a parameter. That list may contain any number of sublists, which themselves may contain sublists, no matter how deep. Your function should return all the elements of these lists in a single flattened list, all the while preserving the order of the elements.

In the beginning, it sounded a bit hard (especially since he mentioned in the book that the exercise it's hard), but after enough playing with the idea, I got to a fairly simple solution, simpler than what I thought it would be and the solutions I've found so far on the internet.

The result should look something like this:

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

Now the function:

defmodule MyList do
  def flatten([]), do: []
  def flatten([head | tail]) when is_list(head) do
      flatten(flatten(head) ++ tail)
  def flatten([head | tail]), do: [head | flatten(tail)]

At first I thought it wouldn't work, but tested it and got surprised.

The flatten function takes care of 3 cases:

  • the given list is empty
  • the head of the list is in itself a list, in which case it should be flattened
  • the head is not a list, in which case we continue with flattening the tail