Proposal: priority queues in containers

Ross Paterson ross at
Fri Mar 19 06:26:29 EDT 2010

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

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

More information about the Libraries mailing list