- Libraries - Haskell.org

Proposal: priority queues in containers
by Louis Wasserman 26 Mar '10

26 Mar '10

PROPOSAL: Add a priority queue implementation to the containers package. Specific modules will include Data.PQueue.Min, Data.PQueue.Max, and Data.PQueue. DEADLINE: Next Friday, Mar 26. The ticket, #3909, is here <http://hackage.haskell.org/trac/ghc/ticket/3909>. It had done some bouncing around glasgow-haskell-users (mostly because I forgot how to do a proper libraries proposal submission), and there have been several implementations benchmarked, compared, and argued about. DETAILS: The proposed implementation benchmarked competitively with every alternative implementation that we tested, and offers good asymptotics in nearly every operation. Specifically, we use a binomial heap, which offers - O(log n) worst-case union - O(log n) worst-case extract (this in particular was a key objective of ours) - amortized O(1), worst-case O(log n) insertion. (In a persistent context, the amortized performance bound does not necessarily hold.) This implementation seems to offer the best balance between practical performance and asymptotic behavior. Moreover, this implementation is extremely memory-efficient, resulting in better performance on large data sets. (See the ticket for benchmarks. The most accurate benchmarks are towards the end.) 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. - Min-queues and max queues are separated the following way: - Data.PQueue.Min exports the type MinQueue. - Data.PQueue.Max exports the type MaxQueue. (This is implemented as a wrapper around MinQueue.) The method names are the same as Data.PQueue.Min, but I think it's acceptable to force qualified imports when using both a max-queue and a min-queue. - Data.PQueue adds the alias type PQueue = MinQueue, so that the "default" behavior is a min-queue. These design decisions seem to be sufficient to handle most traditional uses for priority queues. In particular, this approach offers a superset of the functionality offered by Java's built-in priority queue implementation<http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html>, which makes the same design decisions, but of course, is all imperative and yucky! (Also, it offers inferior asymptotics, heh.) I'm really satisfied with the patch as-is, modulo maybe tinkering with the code style a little. I'm also working on an article for TMR on priority queues in Haskell, some of the different structures we considered, and particularly the new more-type-safe implementation I came up with for binomial heaps in the writing of this implementation. Anyway, discuss, complain, et cetera. Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

19 35

Re: [Haskell-cafe] Patch for library (new feature) - how to deal with it
by Gregory Collins 26 Mar '10

26 Mar '10

Maciej Piechotka <uzytkownik2(a)gmail.com> writes: > Hello, > > I have written patch (attached) which introduce new API for zlib - > personally I wrote it to have easy implementation of > compression/decompression in iteratee (example file - no yet working > -attached). +1, I need this also, and was planning on writing something like this patch (glad I don't have to!) G -- Gregory Collins <greg(a)gregorycollins.net>

1 0

Beta version of the new HP site
by Don Stewart 26 Mar '10

26 Mar '10

http://hackage.haskell.org/platform/new/ Enjoy. Web design courtesy tupil.com (Eelco and Chris) -- Don

9 19

(no subject)
by Johan Tibell 25 Mar '10

25 Mar '10

3 3

cabal install template-haskell-2.4.0.0 fails on ghc 6.10.4
by Bernie Pope 25 Mar '10

25 Mar '10

I'm trying to install template-haskell-2.4.0.0 on OS X with ghc 6.10.4, but get a compilation error: cabal install template-haskell-2.4.0.0 Resolving dependencies... Configuring template-haskell-2.4.0.0... Preprocessing library template-haskell-2.4.0.0... Building template-haskell-2.4.0.0... [1 of 7] Compiling Language.Haskell.TH.Syntax.Internals ( Language/Haskell/TH/Syntax/Internals.hs, dist/build/Language/Haskell/TH/Syntax/Internals.o ) [2 of 7] Compiling Language.Haskell.TH.Syntax ( Language/Haskell/TH/Syntax.hs, dist/build/Language/Haskell/TH/Syntax.o ) [3 of 7] Compiling Language.Haskell.TH.PprLib ( Language/Haskell/TH/PprLib.hs, dist/build/Language/Haskell/TH/PprLib.o ) [4 of 7] Compiling Language.Haskell.TH.Ppr ( Language/Haskell/TH/Ppr.hs, dist/build/Language/Haskell/TH/Ppr.o ) [5 of 7] Compiling Language.Haskell.TH.Lib ( Language/Haskell/TH/Lib.hs, dist/build/Language/Haskell/TH/Lib.o ) [6 of 7] Compiling Language.Haskell.TH ( Language/Haskell/TH.hs, dist/build/Language/Haskell/TH.o ) [7 of 7] Compiling Language.Haskell.TH.Quote ( Language/Haskell/TH/Quote.hs, dist/build/Language/Haskell/TH/Quote.o ) Language/Haskell/TH/Quote.hs:31:12: Not in scope: data constructor `CharConstr' cabal: Error: some packages failed to install: template-haskell-2.4.0.0 failed during the building phase. The exception was: exit: ExitFailure 1 The offending piece of code is: dataToQa mkCon mkLit appCon antiQ t = case antiQ t of Nothing -> case constrRep constr of AlgConstr _ -> appCon con conArgs IntConstr n -> mkLit $ integerL n FloatConstr n -> mkLit $ rationalL (toRational n) CharConstr c -> mkLit $ charL c I have base 4.1.0.0 installed. Cheers, Bernie.

1 0

Fwd: HP Windows installer 2010.1.0.0 RC1
by Don Stewart 24 Mar '10

24 Mar '10

Progress on the Windows installer. Can Windows users (around 40% of Platform users) help out Mikhail by testing and reporting bugs? http://trac.haskell.org/haskell-platform/ -- Don ----- Forwarded message from Mikhail Glushenkov <the.dead.shall.rise(a)gmail.com> ----- Date: Wed, 24 Mar 2010 01:05:48 +0100 From: Mikhail Glushenkov <the.dead.shall.rise(a)gmail.com> To: Don Stewart <dons(a)galois.com> Cc: haskell-platform(a)community.haskell.org Subject: Windows installer 2010.1.0.0 RC1 Hi, I've uploaded the candidate 2010.1.0.0 installer to http://code.haskell.org/~refold/HaskellPlatform-2010.1.0.0-setup.exe It has two known serious issues: * cabal-install version is 0.8.0, which is known to be buggy on Windows (I couldn't compile the darcs version). * regex-posix doesn't work. The error is described in [1], and I haven't found out how to fix it yet. On the bright side, HP on Windows now comes bundled with WinGHCi. [1] http://www.mail-archive.com/haskell-cafe@haskell.org/msg51787.html -- () ascii ribbon campaign - against html e-mail /\ www.asciiribbon.org - against proprietary attachments ----- End forwarded message -----

1 0

Re: Libraries Digest, Vol 79, Issue 31
by Louis Wasserman 24 Mar '10

24 Mar '10

Yo, > * 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. I'm pretty sure there won't be a containers-compatible solution, certainly not a solution compatible with the style of containers as it's currently written, because your solution depends on exporting functionality with type classes. If we're going to change that style in containers, it should be done all at once, in a complete rewrite. Whether or not priority queues get added to containers, I'm at least going to keep the style *consistent* with containers. With regards to benchmarks, we examined a comparison with leftist heaps earlier. The biggest complaint is the O(log n) insert time, which is really kind of icky. Here was Milan's conclusion: LeftistByMilan is actually pretty good for small inputs (up to ~ 216), and > the implementation is super-trivial compared to Binomial. But when the list > gets bigger, the complexity gets worse. I think this is beause of O(log N) > inserts -- the Binomial implementation with O(1) amortized inserts allocates > much less memory and does not need to run a GC. 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). Furthermore, I added your implementation to the benchmarks that we'd been using previously, which was essentially a full heapsort, rather than just searching for the five smallest elements as in your quickie benchmark. By this comparison, your implementation is moderately slower<http://code.haskell.org/containers-pqueue/bench-chart.pdf>. (The source code and data for this benchmark version are now in the code.haskell.org/containers-pqueue directory.) Though your implementation might be faster for some particular cases of problems, I think this is a fair comparison overall, and I'm definitely not willing to accept leftist heaps' O(log n) insert time given the slower overall performance for heapsort. 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. > Again, my preference is to add pqueues to containers, and then if containers gets decoupled, then so will priority queues. If I'm going to split off a separate package for priority queues, it'll be because I've been convinced that it ought to be separated from containers, period -- not just because people think containers should be broken up, and this is a good place to start. Meh. Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

4 4

Landing pages and help for the HP
by Don Stewart 23 Mar '10

23 Mar '10

http://hackage.haskell.org/platform/new/ Has two new changes: * Per-platform "landing" pages, where we can describe the packages for each system: + http://hackage.haskell.org/platform/new/mac.html + http://hackage.haskell.org/platform/new/windows.html + http://hackage.haskell.org/platform/new/linux.html And the "Help" link, which goes to a wiki where we can document any issues, as well as suggesting tutorials and so forth. If you maintain one of the installers, patches can be made to the landing pages via the markdown files in the darcs repo: darcs get http://code.haskell.org/haskell-platform/ in the download-website/new/ directory. Also, you can improve the installation instructions on the wiki pages: http://haskell.org/haskellwiki/Haskell_Platform Thanks everyone so far for the feedback.

4 5

Haskell platform proposal: time-extras package
by Ashley Yakeley 22 Mar '10

22 Mar '10

All, I'd like to propose my "time-extras" package to be included in the next major release of the Haskell platform. The "time" package, which is already in the Haskell Platform, is currently restricted to Haskell 98. This means that it cannot, for instance, export instances of the Data class (since this requires Rank2 or RankN). The "time-extras" package contains functionality that would be in "time" were it not for the 98 restriction. Its version number matches that of "time". Currently, it consists only of Data instances. I am the author and maintainer of "time" and "time-extras". Everyone is invited to review this proposal, following the standard procedure for proposing and reviewing packages: http://trac.haskell.org/haskell-platform/wiki/AddingPackages You can always find the latest version of this proposal here: http://trac.haskell.org/haskell-platform/wiki/Proposals/time-extras Hackage link: http://hackage.haskell.org/package/time-extras -- Ashley Yakeley

5 9

Nested types for binomial heaps
by Jim Apple 22 Mar '10

22 Mar '10

Clever type nesting techniques for ensuring the structural correctness of binomial heaps have been invented before, including the technique that Louis Wasserman implemented so efficiently for his recent proposal http://hackage.haskell.org/trac/ghc/ticket/3909 . Perhaps these previous techniques could make the nested priority queue implementation even more efiicient. Ralf Hinze: (uses a different(?) extractMin algorithm) http://web.comlab.ox.ac.uk/oucl/work/ralf.hinze/publications/IAI-TR-98-12.p… Mirror: http://scholar.google.com/scholar?cluster=5719010893172593338 Chris Okasaki: (stores children in a difference list to make their reversal fast) http://okasaki.blogspot.com/2009/10/binomial-queues-as-nested-type.html Bertram Felgenhauer: (suggests some space savings) http://www.haskell.org/pipermail/haskell-cafe/2009-October/068351.html Mirror: http://groups.google.com/group/fa.haskell/msg/cdffdbb12b28e027 Mirror 2: http://article.gmane.org/gmane.comp.lang.haskell.cafe/65428

1 0