I actually found a (potential) problem with the GHC implementation. See here: https://github.com/nh2/psqueue-benchmarks/blob/db89731c5b4bdd2ff2ef81022a65f... If I fromList 1000000 entries into the queue, it stack space overflows. I got the same problem with the fingertree implementation, so maybe I just construct the test case wrong and cause the stack space overflow myself, but it works with the other two implementations. Also, looking at the updated graph: http://htmlpreview.github.com/?https://raw.github.com/nh2/psqueue-benchmarks... we can see that GHC's queue is 3 times slower than queuelike for "findmin sequential". Where could the stack overflows come from? Niklas On 30/03/13 09:07, Kazu Yamamoto (山本和彦) wrote:
Hi Niklas,
No, it does not stack overflow, and it seems to perform slightly better than the other implementations; it also doesn't suffer from the toList slowness problem as does listlike.
Thanks. It's nice.
However, it is probably not as generally usable as it hardcodes the priorities to be Doubles.
I think that you can import the tips of GHC PSQ to original PSQ.
P.S.
If you need test cases, you can find some properties for Heap (priority queue) here:
https://github.com/kazu-yamamoto/llrbtree/blob/master/test/Heap.hs
You can add some properties relating dilatation to them.
--Kazu