Proposal: priority queues in containers

[Ross Paterson]

On Fri, Mar 19, 2010 at 10:52:10AM +0100, Stephan Friedrichs wrote:
> On 17/03/10 16:47, Ross Paterson wrote:
> > On Tue, Mar 16, 2010 at 08:54:15AM -0500, Louis Wasserman wrote:
> >> 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.
> > 
> > I disagree with this one.  It requires an Ord instance that isn't really
> > an ordering, and makes a Functor instance impossible.  I would prefer
> > an interface separating keys and values like that of Data.Map (which
> > would also increase consistency within the package).
> 
> I agree. The Functor instance is crucial (at least to me). Besides, I'm
> the author of [1] and writing that package, I made the experience that
> it absolutely makes sense to separate the part of a queue entry that
> determines it's position within the queue from the part that is user
> data. A clean Functor instance is just one of the benefits.

For a containers-compatible interface (ignoring the implementation), see

http://hackage.haskell.org/packages/archive/fingertree/0.0.1.0/doc/html/Data-PriorityQueue-FingerTree.html

>  * I'm not comfortable with having two redundant modules, one for Min-
> and one for MaxQueue. It is possible to implement both in the same data
> structure and still get type errors when e.g. 'union' on a Min- and a
> MaxQueue (I did that in [1], please have a look at the latest version).
> My solution needs type families, which would not be good for containers,
> but I'm pretty sure there's a containers-compatible solution.

If keys are separate, the two versions could be easily achieved using
an inversion adaptor on Ord, which has been proposed before and would
have many other uses.