Updating a list in place while iterating through it

Questions / Help
1

Hello

I have a function where I need to update the values in a list if a certain condition is met. I’m pretty new with Elixir and functional programming, so this is not as obvious to me as with some other language such as Java.

I want to accomplish the same with Elixir as the following piece of Java Code:

public void union(int p, int q)
{  
   int pID = list[p];
   int qID = list[q];

   if (pID == qID) return;

   for (int i = 0; i < id.length; i++)
       if (id[i] == pID) id[i] = qID;
 }

Here is my attempt in Elixir. Instead of updating the list, I am appending to a new list:

def union(list, p, q) do
    p_id = Enum.at list, p
    q_id = Enum.at list, q
    Enum.reduce(list, [], fn (value, new_list) ->
        if value == p_id do
            new_list ++ [q_id]
        else
            new_list ++ [value]
        end
    end)
end

Is there a better or more functional way of doing this? Any help would be appreciated.

2

Your approach does not scale very well, as it has quadratic runtime because of appending to the list on each step.

As I understand your code, you actually want to replace the item at index p with the item at index q, while not touching anything else (including item q)?

def union(list, p, q) do
  q_id = Enum.at(list, q)
  {front, [_ | tail]} = Enum.split(list, p)
  front ++ [q_id | tail]
end

This should do it, if I understood you correctly. Its not perfect, again, but better than your initial code.

The most idiomatic way were probably to not depend on indexes at all, but that problem is hard to solve without knowing anything.

2 Likes
3

I’m not sure where id comes from in the original code, I’m assuming it is a list of IDs (and pID and qID are examples), and you are replacing all occurrences of pID with qID in the list id? If so, this should do it:

def union(list, p, q) do
  p_id = Enum.at(list, p)
  q_id = Enum.at(list, q)
  Enum.map(list, fn(x) -> if x == p_id do q_id else x end end)
end
2 Likes
4

Thank you NobbZ. You are absolutely right, it won’t scale very well. It’s actually one of the least optimal solutions to the Dynamic Connectivity problem in the Algorithms book by Sedgewick, section 1.5

1 Like
5

Thank you jfeng. The id variable is a list of integers set as an instance variable in the class. Yes, you are correct. It is replacing all occurrences of pID with qID in the list. As NobbZ pointed out, p and q are the indexes of the items in the list, and p_id and q_id are the values at those indexes.

1 Like
6

For something more familiar looking, a comprehension could also be used:

def union(list, p, q) do
  p_id = Enum.at(list, p)
  q_id = Enum.at(list, q)
  for id <- list do
    case id do
      p_id -> q_id
      x -> x
    end
  end
end
1 Like
7

That certainly feels more familiar, but I prefer the conciseness of your first solution. Thank you

1 Like
8

For note, this line can also be (and more efficiently since only performing the ‘at’ when needed on q_id:

p_id = Enum.at(list, p)
Enum.map(list, &if(&1 == p_id, do: Enum.at(list, q), else: x))

And you could make it even faster by grabbing both p and q ID’s in a single pass but meh, that makes it longer now… ^.^;

1 Like