Enum.at/3 function is used to find an element at the given index in zero-based. This document describe how this function work and explain it complexity.
The Enum.at/3 is defined in the official elixir repository at this code: https://github.com/elixir-lang/elixir/blob/d3285b176e87b025a6949867b58a7ce0e3839b58/lib/elixir/lib/enum.ex#L478
def at(enumerable, index, default \\ nil) when is_integer(index) do
case slice_forward(enumerable, index, 1, 1) do
[value] -> value
[] -> default
end
endThe slice_forward/4 function is defined at this code: https://github.com/elixir-lang/elixir/blob/d3285b176e87b025a6949867b58a7ce0e3839b58/lib/elixir/lib/enum.ex#L4460
defp slice_forward(enumerable, start, amount, step) when start < 0 do
{count, fun} = slice_count_and_fun(enumerable, step)
start = count + start
if start >= 0 do
amount = Kernel.min(amount, count - start)
amount = amount_with_step(amount, step)
fun.(start, amount, step)
else
[]
end
end
defp slice_forward(list, start, amount, step) when is_list(list) do
amount = amount_with_step(amount, step)
slice_list(list, start, amount, step)
end
defp slice_forward(enumerable, start, amount, step) do
case Enumerable.slice(enumerable) do
{:ok, count, _} when start >= count ->
[]
{:ok, count, fun} when is_function(fun, 1) ->
amount = Kernel.min(amount, count - start) |> amount_with_step(step)
enumerable |> fun.() |> slice_exact(start, amount, step, count)
# TODO: Deprecate me in Elixir v1.18.
{:ok, count, fun} when is_function(fun, 2) ->
amount = Kernel.min(amount, count - start)
if step == 1 do
fun.(start, amount)
else
fun.(start, Kernel.min(amount * step, count - start))
|> take_every_list(amount, step - 1)
end
{:ok, count, fun} when is_function(fun, 3) ->
amount = Kernel.min(amount, count - start) |> amount_with_step(step)
fun.(start, amount, step)
{:error, module} ->
slice_enum(enumerable, module, start, amount, step)
end
endAs we can see, the second pattern matches this condition: the enumerable is a list.
Take a look at the function that match the second condition:
defp slice_forward(list, start, amount, step) when is_list(list) do
amount = amount_with_step(amount, step)
slice_list(list, start, amount, step)
endThis function call 2 functions amount_with_step/2 and slice_list/4 to slide the list.
The amount_with_step/2 is defined at this code: https://github.com/elixir-lang/elixir/blob/d3285b176e87b025a6949867b58a7ce0e3839b58/lib/elixir/lib/enum.ex#L3042
defp amount_with_step(amount, 1), do: amount
defp amount_with_step(amount, step), do: div(amount - 1, step) + 1The slice_list/4 is defined at this code: https://github.com/elixir-lang/elixir/blob/d3285b176e87b025a6949867b58a7ce0e3839b58/lib/elixir/lib/enum.ex#L4507
defp slice_list(list, start, amount, step) do
if step == 1 do
list |> drop_list(start) |> take_list(amount)
else
list |> drop_list(start) |> take_every_list(amount, step - 1)
end
endThe drop_list/2 is defined at this code: https://github.com/elixir-lang/elixir/blob/d3285b176e87b025a6949867b58a7ce0e3839b58/lib/elixir/lib/enum.ex#L4272
defp drop_list(list, 0), do: list
defp drop_list([_ | tail], counter), do: drop_list(tail, counter - 1)
defp drop_list([], _), do: []The take_list/2 and take_every_list/3 ar defined at this code: https://github.com/elixir-lang/elixir/blob/d3285b176e87b025a6949867b58a7ce0e3839b58/lib/elixir/lib/enum.ex#L4755
defp take_list(_list, 0), do: []
defp take_list([head | tail], counter), do: [head | take_list(tail, counter - 1)]
defp take_list([], _counter), do: []
defp take_every_list([head | tail], to_drop),
do: [head | tail |> drop_list(to_drop) |> take_every_list(to_drop)]
defp take_every_list([], _to_drop), do: []
defp take_every_list(_list, 0, _to_drop), do: []
defp take_every_list([head | tail], counter, to_drop),
do: [head | tail |> drop_list(to_drop) |> take_every_list(counter - 1, to_drop)]
defp take_every_list([], _counter, _to_drop), do: []We simulate the Enum.at/3 function:
defmodule SimulateEnumAt do
def perform(list, index) do
amount = amount_with_step(1, 1)
case slice_list(list, index, amount, 1) do
[] -> nil
[value] -> value
end
end
defp amount_with_step(amount, 1) do
IO.inspect("amount_with_step with the step is 1")
amount
end
defp amount_with_step(amount, step) do
IO.inspect("amount_with_step with the remaining condition")
div(amount - 1, step) + 1
end
defp slice_list(list, start, amount, step) do
if step == 1 do
IO.inspect("slice_list with the step is 1")
list |> drop_list(start) |> take_list(amount)
else
IO.inspect("slice_list with the remaining condition")
list |> drop_list(start) |> take_every_list(amount, step - 1)
end
end
defp drop_list(list, 0) do
IO.inspect("drop_list with the counter is 0")
list
end
defp drop_list([_ | tail] = list, counter) do
IO.inspect("drop_list with the list is #{inspect(list)}, the counter is #{counter}")
drop_list(tail, counter - 1)
end
defp drop_list([], _) do
IO.inspect("drop_list with the list is empty")
[]
end
defp take_list(_list, 0) do
IO.inspect("take_list with the counter is 0")
[]
end
defp take_list([head | tail] = list, counter) do
IO.inspect("take_list with the list is #{inspect(list)}, the counter is #{counter}")
[head | take_list(tail, counter - 1)]
end
defp take_list([], _counter) do
IO.inspect("take_list with the list is empty")
[]
end
defp take_every_list(_list, 0, _to_drop) do
IO.inspect("take_every_list with counter with the counter is 0")
[]
end
defp take_every_list([head | tail] = list, counter, to_drop) do
IO.inspect("take_every_list with counter with the list is #{inspect(list)}, the counter is #{counter}, the to_drop is #{to_drop}}")
[head | tail |> drop_list(to_drop) |> take_every_list(counter - 1, to_drop)]
end
defp take_every_list([], _counter, _to_drop) do
IO.inspect("take_every_list with counter with the list is empty")
[]
end
endRun the simulated function
iex> SimulateEnumAt.perform(["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"], 8)
"amount_with_step with the step is 1"
"slice_list with the step is 1"
"drop_list with the list is [\"a\", \"b\", \"c\", \"d\", \"e\", \"f\", \"g\", \"h\", \"i\", \"j\"], the counter is 8"
"drop_list with the list is [\"b\", \"c\", \"d\", \"e\", \"f\", \"g\", \"h\", \"i\", \"j\"], the counter is 7"
"drop_list with the list is [\"c\", \"d\", \"e\", \"f\", \"g\", \"h\", \"i\", \"j\"], the counter is 6"
"drop_list with the list is [\"d\", \"e\", \"f\", \"g\", \"h\", \"i\", \"j\"], the counter is 5"
"drop_list with the list is [\"e\", \"f\", \"g\", \"h\", \"i\", \"j\"], the counter is 4"
"drop_list with the list is [\"f\", \"g\", \"h\", \"i\", \"j\"], the counter is 3"
"drop_list with the list is [\"g\", \"h\", \"i\", \"j\"], the counter is 2"
"drop_list with the list is [\"h\", \"i\", \"j\"], the counter is 1"
"drop_list with the counter is 0"
"take_list with the list is [\"i\", \"j\"], the counter is 1"
"take_list with the counter is 0"
"i"As we can see, the function loop the list to find the element that match the index by using the drop_list/2 function to drop the first element when the counter is decreased. That mean if we want to find an element by it index, we need index step to loop the list. The worst case is the index is greater than or equal to the number of element. The reason for this solution is the list structure in Elixir is built for real Linked list, so the only way to find an element in a linked list is looping from the first to the last element to find the result. The complexity for this solution is O(n), which n is the number of elements.
Elixir List document: https://hexdocs.pm/elixir/1.14/List.html