Dear Library colleagues

 

It’s not very easy to find http://haskell.org/haskellwiki/Library_submissions, the Haskell library submission process.

 

Starting at haskell.org I thought that the “standard libraries” link should do the job, but it doesn’t.  Maybe the standard libraries link should lead to a page that points to the Haddock stuff but also gives other info such as how to submit changes?  I don’t believe I know how to edit the main page, or even if I should, so I’m just emailing the suggestion

Simon

 

From: Louis Wasserman [mailto:wasserman.louis@gmail.com]
Sent: 16 March 2010 13:41
To: Simon Peyton-Jones
Subject: Re: Feedback request: priority queues in containers

 

Bah.  Have done this before, but a while ago, and I couldn't find the page reminding me of the specific details of what to do for library submissions.

 

Thanks!


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

On Tue, Mar 16, 2010 at 8:34 AM, Simon Peyton-Jones <simonpj@microsoft.com> wrote:

Louis: If you want to propose changes to standard libraries, there’s a well-documented procedure.  (Of course, if you just want to release a package of your own there’s no procedure!)


http://haskell.org/haskellwiki/Library_submissions

 

Simon

 

From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users-bounces@haskell.org] On Behalf Of Louis Wasserman
Sent: 16 March 2010 13:29
To: glasgow-haskell-users@haskell.org
Subject: Feedback request: priority queues in containers

 

Hey,

 

I'd like to request some more feedback on the proposed 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!  

 

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.

 

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

  • O(log n) worst-case union
  • O(log n) worst-case extract (this in particular was a key objective of ours)
  • amortized O(1), worst-case O(log n) insertion.  (In a persistent context, the amortized performance bound does not necessarily hold.)

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.)

 

A couple potentially contentious design decisions:

  • 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.
  • Min-queues and max queues are separated the following way:
    • Data.PQueue.Min exports the type MinQueue.
    • 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.
    • Data.PQueue adds the alias type PQueue = MinQueue, so that the "default" behavior is a min-queue.

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 implementation, which makes the same design decisions, but of course, is all imperative and yucky!  (Also, it offers inferior asymptotics, heh.)

 

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:

  • 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.
  • q !! k is equivalent to toAscList q !! k.
  • 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.)
  • 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.)
  • 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.)
  • Correspondingly, we export toList, toAscList, toDescList, fromList, fromAscList, fromDescList.  (toList returns an *unordered* traversal, and is *not* equivalent to toAscList.)

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.

 

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. =)