<div>First off: I've finally gotten set up with <a href="http://code.haskell.org">code.haskell.org</a>. A darcs repo of my binomial heap implementation is at <a href="http://code.haskell.org/containers-pqueue/">http://code.haskell.org/containers-pqueue/</a>. Also on that site is the <a href="http://code.haskell.org/containers-pqueue/containers-0.3.0.0/html/">haddock documentation</a>, which I'm sure many people will appreciate. Somebody else (Ross?) had requested a separate version of the priority queue to handle priorities and values separately, so I'm working on that.</div>
<meta http-equiv="content-type" content="text/html; charset=utf-8"><div>I've also deleted the Foldable instance of MinQueue, though I still offer a clearly documented unordered toList, which will stay in place.</div>
<div>
<br></div><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
Well, I only tested one thing (heap sort), and QuickBinom is actually</blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
faster under different options (-prof -auto-all or without calling<br>performGC before every heapsort).</blockquote>-prof -auto-all blocks a significant number of optimizations from actually happening. Essentially, if the compiler has to figure out how much time is taken by some particular function, then it's not allowed to inline or eliminate uses of that function. I don't consider it a fair comparison. Moreover, calling performGC makes sense -- it essentially wipes the slate, making each successive comparison unbiased by the previous one.<div>
<br></div><div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Louis, you note later in this email that your implementation is done.<br>
That seems important to me. If we fix a sane interface now, the<br>
implementation can be changed later if we find something more<br>
efficient, right?<br></blockquote><div><br></div><div>Absolutely true. </div></div><br></div><div>However, I finally assembled a benchmark that I think is a fair comparison -- a heapsort, essentially "length . Data.List.unfoldr extract . foldr insert empty". The <a href="http://code.haskell.org/containers-pqueue/bench-chart.pdf">results</a> are pretty supportive of my implementation. (Original timing data, outputted by Progression, is <a href="http://code.haskell.org/containers-pqueue/bench-final.csv">here</a>. I think all of the original code for the benchmark is in the <a href="http://code.haskell.org">code.haskell.org</a> folder, just not part of the darcs repo. However, I had to slightly modify my copy of Progression to force the GC, so YMMV.)</div>
<div><br></div><div>I'm still pretty strongly in favor of putting priority queues into containers: other programming languages consider it necessary for inclusion into standardized libraries, people will be more likely to use appropriate data structures for their needs when reliable, friendly implementations are already at their fingertips, and other reasons already discussed.</div>
<div><br></div><div>In general, I think priority queues should be treated the same as Data.Map or Data.Set, like java.util.* or the C++ STL treat their respective versions of those structures. I don't think there's likely to be any agreement any time soon to split up containers, so my inclination is to put pqueues into containers, and maybe if we agree later to split containers, then priority queues will be part of that decision.</div>
<div><br></div><div>On a somewhat different note: writing unit tests in the existing framework is awkward and hard! Writing QuickCheck tests is trivial and much more exhaustive than what the existing tests look like. The existing containers tests appear to check one particular example that was the source of a preexisting bug, rather than examining exhaustively that methods work correctly, to eliminate potentially new bugs. I mean, Data.IntSet's one existing test is</div>
<div><br></div><div>main = print $ isProperSubsetOf (fromList [2,3]) $ fromList [2,3,4]</div><div><br></div><div>which might have found some preexisting bug, but certainly doesn't convince me of Data.IntSet's correctness. </div>
<div><br></div><div>Is this normal? Is it permissible to use QuickCheck inside unit tests? (A collection of QuickCheck tests -- all of which my implementation passes -- is in the <a href="http://code.haskell.org">code.haskell.org</a> directory.)</div>
<div><br></div><div>Louis Wasserman</div>