Improving containers library

[Louis Wasserman]

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 at gmail.com
http://profiles.google.com/wasserman.louis


On Wed, Mar 3, 2010 at 1:16 PM, Milan Straka <fox at ucw.cz> 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 at gmail.com
> > http://profiles.google.com/wasserman.louis
> >
> >
> > On Wed, Mar 3, 2010 at 11:28 AM, <libraries-request at haskell.org> wrote:
> >
> > > Re: Improving containers library
> > >
>
> > _______________________________________________
> > Libraries mailing list
> > Libraries at haskell.org
> > http://www.haskell.org/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100303/b8eeac8f/attachment-0001.html