# How to update a list in linear time using its previous index value?

Basically, what I want to do is similar to what the following Python function is doing:

``````def myfunction(mylist):
initial = *len(mylist)
initial = 1
for i in range(1, len(mylist)):
initial[i] = mylist[i - 1] * initial[i - 1]
``````

I tried doing something like the code given below, however, it has a complexity more than linear time plus it doesn’t work properly as well since it seems to be using the `i` value rather than the `i-1` value of `initial`.

``````def myfunction(mylist) do
initial = List.duplicate(0, len(mylist))
initial = List.update_at(initial, 0, &(&1 + 1))

1..len(mylist)-1
|> Enum.map(fn(i) ->
initial = List.update_at(initial, i, &(Enum.at(mylist, i-1) * &1))
initial
end)
end
``````

Any help would be appreciated over here. Thank you!

Can you explain what the function is actually doing here? What is an example input and output?

1 Like

Using `Enum.at` inside of a loop over the length will give you `O(N^2)` performance. Avoid it at all costs.

In this case, the indexing is mostly superfluous: a value in the output list is a function solely of the current element and the preceding value of the output list.

Since you need all the intermediate values, `Enum.scan` is a better choice. For instance:

``````# input list
a = [2, 3, 5]

# prepend a 1
b = [1 | a]

# calculate the running product
Enum.scan(b, 1, &Kernel.*/2)
# returns [1, 2, 6, 30]
``````
3 Likes

So basically, let us say that `mylist` = [2,3,4,5,6]. Now, `initial` would be a list of zeros apart from the first index being one, having the following value: `[1,0,0,0,0]`.

Now, the `for` loop will be running from 1 to the length of `mylist` which is 5 in this case. Inside this, the `initial` list is getting updated by multiplying the values of `mylist` with `initial`. For example, when `i=1`, `mylist[i-1]` would be 2 and `initial[i - 1]` would be 1 at the start. `initial[i]` over here would end up becoming 2. Similarly, for `i=2`, `mylist[i-1]` would be 3 now, and `initial[i - 1]` would be 2 and `initial[i]` over here would end up becoming 6.

Initial would get updated in the following way:

``````[1, 0, 0, 0, 0]
[1, 2, 0, 0, 0]
[1, 2, 6, 0, 0]
[1, 2, 6, 24, 0]
[1, 2, 6, 24, 120]
``````
1 Like

This is good advice. Thank you. I will check this out.

Yeah I think @al2o3cr 's answer is great. Notice how he frames it in more functional terms, instead of thinking of it as modifying a list at various points. Instead, he’s framing it as generating a new list as a functional mapping over the old list.

So you’re trying to calculate a list of the first `n` (or rather, the first `length(mylist)`) factorial numbers?

``````defmodule Example do
def factorial_list(other_list) do
1
|> Stream.iterate(fn prev -> prev * prev end)
|> Enum.take(length(other_list))
end
end
``````
1 Like

Won’t this simply give us a list of 1s of `length(other_list)` if lets say our `other_list` is `[2,3,4,5,6]`. And in a way, you’re right about factorial being calculated.

I’m sorry, you’re right.
This is what you’re looking for:

``````defmodule Example do
def factorials_list(other_list) do
Enum.take(factorials(), length(other_list))
end

def factorials do
Stream.concat(
,
Stream.scan(positive_integers(), 1, fn index, acc -> index * acc end)
)
end

def positive_integers do
Stream.iterate(1, fn prev -> prev + 1 end)
end
end
``````
1 Like