Priority Queues, or lack thereof

[Sebastian Sylvan]

On 8/14/05, Frederik Eaton <frederik at a5.repetae.net> wrote:
> I often find that when I want to use priority queues, I'm annoyed by
> the fact that I can't remove something which is not the minimum.
> Suppose I'm scheduling jobs and I want to cancel a job, etc. I can
> imagine that with an imperative data structure I could have it both
> ways - deletion of internal elements, and O(1) findMin. Is this not
> possible with a functional implementation?

Well you could get it at a fairly expensive cost. It is possible to
take, say, a finiteMap implementation and "adapt it" to have a
globally stored root which gets you O(1) findMin and (log n) for most
everything else.
This implementation gets optimal time complexities for other
operations as well, though. O(1) for everyting except deleteMin which
is (log n). O(1) for meld is, for example, quite neat.

> I see the same kind of argument ordering in Data.Map. Why is the data
> structure last? Usually one would think that the arguments should be
> ordered from "most constant" to "least constant" so that currying is
> as useful as possible. But surely the data structure is "more
> constant" than its elements, even (especially?) if it is persistent.

I would think that the most constant parameter is the ordering
function. The second most constant is debatable, but I tend to think
that it's more common to insert the same key into a list of priority
queues, for example, rather than insert different keys in to the same
priority queue (that is, as long as the queue is side-effect free)...

As a side note. After I posted this I found that the implementation of
Edison was a lot further along than expected (there just wasn't any
documentation). And apparently if you load the package "data" you get
access to all that (LazyPairingHeap seems to be faster than my
implementation).
I happen to think that any language with self respect needs a standard
data structures library. Even if "standard" is just de-facto standard.
Personally I think they should include at least one implementation of
all the regular data structures, along with the type class hierarchy
of Edison, in the hierarchical libraries. But barring that I'm willing
to settle for a nice Edison-like library with haddock documentation
and a cabalised installation.

I have a vague memory of running across a pseudo-complete data
structures library (not Edison) a while back, but I'm having trouble
finding it.

/S

-- 
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862