Hey,<div><br></div><div>I'd like to request some more feedback on the <a href="http://hackage.haskell.org/trac/ghc/ticket/3909">proposed</a> implementation for priority queues in containers. Mostly, I feel like adding a new module to containers should be contentious, and there hasn't been as much griping or contention as I expected. The silence is feeling kind of eerie! </div>
<div><br></div><div>I'm inclined to set a deadline of next Wednesday, Mar 24, because the ticket was started two weeks ago and the current implementation has been essentially unchanged for a week. After that point, I'll consider the patch final.</div>
<div><br></div><div>The proposed implementation benchmarked competitively with every alternative implementation that we tested, and offers good asymptotics in nearly every operation. Specifically, we use a binomial heap, which offers</div>
<div><ul><li>O(log n) worst-case union</li><li>O(log n) worst-case extract (this in particular was a key objective of ours)</li><li>amortized O(1), worst-case O(log n) insertion. (In a persistent context, the amortized performance bound does not necessarily hold.)</li>
</ul><div>This implementation seems to offer the best balance between practical performance and asymptotic behavior. Moreover, this implementation is extremely memory-efficient, resulting in better performance on large data sets. (See the ticket for benchmarks. The most accurate benchmarks are towards the end.)</div>
<div><br></div><div>A couple potentially contentious design decisions:</div><div><ul><li>There is no distinction between keys and priority values. A utility type Prio p a with the instance Ord p => Ord (Prio p a) is exported to allow usage of distinct keys and priority values.</li>
<li>Min-queues and max queues are separated the following way:</li><ul><li>Data.PQueue.Min exports the type MinQueue.</li><li>Data.PQueue.Max exports the type MaxQueue. (This is implemented as a wrapper around MinQueue.) The method names are the same, but I think this is acceptable, because I can't think of any algorithms that use a min-queue and a max-queue separately.</li>
<li>Data.PQueue adds the alias type PQueue = MinQueue, so that the "default" behavior is a min-queue.</li></ul></ul><div>These design decisions seem to be sufficient to handle most traditional uses for priority queues. In particular, this approach offers a superset of the functionality offered by Java's built-in priority queue <a href="http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html">implementation</a>, which makes the same design decisions, but of course, is all imperative and yucky! (Also, it offers inferior asymptotics, heh.)</div>
<div><br></div><div>I made a particular effort to offer the sort of utility functions that are found in the other modules of containers. In particular, it offers:</div><div><ul><li>take, takeWhile, span, and that whole family of functions. take k q returns the *list* of the top k elements, and drop k q returns the *queue* with the first k elements deleted. The rest of these methods have analogous signatures.</li>
<li>q !! k is equivalent to toAscList q !! k.</li><li>filter and partition are offered in O(n) time. (It's actually not obvious that my implementation actually runs in O(n) time, but I managed to prove it.)</li><li>
We offer Functor, Foldable, and Traversable instances that do not respect key ordering. All are linear time, but Functor and Traversable in particular assume the function is monotonic. The Foldable instance is a good way to access the elements of the priority queue in an unordered fashion. (We also export mapMonotonic and traverseMonotonic, and encourage the use of those functions instead of the Functor or Traversable instances.)</li>
<li>We offer foldrAsc, foldrDesc, foldlAsc, and foldlDesc. (Descending-order operations are just implemented as duals of the ascending-order operations, for MinQueue. For MaxQueue, it's the other way around.)</li><li>
Correspondingly, we export toList, toAscList, toDescList, fromList, fromAscList, fromDescList. (toList returns an *unordered* traversal, and is *not* equivalent to toAscList.)</li></ul><div>I'm really satisfied with the patch as-is, modulo maybe tinkering with the code style a little. I'm also working on an article for TMR on priority queues in Haskell, some of the different structures we considered, and particularly the new type-safety implementation I came up with for binomial heaps in the writing of this implementation.</div>
<div><br></div><div>In conclusion, I want to be sure people actually like this approach! So check it out. Complaints are appreciated, but even "I think your implementation is absolutely perfect" would reassure me. =)</div>
<div><br></div></div></div></div><div>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>
</div>