Proposal: priority queues in containers

[Stephan Friedrichs]

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.

> Other comments:
> 
> The Foldable instance breaks the abstraction.  I think it should process
> elements in order.

Yes. I'd consider everything else a bug.

> 
> [...]
> 

Other points are:

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

 * Not so important, but IMHO 'extract' should be called 'view', because
that's, how this sort of function is usually called, isn't it? ;)

Regards,
Stephan

[1] http://hackage.haskell.org/package/heap