Proposal: Enum.pop_by/2

[Eric Froese]

In my current project, I have an existing list of unique objects (A0), and an updated representation of that list (A1).

I need to group A1 into thee lists: {added, still_present, removed} by comparing it to the state of A0 (then take an action on the added and removed items, but thats unrelated to this proposal).

Since each item is unique, once I determine that an item is "still_present" that item no longer needs to be part of the list which we use in determining grouping for the next item.

I coming up with the solution for that task, I came up with Enum.pop_by/2, with the following implementation.

@doc """

Returns a tuple with the popped value and the remainder of the list. The popped value is found

by the given function. Once it finds the popped value, it stops searching and returns the result.

Example:

pop_by([1, 2, 3], fn a -> a == 2 end)

> {2, [1, 3]}

# No item returns nil and unchanged list

pop_by([1, 2, 3], fn a -> a == 4 end)

> {nil, [1, 2, 3]}

"""

def pop_by(enumerable, fun), do: do_pop_by(enumerable, fun)

defp do_pop_by(enumerable, fun, collector \\ [])

defp do_pop_by([], _fun, collector), do: {nil, Enum.reverse(collector)}

defp do_pop_by([head | tail], fun, collector) do

if fun.(head) do

# found item! Reverse collector to maintain original list order and concat to tail

{head, Enum.reverse(collector) ++ tail}

else

do_pop_by(tail, fun, [head | collector])

end

end

What do you think? Could also make the collector reversal optional which would improve time complexity in cases where the order of list doesn't need to be maintained

[Ben Wilson]

Hi Eric,

Whether or not this is functionally equivalent to split_with depends on how it handles non unique lists, eg:

Enum.pop_by([1,2,2,3], fn x -> x == 2 end)

If it returns

{2, [1, 2, 3]}

Then it is definitely at least different.

This almost seems better suited for the List module. Map and many other Enumerables already have a pop concept that would be a lot more efficient, and this specific approach seems very list centric.

[Eric Froese]

Hi Ben,

I agree, the List module might be a better place for this function. It seems like a bit of a grey area as to what qualifies as Enum or List territory :P

Another difference in the pop_by function is that it quits after finding an appropriate index. split_with would continue to enumerate the entire list after finding a match. In my specific use case, this is nice because I am running pop_by on a list until that list is depleated, so the entire algo is O(n^logn) (instead of O(n^2) If I were to use split_with).

Yes, Enum.pop_by([1,2,2,3], fn x -> x == 2 end) would return {2, [1, 2, 3]}

I would love to get a chance to contribute to Elixir :) But of course, not if it's not worth adding into the std lib!