16 Jul 2013, 02:16
Dave_gnome_head_isolated_pragsmall

Dave Thomas (338 posts)

  • (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
# 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)
  def flatten(head), do: [ head ]
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
18 Dec 2013, 18:58
Generic-user-small

Chris Doggett (3 posts)

Mine wound up close to José Valim’s:

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

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

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

defp _flatten([head|tail], acc) do
    _flatten(tail, [head|acc])
end
13 Aug 2014, 04:24
Generic-user-small

Michael Bishop (2 posts)

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

module MyList do
  def flatten([]), do: []
  def flatten([head|tail]) when is_list(head) do
    flatten(head ++ tail)
  end
  def flatten([head|tail]), do: [head|flatten(tail)]
end
24 Sep 2014, 23:07
Nathan-6kites_pragsmall

Nathan Feaver (8 posts)

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.

12 Nov 2014, 02:45
Generic-user-small

Elliot Finley (11 posts)

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
  defp _flatten([head|tail], result) when is_list(head) do
    _flatten(head ++ tail, result)
  end
  defp _flatten([head|tail], result) do
    _flatten(tail, [head|result])
  end
end
05 Dec 2014, 21:15
9863_pragsmall

Suraj Kurapati (15 posts)

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
28 Dec 2014, 02:03
Generic-user-small

Pierre Sugar (55 posts)

defmodule MyList do
  def flatten(collection) do
    Enum.reduce(collection, [], &(_flatten_build/2))
  end

  defp _flatten([head|tail]) do
    if is_list(head) do
      _flatten(head)
    else
      [head|_flatten(tail)]
    end
  end
  defp _flatten(head), do: head

  defp _flatten_build(element, acc) do
    result = _flatten(element)
    if is_list(result) do
      acc ++ result
    else
      acc ++ [element]
    end
  end
end
15 Feb 2015, 03:29
Bach_sunglasses_pragsmall

Josh Smith (2 posts)

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.

  You must be logged in to comment