small medium large xlarge

Dave_gnome_head_isolated_pragsmall
16 Jul 2013, 02:16
Dave Thomas (370 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 (4 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 (9 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 (13 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 (12 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 (4 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
Generic-user-small
24 Sep 2015, 21:26
Mikalai Silivonik (1 post)

In Jose’s solution the following

  def do_flatten([h|t], tail) do
    [h|do_flatten(t, tail)]
  end

can be optimized like this:

  def do_flatten(l, tail) do
    [l|tail]
  end

because at this point tail is already flattened.

Generic-user-small
18 Jan 2016, 20:22
Riley White (4 posts)

I believe the second solution offered up by Dave (reproduced here) has an error where it doesn’t flatten the head item if it’s a nested empty list.

So you get:

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

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

Here’s the original code.

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

Here’s my stab at a version that addresses the bug:


  def flatten(nested_lists), do: reverse(_flatten(nested_lists, []))
  
  defp _flatten([], acc), do: acc
  defp _flatten([[]|tail], acc), do: _flatten(tail, acc)
  defp _flatten([[head|tail]|outer_tail], acc), do: _flatten([head, tail | outer_tail], acc)
  defp _flatten([head|tail], acc), do: _flatten(tail, [head|acc])

I originally used ++ to join tail and outer_tail in the 3rd _flatten function, which I felt was inefficient. On comparing with Dave’s solution, I much preferred his use of [h, t tail] :-)
Generic-user-small
10 Feb 2016, 06:25
Stefan Houtzager (8 posts)

Not the meaning of the exercise to solve it this way maybe but:

defmodule MyList do
  def flatten(list) do
    to_char_list RegEx.replace(~r{[\[\]]}, to_string(list), "")
  end
end

IO.inspectMyList.flatten([1, 2, [[[5, 9]], [3]]]) 
Generic-user-small
16 Feb 2016, 20:39
Alex Deva (4 posts)

Here’s mine:

def MyList
  def flatten([]), do: []
  def flatten([h|t]) when is_list(h), do: flatten(h) ++ flatten(t)
  def flatten([h|t]), do: [h] ++ flatten(t)
end

I don’t understand why José’s solution needed to have helper functions. Can anybody enlighten me? Maybe I’m missing something important.

Generic-user-small
04 Mar 2016, 22:22
Quentin Crain (1 post)

Alex: Probably old habits of functional programmers die hard! ;)

Here is mine (meaning basically Jose’s):


def flatten_2(list), do: _flatten_2(list, []) |> Enum.reverse
defp _flatten_2([], result), do: result
defp _flatten_2([head|tail], result), do: _flatten_2(tail, _flatten_2(head, result))
defp _flatten_2(item, result), do: [item | result]

Do you know why we need a guard? Here was my thinking:

Ok, we are going to do this recursively with an accumulator. (Functional programming “standard”.)

So, the 1st function clause is obvious.

Now, lets do the normal head/tail thing and .. wait! If the 2nd clause succeeds then whatever it was sent must be a list, so the 3rd clause can just take the item/element – assumed to be a not-list – and add it to the list! Cool!

So, back to the 2nd clause, we call recursively with the tail (again, functional programming “standard” …) and the accumulator is .. a recursive call with the head!

That makes sense.

Img_2196_pragsmall
27 May 2016, 13:08
Diogo Neves (12 posts)

Can anyone explain this comment?

# The simplest version is probably to use list concatenation. However,
# this version ends up rebuilding the list at each step

I don’t understand why it rebuilds the list each step (compared to other solutions)

Thanks

EDIT:
After looking around I think I know how to explain it.

# this creates a new list with head that links to the list
# returned in the call
[ head | recursive_call(tail) ]

# this creates a completely new list and copies all items,
# returned from the function, to it
recursive_call(tail) ++ [head]

The main reason is that to append an element to the end of a list would change it but not if it’s added to the beginning.
Here’s a simple example:

list1 = [2, 3]
# list 1 'points' to the element with value 2

list2 = [1 | list1]
# list 2 'points' to the element with value 1 but list 1
# still starts at 2

[    1,     2, 3]
#    ^      ^
#  list2   list1

# if instead we do
list3 = list2 ++ [4]

# we should end up with 2 lists:
[    1,     2, 3]
#    ^      ^
#  list2   list1

[    1, 2, 3, 4 ]
#    ^ 
#  list3

and here’s a simple way to measure the difference (a lot!):

defmodule Benchmark do

  def measure(function) do
    function |> :timer.tc |> elem(0) |> Kernel./(1000000)
  end

end

defmodule TestPerformance do

  def upto_reverse(n), do: _upto_reverse(n) |> Enum.reverse
  defp _upto_reverse(0), do: []
  defp _upto_reverse(n), do: [n | _upto_reverse(n - 1)]

  def upto(0), do: []
  def upto(n), do: upto(n - 1) ++ [n]

end

Benchmark.measure(fn -> TestPerformance.upto_reverse(100000) end) # fast
Benchmark.measure(fn -> TestPerformance.upto(100000) end) # sloooooow
You must be logged in to comment