On 5/5/11 2:31 AM, Brandon Moore wrote:

...

2011-5-4 8:53:50 PM, wren ng thornton On 5/1/11 7:58 PM, Edward Z. Yang wrote:

...

OK, to summarize the current discussion: - It would be nice to have a general-purpose priority queue in containers. I'm not interested in this goal per se, but I do view it as the cleanest way to get what I want.

With regards to this point, is there any reason why the following does not suffice (albeit not in base)?

http://code.google.com/p/priority-queues/

They're not priority *search* queues, but I'm not sure how much to read into your leaving out that word...

That word is pretty significant. In a priority queue every element also has a key, which can be used to efficiently remove it or adjust the priority.

That package wouldn't support cancelling a timeout, for example.

Yes, I know it's important. Which is why I brought up the question about whether the omission in ezyang's summary was intentional or an unfortunate oversight. If the goal is only to provide general-purpose priority queues, then I argue that we should be promoting that package. Algorithmically, they're asymptotically optimal; practically, they come with proofs of correctness; and, in practice, I've been quite happy with them. The only reason to promote something else is as a special case, if someone has a PQ which has better constant factors (for folks whose data is small enough not to care about asymptotics). However, if the goal in question is to provide general-purpose priority search queues, then clearly that project is irrelevant. -- Live well, ~wren

Also note that the finger tree version is about 10x slower than a more traditional PSQ, in exchange for nicer fairness properties. Sent from my iPad On May 6, 2011, at 4:01 AM, Balazs Komuves wrote:

There is also a fingertree-based priority search queue on Hackage:

http://hackage.haskell.org/package/fingertree-psqueue

which I used once. I think it is not thoroughly tested, though (the first version was rather buggy).

On Thu, May 5, 2011 at 3:53 AM, wren ng thornton wrote: On 5/1/11 7:58 PM, Edward Z. Yang wrote:

...

OK, to summarize the current discussion: - It would be nice to have a general-purpose priority queue in containers. I'm not interested in this goal per se, but I do view it as the cleanest way to get what I want.

With regards to this point, is there any reason why the following does not suffice (albeit not in base)?

http://code.google.com/p/priority-queues/

They're not priority *search* queues, but I'm not sure how much to read into your leaving out that word...

-- Live well, ~wren

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries