Open treeowl opened 1 year ago
The only theoretical downside of the proposed change is that the queues become slightly nondeterministic. But I believe that nondeterminism is expected by the priority search queue abstract datatype in general. Since the expensive determinism was never even documented, I don't think anyone could legitimately have relied on it anyway.
My first thought was #40 , which just simplifies the expression of the current
Eq
implementation. But thinking about it some more, I think we should be able to do much better. In particular, there's no remotely obvious reason to work through the queues in priority order. It seems much simpler to do so in key order:Aside from being more efficient for implementing
(==)
, it looks like there's a rather bigger potential benefit. Elsewhere, we haveHmmmm. That's interesting. We're doing key comparisons in
lsingleLeft
,rsingleRight
, andplay
just to make this particularEq
instance work? Those are pretty hot, so that sounds pretty pricy. I checked the documentation to see ifminView
(or anything related) even advertises that it returns the smallest key first, and I could find no sign of that. So unless that's an independent goal, we just shouldn't do it!