# 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

2 Likes

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

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.

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

I donâ€™t understand how you get the result above. It seems like the result ought to be:
[1, â€śAâ€ť, 2, â€śBâ€ť, 3, 4, â€śCâ€ť, 5, 6, 7, 8, 9, 10]
This is list_one with the list_two values inserted at the specified index. What am I missing?

Yeah, the original question isnâ€™t actually what I ended up needing, index relative to original list without mutation. What you posted is what I ended up needing and how I ended up writing `insert_at_many/2` .

Here is an alternate implementation:

``````def insert_at_many(into_list, insert_list) do
insert_list = Enum.sort_by(insert_list, &(elem(&1, 1)))
Enum.reduce(insert_list, into_list, fn({value, index}, acc) -> List.insert_at(acc, index, value) end)
end
``````

All in just one clause.

I already wrote this as `Example.simple/2`.

Also thiis code is wrong, because the `sort_by` function needs to be in `:desc` mode, because otherwise you have a mess with indexes and therefore output is wrong.

@CharlesIrvine That could work but is where my initial question about performance comes into play. prepending an item to the list is cheap, searching the list then adding the link is more expensive.

Here is my module and test module. Everything seems to work fine. Note that I previously posted a question to the original poster asking for a clarification on the original intent.

``````defmodule Utils do

@spec insert_list_into(list(), [tuple()]) :: list()
def insert_list_into(into_list, insert_list) do
insert_list = Enum.sort_by(insert_list, &(elem(&1, 1)))
Enum.reduce(insert_list, into_list, fn({value, index}, acc) -> List.insert_at(acc, index, value) end)
end

end
``````

and:

``````defmodule UtilsTest do
use ExUnit.Case
doctest Example

test "insert sorted items into list" do
into_list = [0, 1, 3, 5]
from_list = [{:two, 2}, {:four, 4}]

assert Utils.insert_list_into(into_list, from_list) == [0, 1, :two, 3, :four, 5]
end

test "insert unsorted items into list" do
into_list = [0, 1, 3, 5]
from_list = [{:four, 4}, {:two, 2}]

assert Utils.insert_list_into(into_list, from_list) == [0, 1, :two, 3, :four, 5]
end

test "insert unsorted and out of range items into list" do
into_list = [0, 1, 3, 5]
from_list = [{:four, 4}, {:two, 2}, {:ninety_nine, 99}]

assert Utils.insert_list_into(4, from_list) == [0, 1, :two, 3, :four, 5, :ninety_nine]
end
end
``````

I actually didnâ€™t see your last implementation. Iâ€™m not sure yourâ€™s is exactly like mine. Your reduce is on the data_list and mine is on the insert_list.

1 Like

Yeah, I suppose that could be. Iâ€™d have to think about it. But it always depends on your context. Depending on the context, the difference in performance between two functions could be negligible. Maybe you could post the implementation that you went with.

judging by your handle, my implementation is probably what led you here

Sorry, didnâ€™t followâ€¦

we probably work together.

Ohâ€¦ But only recently. I think I get you now. Yep, and youâ€™re right, thatâ€™s what brought me here. Well, also, itâ€™s been three years since I coded Elixir. Also, I was refamiliarizing myself with Enum.reduce this morning.

So you need to calculate a proper `index` (after insertion) in this list. Usually the `index` refers to `into_list` and not `output` list, so `from_list` usually looks like:

``````[{:two, 2}, {:four, 3}]
``````

and in this case `index` matters.

Your solution is more like merge original list with `[nil, nil, :two, nil, :four]` list, but for shorter format `nil` are replaced with `indexes`.

Now please take a look at example input and output in first post:

With your code it looks like:

``````Utils.insert_list_into(list_one, list_two)
[1, "A", 2, "B", 3, 4, "C", 5, 6, 7, 8, 9, 10]
``````

which is incorrect.

Edit: Looks like what I wrote was correct, but `4 months ago`, sorry.

I would advise to update questions in that one in future with proper Edit section as we can have misunderstanding like now.

Thatâ€™s the thing that I clarified with the original poster in my first post today. He clarified that though the result above isnâ€™t what he was originally looking for, it turned out that it is what he wanted.

1 Like