Proposal: priority queues in containers

[Ross Paterson]

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

Other comments:

The Foldable instance breaks the abstraction.  I think it should process
elements in order.

How does this implementation compare with using Map/Set as a priority
queue?

The documentation for union should mention that it's not stable.  That's a
pity, but may be justified if there's a big performance difference with
the representations that support stable union.

I think the containers package should offer general extractor functions
with a parameter of type (a -> Maybe (b, a)), so we wouldn't need special
cases like these ones.