On 8/14/05, Frederik Eaton
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