Libraries Digest, Vol 79, Issue 31

Louis Wasserman wasserman.louis at
Fri Mar 19 09:39:41 EDT 2010


>  * 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

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
  (The source code and data for this benchmark version are now in the 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 at
-------------- next part --------------
An HTML attachment was scrubbed...

More information about the Libraries mailing list