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

Questions / Help
1

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
2

Hey @CherryPoppins, what have you tried so far?

1 Like
3

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
4

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!

4 Likes
5

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
6

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
7

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?

8

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?

9

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 :wink:.

10

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.

11

I already wrote this as Example.simple/2. :sweat_smile:

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.

12

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

13

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
14

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.

15

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

16

Sorry, didn’t follow…

17

we probably work together.

18

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.

19

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. :sweat_smile:

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

20

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