Whoops, meant to send this to the whole libraries list.<br><br>What do people think of this implementation and approach? It's got O(log n) union and all. I think it could even be made stable, with some thought...<br>
<br clear="all">Louis Wasserman<br><a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a><br><a href="http://profiles.google.com/wasserman.louis">http://profiles.google.com/wasserman.louis</a><br>
<br><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Louis Wasserman</b> <span dir="ltr"><<a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a>></span><br>
Date: Wed, Mar 3, 2010 at 8:06 PM<br>Subject: Re: Improving containers library<br>To: Milan Straka <<a href="mailto:fox@ucw.cz">fox@ucw.cz</a>><br><br><br>Hokay, check it out: <a href="http://hackage.haskell.org/trac/ghc/ticket/3909" target="_blank">http://hackage.haskell.org/trac/ghc/ticket/3909</a><br>
<br>I just started this ticket to get going on adding priority queues to containers.<br>
<br>I spent probably way too much time today working on implementing binomial queues in Haskell <i>well</i>. I think that while my code needs cleaning up, my data structures are just about perfect. The way I wrote it, that my program type-checks provides serious evidence that it's written correctly.<br>
<br>data PQueue a = Empty | PQueue {-# UNPACK #-} !Int a !(BinomHeap a)<br><div style="margin-left: 40px;">-- It's based on a binomial heap augmented with a global root, so PQueue n x forest is a queue <br>-- with size n, with global root x, and with its other elements in the binomial heap<br>
</div>type BinomHeap a = BinomForest a ()<br>data BinomForest a ch<br><div style="margin-left: 40px;">= Nil | Skip !(BinomForest' a ch) | Cons !(Bin a ch) !(BinomForest' a ch)<br></div><div style="margin-left: 40px;">
-- BinomForest a ch represents a binomial forest with roots having some minimum rank k, in which the keys have type 'a' <br>-- and the set of children of a root of rank k has type 'ch'. BinomForest' a ch is the type of a binomial forest, starting at rank <br>
-- k+1.<br></div>type BinomForest' a ch = BinomForest a (Children a ch)<br><br>data Bin a ch = Bin a ch<br><div style="margin-left: 40px;">-- If ch corresponds to the children of a binomial node of rank k, then this is a binomial node of rank k.<br>
</div>data Children a ch = Children {-# UNPACK #-} !(Bin a ch) ch<br><div style="margin-left: 40px;">-- At rank k, ch will have the form Children a (Children a (... (Children a ())...)) with depth k. Then values of this type,<br>
-- written out, look like Children tk1 (Children tk2 (....(Children tkk ())...)), where tki is a binomial tree of rank (k-i).<br>-- This is exactly how the children of a binomial tree of rank k work.<br><br></div>Observe that subtrees in Children are written in descending order of rank, while subtrees in BinomForest are written in ascending order of rank. When we delete-min on a binomial heap, we'll need to merge the children of the smallest root with the rest of the roots, but merging only works when we have two ascending-rank sequences. This might cause some problems, except for a lovely workaround: we merge the children of the smallest root into the rest of the roots as we work backwards. With laziness, we can get away without even knowing whether or not our current candidate is the smallest root.<br>
<br>As a result, we get something that type checks perfectly -- which guarantees that roots of the correct rank are being assembled properly. Furthermore, we maintain all of the amortized bounds, without problems.<br><br>
I'm not entirely sure how different the performance would be in a more traditional, less type-safe implementation -- for one thing, we might be able to skip the "Skip" constructor in BinomForest, so when the heap had 2^n elements we'd only have to traverse a single root. However, this approach allows a lot of constructors to be unpacked nicely, which has nontrivial advantages, to say nothing of the correctness guarantees.<div class="im">
<br>
<br clear="all">Louis Wasserman<br><a href="mailto:wasserman.louis@gmail.com" target="_blank">wasserman.louis@gmail.com</a><br><a href="http://profiles.google.com/wasserman.louis" target="_blank">http://profiles.google.com/wasserman.louis</a><br>
<br><br></div><div><div></div><div class="h5"><div class="gmail_quote">On Wed, Mar 3, 2010 at 1:29 PM, Louis Wasserman <span dir="ltr"><<a href="mailto:wasserman.louis@gmail.com" target="_blank">wasserman.louis@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div>Hehehehe.<br><br>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)).<br>
<br>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.<br><br clear="all"></div>
<div>Louis Wasserman<br>
<a href="mailto:wasserman.louis@gmail.com" target="_blank">wasserman.louis@gmail.com</a><br><a href="http://profiles.google.com/wasserman.louis" target="_blank">http://profiles.google.com/wasserman.louis</a><br>
<br><br></div><div class="gmail_quote"><div>On Wed, Mar 3, 2010 at 1:16 PM, Milan Straka <span dir="ltr"><<a href="mailto:fox@ucw.cz" target="_blank">fox@ucw.cz</a>></span> wrote:<br></div><div><div></div>
<div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi,<br>
<br>
if I understand the function "fusing" correctly, you use the multi-pass<br>
variant of a pairing heap? Personally I thought more in the lines of<br>
a two-pass lazy variant of pairing heap mentioned in Okasaki's book.<br>
And there are skew heaps... Well, we'll let a benchmark do the judging :)<br>
<br>
Thanks,<br>
Milan<br>
<div><div></div><div><br>
> Yo,<br>
><br>
> If you're interested in adding priority queues to containers, shameless<br>
> plug: I've got a good implementation of pairing heaps in<br>
> <a href="http://hackage.haskell.org/package/queuelike" target="_blank">http://hackage.haskell.org/package/queuelike</a>. It's a bit obfuscated right<br>
> now, but I'd definitely be interested in producing something that's actually<br>
> readable and usable enough to be put into containers...<br>
><br>
> Louis Wasserman<br>
> <a href="mailto:wasserman.louis@gmail.com" target="_blank">wasserman.louis@gmail.com</a><br>
> <a href="http://profiles.google.com/wasserman.louis" target="_blank">http://profiles.google.com/wasserman.louis</a><br>
><br>
><br>
> On Wed, Mar 3, 2010 at 11:28 AM, <<a href="mailto:libraries-request@haskell.org" target="_blank">libraries-request@haskell.org</a>> wrote:<br>
><br>
> > Re: Improving containers library<br>
> ><br>
<br>
</div></div>> _______________________________________________<br>
> Libraries mailing list<br>
> <a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br>
> <a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
<br>
</blockquote></div></div></div><br>
</blockquote></div><br>
</div></div></div><br>