I have an algorithm in python which I need to implement in a functional programming language, Elixir.

input:

• list of tuples: [("A", "B"), ("B", "C"), ..., ("E", "F")]
• list of booleans: [False, True, True, False, True]
  • indicate whether a tuple is valid or not
  • ("A", "B") valid , ("B", "C") invalid, ...

output:

• [["A"], ["B", "C", "D"], ["E", "F"]]
  • nested list of grouped tokens
  • A does not have a connection -> single item
  • B, C, D have a connection -> grouped together

Basically I want to translate this python sample code to Elixir:

input = ["A", "B", "C", "D", "E", "F"]
tuples = list(zip(input, input[1:]))
# --> [("A", "B"), ("B", "C"), ..., ("E", "F")]

# this is a black box -> database result
results = [False, True, True, False, True]
combined = zip(tuples, results)

[first_item, *_] = input
biglist = []; smalllist = [first_item]
for (left, right), result in zip(tuples, results):
    if result:
        # valid tuple, keep filling current bucket
        smalllist.append(right)
    else:
        # invalid tuple
        biglist.append(smalllist)
        smalllist = [right]
        
if len(smalllist) > 0:
    biglist.append(smalllist)

print(biglist)
[["A"],  ["B",  "C",  "D"],  ["E", "F"]]
#     fls,   tru,  tru,   fls,   tru

What is the Elixir-way for that problem?

CodePudding user response：

This is the exact transliteration. There's probably a much better way to do it though, maybe I'll come back to it later if nobody else does.

defmodule Example do
  def run do
    input = ~w(A B C D E F)
    tuples = Enum.zip(input, tl(input))

    results = [false, true, true, false, true]
    combined = Enum.zip(tuples, results)

    first_item = hd(input)
    small_list = [first_item]
    big_list = []

    {small_list, big_list} =
      Enum.reduce(combined, {small_list, big_list}, fn
        {{_left, right}, true}, {small_list, big_list} ->
          {[right | small_list], big_list}

        {{_left, right}, false}, {small_list, big_list} ->
          {[right], [Enum.reverse(small_list) | big_list]}
      end)

    case small_list do
      [] -> big_list
      _ -> [Enum.reverse(small_list) | big_list]
    end
    |> Enum.reverse()
  end
end

Output:

[["A"], ["B", "C", "D"], ["E", "F"]]

CodePudding user response：

A similar solution, using Enum.chunk_while/4

defmodule Chunky do
  def collect([], _), do: []

  def collect([hd | rest], acceptance_list) do
    rest
    |> Enum.zip(acceptance_list)
    |> Enum.chunk_while(
      [hd],
      fn
        {next, true}, candidate_list ->
          {:cont, [next | candidate_list]}
        {next, false}, candidate_list ->
          {:cont, Enum.reverse(candidate_list), [next]}
      end,
      fn
        [] = acc -> {:cont, acc}
        [_ | _] = candidate_list -> {:cont, Enum.reverse(candidate_list), []}
      end
    )
  end
end

I skipped the first zip because the value from it was being ignored anyway (Missed that the first several passes through).

In the first pattern match case in the chunk_while, in the event the prior acceptance was false, we replace the sublist with the "next" item and emit the reversed chunk.

For the second case, in the event the prior acceptance was false, we replace the sublist with the "next" item and emit the reversed chunk.

A small caveat to this approach is that, under the covers, chunk_while does more or less what Adam's solution does: it reverses the list each chunk. So effectively this requires an additional reversal behind the scenes, which doesn't cost that much with this data size but might of concern for larger lists.

Although it's possible it will demand slightly less cognitive load.

I turned this into a /2 function just for my own convenience while testing; you can run it like this:

list = ["A", "B", "C", "D", "E", "F"]
acceptance = [false, true, true, false, true]

Chunky.collect(list, acceptance)

I did not do it in the example above, because the overhead added wasn't worth it given the small list size, but for larger lists you may find it useful to replace the Enum.xyz functions with their Stream.xyz equivalents.