you should be looking for a better data structure - one that supports deletions from arbitrary positions faster than
O(length).
This is a misunderstanding of original task. @Changxin was just looking for solution to delete the first element he has found satisfying the predicate during traversal of the structure.
So, first of all, the traversal of the structure is already a O(length) task. O(length) to delete, doesn’t change complexity
Secondly, list is one of the fastest structures which can delete value during traversal (second one is tuple).
So the most efficient solution is:
defp do_delete_first([], _func), do: []
defp do_delete_first([head | tail], func) do
if func.(head) do
Process.put(:"__delete_first_found__", head)
tail
else
[head | do_delete_first(tail, func)]
end
end
def delete_first(list, func) do
list = do_delete_first(list, func)
{Process.delete(:"__delete_first_found__"), list}
end
Because it has nothing in the stack, it traverses until reaches the value and it uses this trick with tail recursion where return value is moved into the head of the list once the function returns. But this function looks ugly, because it uses pdict.
That’s why implementation of this function is a job for a library
Considering other arguments,
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.
Some strucutres can be traversed and ordered (consider tuples and keywords). For these structures you also shouldn’t traverse the whole structure
The situation on the BEAM is more complicated than “body recursion BAD, tail recursion GOOD”.
Yeah, I know that, and I’ve read about it in “7 myths of erlang efficiency”, but I’ve described why this particular case of recursion is worse than just a tail recursion. The reason were: extra concatenations and variables on the stack
Math problem. How to code `Xn+1 = Xn + Xn * S` - #10 by al2o3cr
This is a great post, thanks!
