Changxin

How to `get` or `remove` the first matched element in a list without traverse it?

Hi, are there some functions like

Enum.find_first(enumerable, x -> boolen())
# or
Enum.fliter_first(enumerable, func)
Enum.remove_first(enumerable, func)

I don’t want to traverse a whole list, but some implements like below are not so efficent.

def filter_first([], _func), do: {nil, []}
def filter_first([h | t], func) do
  case func.(h) do
    true -> {h, t}
    false ->
      {first, left} = filter_first(t, func)
      {first, [h | left]}
  end
end

are there some efficient ways to make it?

30 comments

#troubleshooting #learning-elixir #newbie

1 5550 30

2024-07-19 09:39:08 UTC

Marked As Solved

hst337

The most efficient and simple solution is to use pathex

To define first element in an enumerable which satisfies the condition (for which func returns true), you can write something like

import Pathex; import Pathex.Lenses
path_to_first = some() ~> filtering(func)

And you can use this path to delete, set, update, etc. using Pathex verbs like

Pathex.delete(enumerable, path_to_first)
Pathex.set(enumerable, path_to_first, new_value)
Pathex.over(enumerable, path_to_first, fn old_value -> old_value + 2 end)

Post #3

Also Liked

sabiwara

Elixir Core Team

Interesting trick. I think you meant body recursion

Just for the sake of completion, here is the tail recursive version:


  def find_delete(list, fun) when is_function(fun, 1) do
    do_find_delete(list, fun, [])
  end

  defp do_find_delete([head | tail], fun, acc) do
    if fun.(head) do
      {head, :lists.reverse(acc, tail)}
    else
      do_find_delete(tail, fun, [head | acc])
    end
  end

  defp do_find_delete([], _fun, acc) do
    {nil, :lists.reverse(acc)}
  end

This rough benchmark gives me a slightly faster time for the tail-recursive version, but takes slightly more memory (results). Of course this would vary based on OS, list size, OTP version…

Post #16

kokolegorille

Hello and welcome,

You could use Enum.find, as it returns the first match…

Post #2

al2o3cr

Using a function that returns a list on non-list Enumerables is possible, but it’s going to 100% have to traverse the whole structure to create all the list cells.

For instance:

  def filter_first(enum, func) do
    case Enum.reduce(enum, {:not_found, []}, &reduce_filter_first(&1, &2, func)) do
      {:ok, result, list} ->
        {result, Enum.reverse(list)}

      {:not_found, list} ->
        {nil, Enum.reverse(list)}
    end
  end

  defp reduce_filter_first(el, {:ok, result, rest}, _func) do
    {:ok, result, [el | rest]}
  end

  defp reduce_filter_first(el, {:not_found, rest}, func) do
    if func.(el) do
      {:ok, el, rest}
    else
      {:not_found, [el | rest]}
    end
  end

This uses Enum.reduce to accept anything that speaks the Enumerable protocol.

However, it has a couple of efficiency concerns:

has to traverse every element of the input list, even if the value has already been found since the result from reduce contains the list in reverse order
returns a new list even if the input was a list and the function never returned true. (for the same reason)
it uses less stack, but creates more garbage on the heap (the entire input of Enum.reverse will become garbage)

The situation on the BEAM is more complicated than “body recursion BAD, tail recursion GOOD”.

See a recent post where I went much farther down that rabbithole than I expected to:

BUT TO REITERATE

If you have enough elements in the list for any of this to really matter, you should be looking for a better data structure - one that supports deletions from arbitrary positions faster than O(length).

Post #8