Open Boarders opened 4 years ago
@Boarders Good question! What is the use case here? More concretely, what would the type of this insertWith
be? How would it change the priority if the "to be inserted" priority differs from the priority that's already there?
In my use case I am only using:
type HashPSQ' = HashPSQ k p ()
and I hoped a function of the form:
insertWith :: (Ord k, Hashable k, Ord p) -> (p -> p -> p) -> k -> p -> HashPSQ k p v -> HashPSQ k p v
Maybe this is a hopeless thing to ask for and the best one can do is simply delete the element if present and then reinsert?
I think the best way to do this is using the existing alter.
The goal of psqueues
is somewhat different than e.g. Data.Map
-- we don't really aim to cover the entire space of possible operations, we just expose the core operations that users can build on and some extra operations prefixed with unsafe
that can be used to speed things up if certain preconditions are true.
I'm not sure if there's a way to write an insertWith
that is much faster than alter
unless there are some preconditions here (e.g. the priority will never be decreased, the item is not present...). I would also expect a "general" insertWith
to be able to modify the value; so the higher-order function passed in would be closer to p -> v -> p -> v -> (p, v)
.
That makes sense, In my case I am also only ever increasing the priority but I'm not sure if this is too much of a special case. The sort of situation it comes up is in building something like a frequency table as a priority search queue, if the key is already present then you want to be able to increase it's priority.
Would it be possible to provide insertWith functions. I am not sure enough about the internals to know how feasible this is.