small medium large xlarge

Dave_gnome_head_isolated_pragsmall
16 Jul 2013, 02:16
Dave Thomas (344 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</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)
  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

</details>

Generic-user-small
18 Dec 2013, 18:58
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
Generic-user-small
13 Aug 2014, 04:24
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
Nathan-6kites_pragsmall
24 Sep 2014, 23:07
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.

Generic-user-small
12 Nov 2014, 02:45
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
9863_pragsmall
05 Dec 2014, 21:15
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
Generic-user-small
28 Dec 2014, 02:03
Pierre Sugar (56 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
Bach_sunglasses_pragsmall
15 Feb 2015, 03:29
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.

Generic-user-small
20 Jun 2015, 10:19
Charles Okwuagwu (2 posts)
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
Mee_pragsmall
26 Jul 2015, 06:26
Hector Ivan Patricio Moreno (1 post)

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
    [head| flatten_(tail,acc)]
  end
end
  You must be logged in to comment