Offer untopped queues

[treeowl]

BinomHeap can easily be wrapped up in a newtype to offer basic binomial queues that don't track size and don't store the minimal entry separately. For some applications, such as heapsort, this should be significantly more efficient. Let's do it.

[treeowl]

I've done this now (for plain min-queues); there were no real difficulties. But as it is, there's a lot of code duplication. The fix, I think, is to define

data MinQueue a = Empty | MinQueue {-# UNPACK #-} !Int !a !(BMinQueue a)

where BMinQueue is the "untopped" queue. For certain purposes, we'll need a conversion function from BMinQueue to MinQueue that extracts the minimal element and calculates the size. We could do those together, but I'm not sure it's worth the trouble. Even without that, I think a number of functions (partitions, say) will get faster, because it's more efficient to build a large untopped queue and then extract its minimum than to build a large topped queue. O(n) fewer comparisons, and probably also O(n) less allocation.

[konsumlamm]

Hmm, I'm really not sure what to think of this one. On one hand, more efficient functions sound good, but otoh I'd really like to avoid the code duplication.

I don't think the average pqueue user would use such an untopped queue, nor do I think that heapsort is a common application (there are better sorting algorithms). So maybe this should be in an internal module or a separate package? However, that still doesn't avoid the code duplication...

[konsumlamm]

Isn't a BMinQueue just a BinomHeap anyway? So we don't really need new types/modules if we just want more efficient operations.

[treeowl]

The code duplication is gone. That was just an intermediate stage. I think the overall situation is much better now. Wouldn't this untopped version also be better for shortest path algorithms?

[treeowl]

Isn't a BMinQueue just a BinomHeap anyway? So we don't really need new types/modules if we just want more efficient operations.

Yes, a BMinQueue is a BinomHeap. It's an actual binomial queue, rather than one augmented with extra stuff. But giving it a newtype wrapper has at least two big benefits:

1. It can be treated as a proper abstract datatype.
2. We can give it typeclass instances.

I think these are both necessary and sufficient for principled use outside the package. As you can see from the PR, (1) is also quite useful within the package, where it lets us write compare much more succinctly.

To repeat what I said above, the untopped queues aren't just for sorting. They're for pretty much any algorithm that doesn't need to be able to peek at the minimal element in O(1) time and does not see mostly decreasing keys. This includes, at least, shortest path algorithms and k-way merge algorithms. Untopped queues are particularly beneficial when comparisons are not extremely cheap.

[konsumlamm]

The code duplication is gone. That was just an intermediate stage. I think the overall situation is much better now.

Fair, it is better now. However, we still have twice the functions (that we need to maintain). While I don't see a way to avoid this, I still don't like it.

Wouldn't this untopped version also be better for shortest path algorithms?

Those usually also use "decrease priority" operations (at least Dijkstra's algorithm does) which our priority queues don't provide, so I'm not sure how those would best be implemented using pqueue anyway. But apart from that you're right.

But giving it a newtype wrapper has at least two big benefits:

Makes sense.

To repeat what I said above, the untopped queues aren't just for sorting.

I just mentioned heapsort because you listed it as an argument for this change.

They're for pretty much any algorithm that doesn't need to be able to peek at the minimal element in O(1) time and does not see mostly decreasing keys. This includes, at least, shortest path algorithms and k-way merge algorithms. Untopped queues are particularly beneficial when comparisons are not extremely cheap.

Yeah, I think many algorithms would benefit from this (at least in theory), but we should have benchmarks to verify that (#48). One problem I see is that with untopped/bare queues, it may be hard for the users to decide which version they want (perhaps you don't know beforehand whether you'll need O(1) size/getMin, although ig you can just switch out the module).

[treeowl]

Since people might well want to experiment with whether they want bare queues or augmented queues, it might be better to give the types the same names. I'm thinking I should rename Data.PQueue.Bare to Data.BinomialQueue (or just BinomialQueue? That seems to be the current fashion) and make the types MinQueue and so on.

[treeowl]

For reasons I really, really don't understand, the bare queues don't do well on the k-way merge benchmark. What am I missing?