Enum over list and insert items from another list at certain indexes?

If I have 2 lists. list_one a list of values and list_two a list of tuples that represent {value, index}

list_one = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
list_two = [{11, 1}, {12, 3}, {13, 6}]

what is the most performant way in Elixir to insert the values from list_two into list_one at the given index and pushing the value at that index back a spot. like:

list_one = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
list_two = [{"A", 1}, {"B", 3}, {"C", 6}]
#becomes
[1, "A", 2, 3, "B", 4, 5, 6, "C", 7, 8, 9, 10]
1 Like

Hey @CherryPoppins, what have you tried so far?

1 Like

so, just real quick something like:

  def test do
    list_one = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    list_two = [{"A", 1}, {"B", 3}, {"C", 6}]

    Enum.reverse(find(list_one, list_two, 0, []))
  end

  def find(a, _, _, result) when a == [], do: result

  def find([head | tail], [{value, index} | rest], here, result) when here == index,
    do: find(tail, rest, index + 1, [head, value | result])

  def find([head | tail], inserts, index, result),
    do: find(tail, inserts, index + 1, [head | result])

don’t judge my function/arg names lol

1 Like

This is pretty good! As far as your version goes I think the only thing I’d change is to use pattern matching over guards where possible eg:

# instead of
  def find(a, _, _, result) when a == [], do: result
# you can do
  def find([], _, _, result), do: result

# and instead of 
  def find([head | tail], [{value, index} | rest], here, result) when here == index
# you can do
  def find([head | tail], [{value, index} | rest], index, result)
# this works because when two variables have the same name in a match, they must be equal for the match to work.

Otherwise your solution is pretty optimal! You could add one additional clause to terminate early if there are no more inserts:

  def find(remaining, [], here, result) do
    Enum.reverse(result, remaining)
  end

This basically reverses the result that was accumulated backwards up to this point on top of remaining which is in the right order already.

Otherwise, great answer!

3 Likes

There is only one problem when inserting many values to a list i.e. indexes. When you insert said 11 (or "A" in second example) at index 1 then all next list elements have increased their index by 1 and the same happen for every next insert operation.

There are 2 possible solutions:

  1. The simplest is to order list_two by index in desc mode and simply reduce it over list_one by just inserting each element to list. This way we do not need to worry about indexes as we do that in reverse mode and we do not care what happens with all next element indexes.

  2. However there is much faster way. We can use pattern matching when calling same function recursively and increase current index (stored as an extra argument) by 1 only when we insert element.

    This way instead of rely on element’s index, which is changed for every insert operation, we are inserting elements in proper place with “shadow” index which counts only original elements.

Your code is close to 2nd option, but except @benwilson512 suggestions you can also avoid reversing your list.

Here is a code example for both ways:

defmodule Example do
  # fast/3 assumes that you have proper order of insert_list
  # so there is no sorter function used here
  def fast(data_list, insert_list, index \\ 0)

  # when data_list is empty all we need to do
  # is to add each element from insert_list regardless of index
  # look that passed index here may be any as it would not be used in pattern matching anymore
  def fast([], [{element, _index} | insert_list], index) do
    [element | fast([], insert_list, index)]
  end

  # this clause is even more simpler
  # when we don't have anything to insert all we need
  # to do is to return rest of data_list as a tail of result list
  def fast(data_list, [], _index), do: data_list

  # a "shadow" index matches index in insert_list
  # we simply insert the element
  # and *DO NOT* change "shadow" index 
  def fast(data_list, [{element, index} | insert_list], index) do
    [element | fast(data_list, insert_list, index)]
  end

  # otherwise inserting element from data_list
  # and recursively call same function
  # with new data_list and increased "shadow" index
  def fast([element | data_list], insert_list, index) do
    [element | fast(data_list, insert_list, index + 1)]
  end

  def simple(data_list, insert_list) do
    insert_list
    # ensure desc i.e. reverse index order
    |> Enum.sort_by(&elem(&1, 1), :desc)
    # each tuple from insert_list is passed to anonymous function below
    |> Enum.reduce(data_list, fn {item, index}, acc ->
      # in this example acc (accumulator) is our data_list
      List.insert_at(acc, index, item)
    end)
  end
end

list_one = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
list_two = [{"A", 1}, {"B", 3}, {"C", 6}]

iex> Example.fast(list_one, list_two)
iex> Example.simple(list_one, list_two)

What’s interesting in those example is that both support multiple elements with same index in insert_list. However since a simple solution in fact reverses insert_list the order of inserted elements is reversed, see:

list_one = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
list_two = [{"A1", 1}, {"A2", 1}, {"B1", 3}, {"B2", 3}, {"C1", 6}, {"C2", 6}]

iex> Example.fast(list_one, list_two)
[1, "A1", "A2", 2, 3, "B1", "B2", 4, 5, 6, "C1", "C2", 7, 8, 9, 10]

iex> Example.simple(list_one, list_two)
[1, "A2", "A1", 2, 3, "B2", "B1", 4, 5, 6, "C2", "C1", 7, 8, 9, 10]

I believe those examples are interesting also for a learning purposes.

Helpful resources:

  1. Enum.reduce/3
  2. Enum.sort_by/3
  3. List.insert_at/3
  4. Patterns and Guards
2 Likes

hi! how about this?

 def insert_before_index(list, new_items) do
    new_items_hash = Enum.into(new_items, %{}, fn {n, i} -> {i, n} end)
    list
    |> Enum.with_index()
    |> Enum.flat_map(fn {l, i} ->
       (if new_items_hash[i], do: [new_items_hash[i], l], else: [l])
    end)
 end

with my 2 testcases gives:

> elixir insert-into-list.exs
[["A", "C", "E"], [{"B", 1}, {"D", 3}]]
   -->  : ["A", "B", "C", "E"]

[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [{"A", 1}, {"B", 3}, {"C", 6}]]
   -->  : [1, "A", 2, 3, "B", 4, 5, 6, "C", 7, 8, 9, 10]

thoughts?

1 Like

Also, when i first read this i thought the 2nd list’s numbers were the index at which the item should be in the resultant list!!

So, that version is similar:

  def insert_after_index(list, new_items) do 
     new_items_hash = Enum.into(new_items, %{}, fn {n, i} -> {i, n} end) 
     0..(length(list) + map_size(new_items_hash) - 1) 
     |> Enum.reduce([[], list], fn 
        i, [acc, [l|rest]=list] -> 
         if new_items_hash[i] do 
           [[new_items_hash[i]|acc], list] 
         else 
           [[l|acc], rest] 
         end 
     end) 
     |> hd 
     |> Enum.reverse() 
   end

Thoughts on this one too?