Equality for priority queues

#23

My suggestion would be to accept that, on what I would consider degenerate inputs, == runs in quadratic time [1]. If for whatever reason that is unacceptable in an application: the user should switch to a different type of priority queue that supports lookup queries so that one can keep elements with the same key in whatever particular order is desired. (I.e. if you somehow care enough that == should maintain the insertion order, picking an implementation that cannot reasonably maintain that order distinguished seems like a bad choice in DS in the first place).

I think having the Ord a constraint is bad since it restricts which type of elements one can store in the priority queue. It would seem to me there are much more types that have a reasonable Eq instance but no Ord instance. Admittedly, I’m having trouble producing concrete examples at the moment.

[1] Edit: Maybe to stress: in, “normal” operations where each key appears at most once (or even at most sqrt(log n)) times) == would just run in O(n log n) time as expected.

Edit 2: Actually, even if a few keys appears at most sqrt(n) times that is fine. I.e. as long as sum_i^k O(n_i^2) <= O(n log n) things are fine (where k is the number of unique keys and n_i is the number of keys equal to key i)

#24

So to be more explicit about my suggestion: A priority queue represents a set of (key, MultiSetOfElements) pairs, and two queues are equal if and only if their set of (key, MultiSetOfElements) is the same.

One can implement this in O(n log n + sum_{i=1}^k n_i^2) time as follows. For each queue repeatedly extract the minimum element, producing a list of (key,element) pairs that is ordered on key. Group the list into a list of (key, list) pairs on key. zip the two list representations comparing the (key,ListOfElement) pairs. To compare the two ListOfElements use the trivial naive O(n_i^2) time algorithm.

#25

I feel like tricking users into a quadratic algorithm is wretched. And having compare x y == EQ be potentially much faster than x == y is surprising and highly unpleasant. I’d rather just get rid of the (admittedly semantically shaky) instance and add standalone functions than do that.

1 Like
#26

I’m not advocating for using a slow quadratic algorithm. My preferred options rn are to keep the current instance or remove it. What makes the Ord a constraint evil imo is that it isn’t theoretically needed and it might exclude some types from checking for equality, even if the algorithm is unrealistically slow.

Using the Eq instance for testing is a good point though, and it is indeed how I discovered the issue in the first place. However, imo the current way of just comparing sorted lists works fine.

#27

The current instance is utter nonsense, as far as I can tell. I don’t believe it even guarantees

 p == q = True ===> insert k v p == insert k v q = True

Using plain structural equality is … an option. But I think it’ll be much more confusing than helpful.

#28

Okay, maybe that’s too strong. I suppose it makes extraction deterministic but insertion and union nondeterministic, dual to the instance I proposed. I hadn’t thought about it that way…

#29

Assuming that interpretation is right, I suppose we could keep the current instance, but we’d have to document it very carefully. However, I’m not convinced it’s useful for anything, even if it’s theoretically reasonable. What could you actually do with it?