-
-
Save veelenga/6057bdef7227bb4a23fcdd2394e0abec to your computer and use it in GitHub Desktop.
def flatten(list), do: flatten(list, []) |> Enum.reverse | |
def flatten([h | t], acc) when h == [], do: flatten(t, acc) | |
def flatten([h | t], acc) when is_list(h), do: flatten(t, flatten(h, acc)) | |
def flatten([h | t], acc), do: flatten(t, [h | acc]) | |
def flatten([], acc), do: acc |
@chx ++
works only on lists, so your code (both samples) will fail on this input: [1, [2]]
.
Here is an adjusted version that allows flattening until we reach the required level (without ++
):
defmodule List do
def flatten(list, depth \\ -2), do: flatten(list, depth + 1, []) |> Enum.reverse
def flatten(list, 0, acc), do: [list | acc]
def flatten([h | t], depth, acc) when h == [], do: flatten(t, depth, acc)
def flatten([h | t], depth, acc) when is_list(h), do: flatten(t, depth, flatten(h, depth - 1, acc))
def flatten([h | t], depth, acc), do: flatten(t, depth, [h | acc])
def flatten([], _, acc), do: acc
end
list = [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
List.flatten(list, 0) # [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8]
List.flatten(list, 1) # [1, 2, [3, 4], 5, [[]], [[6]], 7, 8]
List.flatten(list, 2) # [1, 2, 3, 4, 5, [6], 7, 8]
List.flatten(list, 3) # [1, 2, 3, 4, 5, 6, 7, 8]
List.flatten(list) # [1, 2, 3, 4, 5, 6, 7, 8]
There is one exceptional case:
List.flatten(list, -1) # [[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]]
so you may need to update it a bit :)
Very late to the party, but this is a shorter answer. My benchmarks put it at about .1x to 2x slower than the FlattenReverse method.
defmodule List do
def flatten([head | tail]), do: flatten(head) ++ flatten(tail)
def flatten([]), do: []
def flatten(head), do: [head]
end
An improvement to 0.5 speed of FlattenReverse,
def flatten(list), do: flatten(list, [])
def flatten([h | t], acc) when h == [], do: flatten(t, 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)]
def flatten([], acc), do: acc
@chx, solved my problem, thanks very much!
For anyone ending up here looking for a way to flatten only the first level in a list without concatenation or multiple list traversals (i.e. @chx's request):
list = [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
Enum.flat_map(list, fn x when is_list(x) -> x; x -> [x] end)
# [1, 2, [3, 4], 5, [[]], [[6]], 7, 8]
The above may overflow the stack.
See tail recursion version that I wrote: https://gist.github.com/heri16/e726ee7f335d2ca61bbbb016e6b884e1
What if you wanted to flatten only one level? I can't figure that out without
++
.Or
List.foldl(list, [], &(&1 ++ &2))