Proposal: priority queues in containers

Jim Apple jbapple+haskell-lib at
Mon Mar 22 01:12:54 EDT 2010

> My implementation has performed outstandingly on benchmarks,
> and has beaten a number of competitors.  If someone believes that they have
> a superior implementation, they should email me off-list

So far, the only benchmarks I have seen have been heapsorts. I think
it is worth at least discussing whether or not other benchmarks are
worth considering.

Heapsort, for instance, calls insert and extractMin the same number of
times. It also does not use the data structures persistently. It does
not necessarily test toUnsortedList or meld.

Furthermore, I think it is better to discuss performance comparisons
and requirements in the open, rather than in private off-list emails.
Louis, if you're too busy to engage in additional performance
discussion on this list, I'm sure nobody will think less of you for

Finally, I agree with Louis that there is probably no rush to get the
implementation perfect before fixing an interface. I just think we
should carefully work to measure and improve priority queue
performance out in the open.

More information about the Libraries mailing list