search

lspitzner / pqueue

Haskell priority queue package
Other
15 stars 13 forks source link

mapMaybe and mapEither are completely wrong #110

Closed treeowl closed 1 year ago

treeowl commented 1 year ago

It looks like someone took (very clever; rather tricky to understand) code for filter and partition (which would also work for the plain mapMaybe in the Prio case) and generalized it to mapMaybe, mapEither, mapMaybeWithKey, and mapEitherWithKey. Unfortunately, the generalization is totally bogus; the order of keys in the result is not, in general, related to the order of keys in the argument.

treeowl commented 1 year ago

I believe all these key-mapping functions should just perform unordered folds over the queue to build a new queue. But we may want to rescue the fancy code to directly implement the functions for which it is valid. I believe it's designed to minimize comparisons; whether it's more efficient in practice is less obvious.

treeowl commented 1 year ago

We can probably rename the bogus functions to add the word Monotonic, making them correct.