Hehehehe. Actually, in retrospect, most of the data structures in containers are relatively strict -- they typically won't defer work, and support worst-case performance as opposed to amortized. (Sequence is the exception, but worst-case O(log n) is much nicer than worst-case O(n)). My thinking now is along the lines of a relatively strict binomial heap implementation, with maybe an extra module for pairing heaps when worst-case runtime is less important than overall speed. Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis On Wed, Mar 3, 2010 at 1:16 PM, Milan Straka wrote:

Hi,

if I understand the function "fusing" correctly, you use the multi-pass variant of a pairing heap? Personally I thought more in the lines of a two-pass lazy variant of pairing heap mentioned in Okasaki's book. And there are skew heaps... Well, we'll let a benchmark do the judging :)

Thanks, Milan

...

Yo,

If you're interested in adding priority queues to containers, shameless plug: I've got a good implementation of pairing heaps in http://hackage.haskell.org/package/queuelike. It's a bit obfuscated right now, but I'd definitely be interested in producing something that's actually readable and usable enough to be put into containers...

Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis

On Wed, Mar 3, 2010 at 11:28 AM, wrote:

...

Re: Improving containers library

...

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

On March 3, 2010 14:54:17 Stephan Friedrichs wrote:

On 03/03/10 19:24, Louis Wasserman wrote:

...

If you're interested in adding priority queues to containers, shameless plug: I've got a good implementation of pairing heaps in http://hackage.haskell.org/package/queuelike. It's a bit obfuscated right now, but I'd definitely be interested in producing something that's actually readable and usable enough to be put into containers...

I've also worked on priority queues: http://hackage.haskell.org/package/heap - maybe that project can be of help. Let the games begin! ;)

To jump in without having paid much attention to the thread (i.e., please ignore this if the comment is total useless). There was a paper awhile back on functional implementation of priority search queues called "A Simple Implementation Technique for Priority Search Queues". http://portal.acm.org/citation.cfm?id=507650 Cheers! -Tyson