Proposal: priority queues in containers
ross at soi.city.ac.uk
Wed Mar 17 11:47:37 EDT 2010
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).
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
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.
More information about the Libraries