Stream: contributing

Topic: Set.keepIf and Set.dropIf


view this post on Zulip LoipesMas (Dec 03 2023 at 21:52):

Since Set is implemented through Dict, I wonder if keepIf and dropIf should also be implemented for Dict and then just used in Set. But I'm not sure if Dict.keepIf's predicate would take just key or key and value? Or maybe it doesn't make sense for Dict to have those functions? What do you think? @Richard Feldman

view this post on Zulip Richard Feldman (Dec 03 2023 at 21:56):

I think it makes sense; I'd say the Dict one should get two arguments, one for key and one for value

view this post on Zulip LoipesMas (Dec 03 2023 at 21:57):

That's what I thought, thanks!

view this post on Zulip LoipesMas (Dec 03 2023 at 22:21):

I see three possible implementations for Dict.keepIf:

  1. Create an empty dict and insert keys and values that fit the predicate
  2. Use input dict and remove values that don't fit the predicate
  3. List.keepIf on the data and then Dict.fromList

With current Dict.fromList implementation, 1. would be the same as 3., just written out, so it doesn't really make sense. But I'm not sure if using input dict and using Dict.remove would allow us to avoid allocations (i.e., mutate in-place if the input dict isn't used later). If yes, that would probably be better, right? But 3. is cleaner and when Dict.fromList gets optimized it might be faster than removals. Or am I overthinking this and I should just go with the simplest solution?

view this post on Zulip Brendan Hansknecht (Dec 03 2023 at 22:22):

  1. Use input dict and remove values that don't fit the predicate

view this post on Zulip Brendan Hansknecht (Dec 03 2023 at 22:22):

I would definitely pick that

view this post on Zulip Brendan Hansknecht (Dec 03 2023 at 22:23):

Yeah, should be able to mutate in place if written correctly (that actually might be a bit tricky to do right). And should keep the dictionary capacity around which will help with perf. Don't need to re-allocate a bunch.

view this post on Zulip Brendan Hansknecht (Dec 03 2023 at 22:29):

To clarify why this may be quite tricky. To walk the list to figure out what to remove, you would need to keep a reference to the original list. That would stop mutation. Instead, you probably have to manually write a recursive function that just takes an index. If an item is removed, the index won't update. If it isn't it will. So a bit more complex.

view this post on Zulip LoipesMas (Dec 03 2023 at 22:35):

Indeed, sounds tricky. That's what I get for picking a "very easy" task ;p But I'll give it a try!

view this post on Zulip Brendan Hansknecht (Dec 03 2023 at 22:45):

If you want, just write the naive way and it can be upgraded later.


Last updated: Jul 05 2025 at 12:14 UTC