# 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.

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.

2 Likes

`````` 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?