http://hackage.haskell.org/package/queuelike

I wrote this one. Heh. This is an improvement on it. More importantly, what I wanted to achieve by adding priority queues to containers was having a canonical implementation for a ubiquitous data structure, which has a simple and user-friendly interface (something the queuelike package, above, attempts but isn't extraordinarily successful at), which is guaranteed to perform efficiently and correctly. As a comparison example, there are many, many finite map implementation packages. (I wrote TrieMap, which is a pretty involved automatic generalized trie map type inference system...yeah.) There's a reason, however, that Data.Map exists, and that so many people use it when an algorithmically superior implementation might exist on Hackage -- because it's programmer-friendly and accessible, and because its performance is well-understood and has been thoroughly verified. When I use Data.Map, I'm not trusting some random schlub to have written bug-free code -- I'm trusting the Haskell built-in libraries, and the people who write and maintain those libraries. I think priority queues are ubiquitous enough to deserve the same treatment. On another note, Ian, it's really not very clear what the proper procedure for adding test suites is. Is it to just add a tester program separately from the patch? Is it to put the test suites somewhere within the containers folder, and have them be an integral part of the patch? There seem to be some sort-of-test-ish files in the containers package already, but I have no idea how to add new tests, and if the existing interface is extensible, it's not at all clear how to extend it.

Since priority search queues are actually much more natural in imperative languages than in functional languages -- since we can maintain pointers to the node associated with each key -- I think it makes even less sense for Haskell to use PSQueues in containers.  I think it's fair to say that most algorithms which need it only really require priority queues, and that it makes sense to provide for that majority in containers, though we might consider recommending the PSQueue package to programmers who need the full power of priority search queues.

I'm not sure about some of that. Imperative queues sometimes offer O(1) decreaseKey and O(lg n) delete by storing pointers to elements in a priority queue. The usual purely functional PQs can only offer O(n) decreaseKey and O(n) delete. Purely functional PSQs can offer O(lg n) decreaseKey and O(lg n) delete. Minimum spanning tree is a common application for PQs that makes good use of decreaseKey.

On Wed, Mar 17, 2010 at 4:52 AM, Yitzchak Gale wrote:

This I'm not sure about. I've considered using PQ's perhaps two or three times during the past few years, and ended up not using them at all.

I'd prefer for personal anecdote not to be the driver of discussions like this. Personally, I've never used Data.Tree or Data.Graph from the containers package, and doubt that I ever will, but it doesn't break my arm or steal my wristwatch if they're available. The types in the containers package have subtly different APIs and degrees of control over things like strictness, and also have almost no test coverage along with few signs of usage-driven optimisation. The bar for adding more code to that package is thus pretty low, in my opinion. If I had time, I'd replace it entirely. My advice would be not to stress over whether priority queues go into containers. It's not some pristine thing of beauty that deserves treatment with velvet gloves. If you want a good source of stress, create a replacement package that makes me happy :-)

True, perhaps I would have used them if there had been a simple and reliable PQ implementation at my fingertips. But it's definitely not a ubiquitous meme like Map or Set.

How about recording this great work as yet one more PQ package on hackage. But make it far more usable than all of the others by two simple steps:

1. In the package description, say simply and clearly what purpose this package is designed to serve, as you have described in this thread.

2. Submit this package for canonicalization as part of the Haskell Platform. I would for one would support its inclusion.

...

both the C++ STL and java.util.* provide just a vanilla priority queue, reflecting those design choices in those languages

As does Python. In Python, though, the PQ implementation is not a built-in class in the default namespace (as are dict and set). Rather, it is one of the "batteries included" libraries that come with Python. I think that's the right place for it in Haskell, too.

Please do consider this suggestion. However, if we do not quickly reach a consensus on this, I will withdraw my suggestion and advocate inclusion in containers as originally proposed. The difference between those options is far less important than the risk of losing this great work to haggling.

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

On Mar 17, 2010, at 11:48 , Bryan O'Sullivan wrote:

My advice would be not to stress over whether priority queues go into containers. It's not some pristine thing of beauty that deserves treatment with velvet gloves. If you want a good source of stress, create a replacement package that makes me happy :-)

Especially in the absence of guidelines for "that makes you happy", I think the answer to that one is "build it and see if they come". (There does seem to be a lot of interest in a "cleaner" containers library, but not a whole lot of consensus.) -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

Oh, god, so much to respond to...heh. Submit this package for canonicalization as part of the Haskell Platform. I

would for one would support its inclusion.

This is an option I seriously hadn't considered. To be fair, that's because I've never used the Platform myself, preferring rather to have the most up-to-date version of GHC at all times, heh. That said, while I'd be okay with this option, I'd prefer putting it into containers, because I feel like a canonical, reliable priority queue implementation is the sort of thing a self-respecting language ought to have built in. As does Python. In Python, though, the PQ implementation is not a built-in

class in the default namespace (as are dict and set). Rather, it is one of the "batteries included" libraries that come with Python. I think that's the right place for it in Haskell, too.

I don't know Python, but according to Wikipedia, dict and set are built into the language. I don't think it's a fair comparison: set and dict in Python seem to have a role almost as ubiquitous as [] in Haskell, much more ubiquitous than e.g. Data.Set or Data.Map. I'm also not entirely sure that "batteries included" doesn't describe containers, given all the other packages that come with GHC.

* There is no distinction between keys and priority values. A utility type

Prio p a with the instance Ord p => Ord (Prio p a) is exported to allow

usage of distinct keys and priority values.

I disagree with this one. It requires an Ord instance that isn't really an

ordering, and makes a Functor instance impossible. I would prefer an interface separating keys and values like that of Data.Map (which would also increase consistency within the package).

I'd be okay with separating out a priority/value version. However, I'm still clueless as to what you're talking about with respect to Functor -- what's wrong with the following? data Prio p a = Prio p a instance Ord p => Ord (Prio p a) where ... instance Functor (Prio p) where fmap f (Prio p a) = Prio p (f a) I can understand if you're uncomfortable with (==) and (\ x y -> compare x y == EQ) being inequivalent, but neither the H98 Report nor the Prelude make any such claim, as far as I can tell. The Foldable instance breaks the abstraction. I think it should

process elements in order.

I think that wanting to iterate over the priority queue in the middle of the computation, without caring about order, is a perfectly legitimate desire for a programmer! Moreover, the only way to make a Foldable instance process elements in order would be something like data Ord a => PQueue a = .... which I think is an awfully dirty approach. I'm not at all a fan of adding restrictions like that, not least because it adds lots of awkward overhead. Would you be okay with not exporting a Foldable instance at all, but still exporting a toList method which doesn't guarantee any ordering on the return list? My advice would be not to stress over whether priority queues go into

containers. It's not some pristine thing of beauty that deserves treatment with velvet gloves.

I'm...not sure how to respond to this claim. At least part of me wants to say, I genuinely do think the containers package is a piece of art...and then another part pipes up, "except for the inconsistencies between the various minView/maxView versions, and the little differences between IntMap and Map, and..." That said, I wouldn't be a fan of scrapping the style which the containers package has at least tried to create. I could be convinced that rewriting the rest of containers would be a good thing to do, though...and I might just want to do that myself. Hah. How does this implementation compare with using Map/Set as a

priority queue?

Continuing the discussion of the benchmarks: first, Jim, it appears that I'm the one who made a n00b benchmarking error. TT_____TT That said, as you found, my implementation is still slightly faster when the benchmark is corrected. Some comments: - QuickBinom needs to have O(1) findMin for a reasonable comparison. I added that in the benchmark below, and here. - I can't think of any more optimizations for the sparse binomial heap -- I genuinely think it's not going to get better. - There is a way to optimize my implementation still further, but it makes my code much less readable. (Specifically, I start the BinomForest at Succ Zero, and unpack the first child of every node still in the forest. Modifying the whole implementation that way, though, makes it unreadably ugly...and I think QuickBinom is possibly already at that point. I started implementing it, and realized just how ugly it was, and I stopped, but I can finish it if I have to.) Sorting 500,000 elements, compiled with -O2, run with +RTS -H128m -K64m, with another few implementations thrown in for good measure: Times (ms) min mean +/-sd median max Pairing: 1440.090 1482.893 31.501 1482.093 1532.095 Binomial: 1356.084 1389.687 26.881 1388.087 1436.090 SBinomial: 1376.086 1422.489 48.453 1400.088 1520.095 Data.Set: 1712.107 1800.912 74.880 1782.111 1976.123 Skew: 1584.099 1644.503 85.702 1602.101 1848.116 Some other benchmarkshttp://hackage.haskell.org/trac/ghc/attachment/ticket/3909/plot_2.pngwere done by Milan Straka earlier, when we hadn't decided what heap implementation to use at all. His comments:

I think the pairing heaps are out of the question now. I would choose between Binomial and Leftist. The Binomial have O(1) amortized inserts, but beware, that this does not work in persistent setting -- the insert is O(log N) when the heaps are used persistently (there are Skew Binomial Heaps with O(1) insert in the persistent setting too).

I vote for current (v5) Binomial implementation, even if the O(1)

amortized inserts works only non-persistently (ie. under heavy persistent usage, leftist heaps might be a _little_ better).

Conclusions: There aren't any differences in asymptotics, and as it stands, the existing implementation is just as fast. It's also a) done, and b) full of Haskellish type goodness. After about five hours' work (!!!) I *finally* managed to install Criterion yesterday, so I'll send out those tests ASAP. Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis

Hi,

...

After about five hours' work (!!!) I *finally* managed to install Criterion yesterday, so I'll send out those tests ASAP.

I wanted to use criterion too at one point, but it looked too hard to install so I was scared away...

Why is that? Because of the Chart depencency? You can install progression -- a wrapper over criterion, which uses gnuplot to draw graphs, and disable the Chart dependency. I did just cabal --user install -f "-Chart" criterion progression and it installed without a problem, on ghc-6.12.1, ghc-6.13.something, both Linux and Windows. Cheers, Milan

First off: I've finally gotten set up with code.haskell.org. A darcs repo of my binomial heap implementation is at http://code.haskell.org/containers-pqueue/. Also on that site is the haddock documentationhttp://code.haskell.org/containers-pqueue/containers-0.3.0.0/html/, which I'm sure many people will appreciate. Somebody else (Ross?) had requested a separate version of the priority queue to handle priorities and values separately, so I'm working on that. I've also deleted the Foldable instance of MinQueue, though I still offer a clearly documented unordered toList, which will stay in place. Well, I only tested one thing (heap sort), and QuickBinom is actually faster under different options (-prof -auto-all or without calling

performGC before every heapsort).

-prof -auto-all blocks a significant number of optimizations from actually happening. Essentially, if the compiler has to figure out how much time is taken by some particular function, then it's not allowed to inline or eliminate uses of that function. I don't consider it a fair comparison. Moreover, calling performGC makes sense -- it essentially wipes the slate, making each successive comparison unbiased by the previous one. Louis, you note later in this email that your implementation is done.

That seems important to me. If we fix a sane interface now, the implementation can be changed later if we find something more efficient, right?

Absolutely true. However, I finally assembled a benchmark that I think is a fair comparison -- a heapsort, essentially "length . Data.List.unfoldr extract . foldr insert empty". The resultshttp://code.haskell.org/containers-pqueue/bench-chart.pdfare pretty supportive of my implementation. (Original timing data, outputted by Progression, is herehttp://code.haskell.org/containers-pqueue/bench-final.csv. I think all of the original code for the benchmark is in the code.haskell.org folder, just not part of the darcs repo. However, I had to slightly modify my copy of Progression to force the GC, so YMMV.) I'm still pretty strongly in favor of putting priority queues into containers: other programming languages consider it necessary for inclusion into standardized libraries, people will be more likely to use appropriate data structures for their needs when reliable, friendly implementations are already at their fingertips, and other reasons already discussed. In general, I think priority queues should be treated the same as Data.Map or Data.Set, like java.util.* or the C++ STL treat their respective versions of those structures. I don't think there's likely to be any agreement any time soon to split up containers, so my inclination is to put pqueues into containers, and maybe if we agree later to split containers, then priority queues will be part of that decision. On a somewhat different note: writing unit tests in the existing framework is awkward and hard! Writing QuickCheck tests is trivial and much more exhaustive than what the existing tests look like. The existing containers tests appear to check one particular example that was the source of a preexisting bug, rather than examining exhaustively that methods work correctly, to eliminate potentially new bugs. I mean, Data.IntSet's one existing test is main = print $ isProperSubsetOf (fromList [2,3]) $ fromList [2,3,4] which might have found some preexisting bug, but certainly doesn't convince me of Data.IntSet's correctness. Is this normal? Is it permissible to use QuickCheck inside unit tests? (A collection of QuickCheck tests -- all of which my implementation passes -- is in the code.haskell.org directory.) Louis Wasserman

Okay, let me ask the following question: Would anybody besides me be heartbroken if priority queues *weren't* put into containers, but were instead put into the Platform? Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis On Thu, Mar 18, 2010 at 6:50 PM, Thomas Schilling wrote:

On 18 March 2010 22:02, Louis Wasserman wrote:

...

I'm still pretty strongly in favor of putting priority queues into containers: other programming languages consider it necessary for inclusion into standardized libraries, people will be more likely to use appropriate data structures for their needs when reliable, friendly implementations are already at their fingertips, and other reasons already discussed.

The Haskell Platform is really is intended to be available at your fingertips. Unfortunately, the following does not work (although I thought it's supposed to)

$ cabal install haskell-platform

Nevertheless, the libraries bundled with GHC are those libraries that GHC itself needs and which therefore cannot be upgraded independently. The real standard libraries are the Haskell Platform and if your package is part of the platform, then your package *is* in status equivalent to things like java.util.*.

This weekend's Hackathon in Zürich will partly be dedicated to getting the next release of the Platform release ready. If you can get your package into the following platform release (due 6 months after the current release), then this would surely make it the default package for anyone in need of a PQ.

/ Thomas -- Push the envelope. Watch it bend.

Louis Wasserman wrote:

Would anybody besides me be heartbroken if priority queues *weren't* put into containers, but were instead put into the Platform?

I don't feel strongly either way. One definite advantage of putting it into containers would be that the module would be easy to find. One disadvantage is that improvements will take long to trickle through the next ghc or haskell platform release - updating the containers package in an existing installation would be tricky, I think, because a lot of packages depend on containers. As far as I can tell you did a great job at tuning the implementation. It beats my own home-ground binomial heap (which uses essentially the same data structure, except that it has a special case for leafs) hands down when it comes to running time. So if the consensus is to make this a separate package, please announce it prominently. I'm certainly interested in using it. Best regards, Bertram

On Thu, Mar 18, 2010 at 4:43 PM, Louis Wasserman wrote:

...

 Submit this package for canonicalization as part of the Haskell Platform. I would for one would support its inclusion.

This is an option I seriously hadn't considered.  To be fair, that's because I've never used the Platform myself, preferring rather to have the most up-to-date version of GHC at all times, heh.  That said, while I'd be okay with this option, I'd prefer putting it into containers, because I feel like a canonical, reliable priority queue implementation is the sort of thing a self-respecting language ought to have built in.

I don't like libraries getting bigger, I like them getting smaller. When they're smaller they're easier to understand and easier to upgrade. So I would also advice proposing your package for the HP (Haskell Platform). I'm even for splitting containers into sub-packages: maps, sets, sequence, graph and tree. Those sub-packages would then need to be added to the HP. Then we could turn containers into a meta-package that depends on these sub-packages (similar to how the HP works[1]). Finally we could deprecate containers and after some time remove it. (I'm also for splitting base even more... but one thing at a time) regards, Bas [1] http://hackage.haskell.org/platform/2009.2.0.2/haskell-platform.cabal

On Thu, Mar 18, 2010 at 10:39 PM, Milan Straka wrote:

personally I am against splitting containers. It is a collection of several basic data structures with similar design decisions (reasonably efficient, can be used persistently, decent API). I think these structures should stay together, to have a library of data structures for common usage.

But when turning containers into a meta-package these structures will stay together while at the same time allowing people to use and upgrade them separately. regards, Bas

On Mar 18, 2010, at 18:33 , Milan Straka wrote:

I would like to have basic data structures connected together. I do not really mind if the modules are in one library or in several, as long as I could say "I want 'containers'."

This is what the Haskell Platform is for. No real need to add more stuff to containers; if anything, the libraries stored there should be decoupled so that e.g. the recent Data.Map proposals wouldn't disturb programs not using Data.Map. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

On Tue, Mar 16, 2010 at 11:54:35AM -0500, Louis Wasserman wrote:

On another note, Ian, it's really not very clear what the proper procedure for adding test suites is. Is it to just add a tester program separately from the patch? Is it to put the test suites somewhere within the containers folder, and have them be an integral part of the patch? There seem to be some sort-of-test-ish files in the containers package already, but I have no idea how to add new tests, and if the existing interface is extensible, it's not at all clear how to extend it.

The best way is probably to make tests using the GHC testsuite framework in tests/priority-queue/. The framework would benefit from some tweaking so that it is better able to test a single library in isolation, though. Thanks Ian

On Thu, Mar 18, 2010 at 10:50:05AM +0000, Simon Marlow wrote:

On 17/03/2010 15:56, Ian Lynagh wrote:

...

On Tue, Mar 16, 2010 at 11:54:35AM -0500, Louis Wasserman wrote:

...

On another note, Ian, it's really not very clear what the proper procedure for adding test suites is. Is it to just add a tester program separately from the patch? Is it to put the test suites somewhere within the containers folder, and have them be an integral part of the patch? There seem to be some sort-of-test-ish files in the containers package already, but I have no idea how to add new tests, and if the existing interface is extensible, it's not at all clear how to extend it.

The best way is probably to make tests using the GHC testsuite framework in tests/priority-queue/. The framework would benefit from some tweaking so that it is better able to test a single library in isolation, though.

Shouldn't the tests go in the library repo itself?

Right, I mean tests/priority-queue/ in the containers repo (there are already a couple of tests in tests/). Thanks Ian

On 16/03/10 17:56, Jim Apple wrote:

...

I do wonder how this implementation compares to packages on hackage, e.g.:

Also:

http://hackage.haskell.org/package/heap

Let me speak for this one, as I happen to know it. Unfortunately I don't have much time for a thorough performance comparison (Maybe someone can come up with general testcases? It should be possible to quickly rewrite them for each package!), but I did two tests an heap was twice as fast as the proposition (containers-pqueue): *Data.PQueue.Min> takeWhile (<= 5) $ (fromList [1..100000]) `union` (fromList [100001..200000]) [1,2,3,4,5] and *Data.PQueue.Min> takeWhile (<= 5) $ (fromAscList [1..100000]) `union` (fromAscList [100001..200000]) [1,2,3,4,5] ===== vs. ===== *Data.Heap> takeWhile (<=5) $ (fromList [1..100000]) `Data.Heap.union` (fromList [100001..200000] :: MinHeap Int) [1,2,3,4,5] and *Data.Heap> takeWhile (<=5) $ (fromAscList [1..100000]) `Data.Heap.union` (fromAscList [100001..200000] :: MinHeap Int) [1,2,3,4,5] In both cases, heap was about twice as fast as containers-pqueue. I don't know if theses test cases are representative, please comment on that :) Regards, Stephan

On 17/03/10 16:47, Ross Paterson wrote:

On Tue, Mar 16, 2010 at 08:54:15AM -0500, Louis Wasserman wrote:

...

A couple potentially contentious design decisions:

* There is no distinction between keys and priority values. A utility type Prio p a with the instance Ord p => Ord (Prio p a) is exported to allow usage of distinct keys and priority values.

I disagree with this one. It requires an Ord instance that isn't really an ordering, and makes a Functor instance impossible. I would prefer an interface separating keys and values like that of Data.Map (which would also increase consistency within the package).

I agree. The Functor instance is crucial (at least to me). Besides, I'm the author of [1] and writing that package, I made the experience that it absolutely makes sense to separate the part of a queue entry that determines it's position within the queue from the part that is user data. A clean Functor instance is just one of the benefits.

Other comments:

The Foldable instance breaks the abstraction. I think it should process elements in order.

Yes. I'd consider everything else a bug.

[...]

Other points are: * I'm not comfortable with having two redundant modules, one for Min- and one for MaxQueue. It is possible to implement both in the same data structure and still get type errors when e.g. 'union' on a Min- and a MaxQueue (I did that in [1], please have a look at the latest version). My solution needs type families, which would not be good for containers, but I'm pretty sure there's a containers-compatible solution. * Not so important, but IMHO 'extract' should be called 'view', because that's, how this sort of function is usually called, isn't it? ;) Regards, Stephan [1] http://hackage.haskell.org/package/heap