Two equal priority queues with keys can compare as unequal

[konsumlamm]

Two equal queues may compare as unequal, since duplicate keys are allowed and the Eq implementation takes only care of comparing the keys in order.

Example:

ghci> import qualified Data.PQueue.Min as PMin
ghci> PMin.fromAscList [(1, 'a'), (1, 'b')] == PMin.fromAscList [(1, 'b'), (1, 'a')]
False

This should be documented, as I don't think this can be fixed without making the implementation significantly slower.

[treeowl]

Hrmmmm..... Which operations don't respect ==?

[konsumlamm]

Hrmmmm..... Which operations don't respect ==?

I'm not sure what you mean, the issue is that entries with equal keys (but different values) may be in any order.

[treeowl]

The usual expectation is that if

f :: A -> B
x, y :: A
x == y = True

then

f x == f y = True

We say that f respects ==.

Typically, "safe" API functions should respect ==. If there's a relatively small and well defined set of operations that don't, that can be acceptable for the sake of practicality (see HashMap, for example, where two maps may compare equal even though converting them both to lists may produce differently ordered lists and they may be traversed in different orders). But if it turns out that the most essential priority queue operations don't respect ==, then that == will break everyone's intuition. In that case, it should preferably be changed, or if there's no way to do anything sensible then the Eq instance should likely be removed.

We should start by looking at how insertion and view interact with ==, since those are the most important operations.

[treeowl]

Similarly for binary operations. Given

a == a' = True
b == b' = True

users will want to be able to rely on

merge a b == merge a' b' = True

My bet is that the only ways to make sensible and abstract Eq instances for the Prio queues are to consider the results of minView (hence toList) and/or merge non-deterministic. Considering only minView non-deterministic is easy:

a == b = sort (toList a) == sort (toList b)

I believe we currently consider only merge non-deterministic in our Eq instance, which leads to very difficult/brittle code. So I think we should to the simple thing instead, if we want an Eq instance.

[konsumlamm]

So I did a bunch of (10000) QuickCheck tests and it seems that insert respects ==. I think before changing the Eq instance to (==) `on` (sort . toList), we should be sure that the current implementation is a problem.

[treeowl]

Try merges?

[konsumlamm]

With a better testing method, I actually found an example where insert doesn't respect ==:

ghci> import qualified Data.PQueue.Prio.Min as P
ghci> a = P.fromList [(0, 0), (0, 1), (-1, 0), (-1, 0)]
ghci> b = P.fromList [(-1, 0), (0, 0), (0, 1), (-1, 0)]
ghci> a == b
True
ghci> P.insert 0 0 a == P.insert 0 0 b
False

[treeowl]

Ouch. That's really nasty. I propose either:

1. Define a == b = (==) `on` sort . toList (or equivalent), and document that minView should be considered non-deterministic relative to ==.

2. Remove the Eq instance for Prio queues.

Can you think of any situation where it's essential to have an Eq instance for these things?

[konsumlamm]

Can you think of any situation where it's essential to have an Eq instance for these things?

Hmm, not really, though I feel a bit uneasy about removing an instance, as that would be a breaking change (which would be fine with a major version bump ig). I took a look at how other languages (C++, Java, Rust, Scala) handle this problem and it seems none of those implement custom equality for priority queues.

[treeowl]

Those languages are presumably using pointer equality. I believe the correct thing is the sorting ==, and documentation that these queues are "nondeterministic". That is, all the extraction and traversal functions may access values associated with a given key in any order.

[konsumlamm]

At least Rust and C++ don't, Scala 3 doesn't either afaict, Java always has a default implementation, so that's kinda unfair.

[treeowl]

So you prefer to remove the instance rather than implement the sorting one?

[konsumlamm]

I definitely prefer removing the instance over requiring Ord on the values, but I'm not sure that's my favourite option.

The alternative would be to fix the instance. We could compare the sizes and then iterate through the first argument and for each key-value pair look up if it also exists in the second argument. That would be slower, but it should work.

[treeowl]

That would give a pretty awful user experience, I think. We'd have p == q potentially much slower than compare p q == EQ.