I'm currently putting the finishing touches on the first version of a new
priority queue package. It implements amortized-optimal priority queues and
is intended to compete with the heaps package with a simpler, more compact,
and hopefully faster implementation†. The main types are key-only and
key-value priority queues, which I'm naming based on the conventions of the
pqueue package:
data MinQueue k
data MinPQueue k a
data MaxQueue k
data MaxPQueue k a
Additionally, the implementation uses underlying types with constant time
insertion, logarithmic-time union, logarithmic time peekMin, and
logarithmic time deleteMin:
-- Key-value priority queues that are strict in both the key and the
-- value.
data MinPQueue k a
-- Similar to the above, but associating
-- two values with each key. The @a@
-- value is stored strictly and the @b@ value
-- is stored lazily.
data MinPQueue2 k a b
So I have a few questions:
1. What should I name this package?
2. What should I name the modules containing the bootstrapped queues?
3. What should I name the modules containing the underlying oddly-strict
queues? I don't know how many people will want to use them, but I figure
they're probably just what's needed from time to time and it's better to
let them loose than keep them under wraps.
Finally, there is the question of how to expose internals. In addition to
the queues above, with are all reasonable things for public consumption,
there are modules implementing those, as well as a couple modules
implementing helper types and such. I'm really no good at figuring out how
to "lay out" modules in a package, so any advice would be greatly
appreciated.
† The heaps package uses bootstrapped skew binomial heaps (Brodal and
Okasaki), achieving worst case constant-time union and peekMin and worst
case logarithmic time deleteMin. The package I'm working on uses the same
bootstrapping technique, but with a space-saving modification of Louis
Wasserman's realization of Okasaki lazy binomial heap as the base priority
queue. It achieves the same bounds, but union is only constant time in the
(persistently) amortized sense; it degrades to logarithmic time in the
worst case. In practice, this theoretical degradation likely doesn't
matter, both because it's small and because GHC's garbage collection
imposes occasional delays regardless.
