Stream: beginners

Topic: List & Dict pop?

Aurélien Geron (Sep 13 2024 at 08:22):

Is there an efficient & concise way to pop a value from a List or a Dict?

Right now I'm using this function for List:

popFirst : List a, (a -> Bool) -> (a, List a)
popFirst = \list, condition ->
    index = list |> List.findFirstIndex? condition
    maybeValue = list |> List.get index
    value = when maybeValue is
        Ok val -> val
        Err OutOfBounds -> crash "Unreachable, we just found the value's index"
    updatedList = list |> List.dropAt index
    Ok (value, updatedList)

And a similar helper function for Dict.

Sam Mohr (Sep 13 2024 at 08:31):

Pretty sure we don't, the closest is replace?. We should probably add some swap_remove equivalent function.

Kilian Vounckx (Sep 13 2024 at 09:23):

I guess you could use List.walkWithIndexUntil:

popFirst : List a, (a -> Bool) -> Result (a, List a) [NotFound]
popFirst = \list, condition ->
    List.walkWithIndexUntil list (Err NotFound) \_, element, index ->
        if condition element then
            Break (Ok (element, List.dropAt list index))
        else
            Continue (Err NotFound)

Aurélien Geron (Sep 13 2024 at 10:14):

Nice solution

Brendan Hansknecht (Sep 13 2024 at 15:33):

If possible, swapping the found element with the last element in the list before removing should be more performant

Aurélien Geron (Sep 13 2024 at 20:54):

Why is that?

Aurélien Geron (Sep 13 2024 at 20:55):

Side note: it might be useful to have a "performance tips" page in the docs (unless it already exists?).

Brendan Hansknecht (Sep 13 2024 at 22:17):

If you delete an element in the middle of the list, it will shift all elements following to close the gap and keep the list contiguous.

Brendan Hansknecht (Sep 13 2024 at 22:17):

If you swap and then delete. No other data has to move around besides the swapped elements.

Brendan Hansknecht (Sep 13 2024 at 22:18):

So moving 1 vs n elements

Aurélien Geron (Sep 13 2024 at 22:53):

I see, thanks, but this only works if we don't care about the order of the elements in the list.

Sam Mohr (Sep 13 2024 at 23:01):

Aurélien Geron said:

I see, thanks, but this only works if we don't care about the order of the elements in the list.

The alternative is a linked list, which is O(n) to traverse for the element, but O(1) to remove

Sam Mohr (Sep 13 2024 at 23:04):

However, it's probably not worth doing a linked list, array-backed lists are more efficient for most use cases

Brendan Hansknecht (Sep 14 2024 at 00:58):

I would expect a linked list to lose about 100% of the time for this search then remove algorithm. But it depends on the exact use case. If it truly is a random element in the middle of the list, I would expect the linked list to be terrible.

Brendan Hansknecht (Sep 14 2024 at 01:01):

But yeah, sometimes order matters. When that happens, start with a regular list and just remove the element... shifting everything. It has a cost, but until you get to a large n, is still probably faster than basically everything.

Aurélien Geron (Sep 14 2024 at 02:39):

A Collections package with alternative list implementations, like unrolled linked lists, B-trees, deque, skip lists, gap buffers, etc. would be nice. Perhaps also Counter and DefaultDict, which are two of my favorites in Python.

Brendan Hansknecht (Sep 14 2024 at 02:50):

"unrolled"?

Luke Boswell (Sep 14 2024 at 02:50):

https://github.com/Subtlesplendor/roc-data

I think @Johan Lövgren started on this

Brendan Hansknecht (Sep 14 2024 at 02:51):

Oh, googled it, multiple elements per node linked list.

Brendan Hansknecht (Sep 14 2024 at 02:57):

Personally, I would push away from a generic catch all for data structures. Often turns more into an algorithmic jungle of hopes in big O rather than a handful of simple and powerful data structures that can do most heavy lifting if used well.

Brendan Hansknecht (Sep 14 2024 at 02:57):

But obviously anyone can implement whatever roc packages they please.

Brendan Hansknecht (Sep 14 2024 at 02:57):

And more roc experimentation and code is always good.

Aurélien Geron (Sep 14 2024 at 03:27):

Good point Brendan, I really like the Unix philosophy of doing one thing and doing it well. Roc is a great language for that because packages cannot do bad things outside of their scope, so anyone can try out unknown packages without fear.

Johan Lövgren (Sep 14 2024 at 06:29):

Yes I did some simple things like that, mostly for fun. I also prefer the standard library to be as simple as possible.

Johan Lövgren (Sep 14 2024 at 06:35):

Though admittedly there is a bit of paradox to library defined data structures. As in, “the user should not care about how this queue is defined internally” clashes with the need to know the actual performance

Last updated: Jul 26 2025 at 12:14 UTC