search

jaspervdj / psqueues

Priority Search Queues in three different flavors for Haskell
https://hackage.haskell.org/package/psqueues
Other
64 stars 24 forks source link

add mapPrioritiesMonotonic #20

Closed crclark closed 7 years ago

crclark commented 7 years ago

I found myself needing this. It is, of course, much faster than using fold' and alter to achieve the same purpose.

I tried to imitate the naming convention and documentation of mapKeysMonotonic for Data.Map in containers.

jaspervdj commented 7 years ago

I think adding a function like this makes sense, thanks for putting this together! There are a couple of issues though.

HashPSQ.mapPrioritiesMonotonic is not O(n), or at least not as fast as people will expect it to be, because it uses IntPSQ.map under the hood.

If we want to avoid doing that, we could consider also changing the values, since that doesn't change the structure of the tree either. While we're at it, it doesn't seem like a bad thing to give the higher-order function access read-only to the priority. At this point, it becomes, for all PSQ flavours:

mapMonotonic :: Constraints => (k -> p -> v -> (p, v)) -> SomePSQ k p v -> SomePSQ k p v

What do you think? We will also need some tests covering this new function.

crclark commented 7 years ago

@jaspervdj That sounds much better 👍. I'll fix it up.

crclark commented 7 years ago

I switched to the more general type, improved the code for HashPSQ, and added a test. Thanks for the feedback!

jaspervdj commented 7 years ago

Thanks! I decided to rename it to unsafeMapMonotonic to be a bit more consistent with the rest of the library (functions with unchecked invariants are named "unsafe").