Yo,
* I'm not comfortable with having two redundant modules, one for Min- and one for MaxQueue. It is possible to implement both in the same data structure and still get type errors when e.g. 'union' on a Min- and a MaxQueue (I did that in [1], please have a look at the latest version). My solution needs type families, which would not be good for containers, but I'm pretty sure there's a containers-compatible solution.
I'm pretty sure there won't be a containers-compatible solution, certainly not a solution compatible with the style of containers as it's currently written, because your solution depends on exporting functionality with type classes. If we're going to change that style in containers, it should be done all at once, in a complete rewrite. Whether or not priority queues get added to containers, I'm at least going to keep the style *consistent* with containers. With regards to benchmarks, we examined a comparison with leftist heaps earlier. The biggest complaint is the O(log n) insert time, which is really kind of icky. Here was Milan's conclusion: LeftistByMilan is actually pretty good for small inputs (up to ~ 216), and
the implementation is super-trivial compared to Binomial. But when the list gets bigger, the complexity gets worse. I think this is beause of O(log N) inserts -- the Binomial implementation with O(1) amortized inserts allocates much less memory and does not need to run a GC. I vote for current (v5) Binomial implementation, even if the O(1) amortized inserts works only non-persistently (ie. under heavy persistent usage, leftist heaps might be a _little_ better).
Furthermore, I added your implementation to the benchmarks that we'd been using previously, which was essentially a full heapsort, rather than just searching for the five smallest elements as in your quickie benchmark. By this comparison, your implementation is moderately slowerhttp://code.haskell.org/containers-pqueue/bench-chart.pdf. (The source code and data for this benchmark version are now in the code.haskell.org/containers-pqueue directory.) Though your implementation might be faster for some particular cases of problems, I think this is a fair comparison overall, and I'm definitely not willing to accept leftist heaps' O(log n) insert time given the slower overall performance for heapsort. This is what the Haskell Platform is for. No real need to add more
stuff to containers; if anything, the libraries stored there should be decoupled so that e.g. the recent Data.Map proposals wouldn't disturb programs not using Data.Map.
Again, my preference is to add pqueues to containers, and then if containers gets decoupled, then so will priority queues. If I'm going to split off a separate package for priority queues, it'll be because I've been convinced that it ought to be separated from containers, period -- not just because people think containers should be broken up, and this is a good place to start. Meh. Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis