Little coding challenge

Questions / Help
1

I hope this is appropriate here. I’d like to host a little coding challenge to see who can come up with the neatest way of turning this:

["x", "y", "z"]

into this:

[["x"], ["x", "y"], ["x", "y", "z"]]

So a kind of accumulative/recursive array, if you will. I have it working using Enum.reduce/3 but it has turned out much less elegant than I had hoped. Somehow I think it can be done more cleanly, so I am very curious to see how others would go about solving this little task.

4 Likes
2

I don’t know how complicated your solution was, but mine looks like this

["x", "y", "z"]
|> Enum.reduce({[], []},
     fn(elem, {acc1, acc2}) ->
       {[elem | acc1], [:lists.reverse([elem | acc1]) | acc2]}
     end)
|> elem(1) |> :lists.reverse

#=> [["x"], ["x", "y"], ["x", "y", "z"]]
1 Like
3

It may be faster to append to the end of the list with ++ instead of reversing the list since you will have reallocate the whole list anyway. To me that code would be clearer also.

2 Likes
4 
["x", "y", "z"] |>
Enum.reduce([], fn (x, acc) ->
  last = List.last(acc) || []
  acc ++ [last ++ [x]] 
end) |>
IO.inspect
1 Like
5

@marioosh hey, that is pretty much exactly my solution. :slight_smile:

1 Like
6

In haskell this one is very nice, since there is a function Data.List.tails which does exactly the reverse of what you are asking for. It would turn your given list into [["x", "y", "z"], ["y", "z"], ["z"], []].

So if we were doing filter null . map reverse . reverse . tails . reverse in haskell, that should pretty much do what you want, but thats untested.

so this gives me roughly this:

def ListPlus do
  def tails([x|xs]), do: [[x|xs]|tails(xs)]
  def tails([]), do: []
end

["x", "y", "z"]
|> Enum.reverse
|> ListPlus.tails
|> Enum.reverse
|> Enum.map(&Enum.reverse/1)
|> IO.inpect

Which of course is a little bit mor code than your solutions, but on the other hands side does much more rely on composition instead of folding, and when I helped in the FP classes of my university I realized, that it is hard for many students to grasp folding a list into a list. They all expect that after the fold, the list is gone. So I try to avoid folds that not remove at least one level of wrapping.

2 Likes
7 
for n <- 1..length(l), do: Enum.take(l,n)
12 Likes
8

with Enum.scan/3:

["x", "y", "z"] |> Enum.scan([], &([&1|&2])) |> Enum.map(&Enum.reverse/1)
1 Like
9

I tried using/creating a recursive function to see if I could solve this and arrived at:

def group_them(lst \\ [], acc \\ []) do
    case lst do
      [] -> []
      [h|t] -> [Enum.reverse([h|acc])]++group_them(t, [h|acc])
    end
  end
10

Thank you so much for all your input, this is fun! I think @andre1sk gets first price :medal: for elegance and brevity. I didn’t know that for has that mapping ability. It kind of makes me wonder why there isn’t something like each_with_index or maybe just:

Enum.iterate(list, &Enum.take(list, &1 + 1))

Anyway, I liked @jur0 's suggestion of Enum.scan, which I did’t know either. All the others are also much appreciated and I learned quite a bit today. Thanks again everyone.

3 Likes
11

here’s a much simpler solution than my previous one, that uses Enum.map_reduce/3

["x", "y", "z"]
|> Enum.map_reduce([],
  fn(elem, acc) ->
    x = acc ++ [elem]
    {x, x}
  end)
|> elem(0)
12

I realized that what we need for case like this is something similar to Enum.reduce_map/3, but that it will iterate not based on the number of elements in the enumerable, but based on whether the enumerable still have elements left to be processed.

Please anybody tell me if I missed this function and I have reinvented the wheel (it only works with lists though)

defmodule LittleChallenge do
  @spec iterate_until_empty(list, term, (list, term -> {list, term})) :: term
  def iterate_until_empty(list, acc, fun) when is_list(list) and is_function(fun, 2),
    do: do_iterate_until_empty(list, acc, fun)
  
  defp do_iterate_until_empty([], acc, _fun),
    do: acc

  defp do_iterate_until_empty(list, acc, fun) do
    {list, acc} = fun.(list, acc)
    do_iterate_until_empty(list, acc, fun)
  end
end

and you will do something like this,

["x", "y", "z"]
|> LittleChallenge.iterate_until_empty([], fn
  list, [] ->
    {list, [list]}

  list, acc ->
    case :lists.droplast(list) do
      [] ->
        {[], acc}
      term ->
        {term, [term | acc]}          
    end
end)
13

thanks @jur0 …
["x", "y", "z"] |> Enum.scan([], &(&2 ++ [&1]))

1 Like