March 2010 - Glasgow-haskell-users

partially applied type synonyms
by Arie Peterson 05 Mar '12

05 Mar '12

Dear list, Is there a good reason that partially applied type synonyms cannot be made instances of classes? - A simple example would be making the identity type 'Id' ("type Id x = x") instance of 'Monad'. This would eliminate the need for some silly occurrences of 'runIdentity', and perhaps narrow the gap between monads and monad transformers. - The reason I complain about this now is a more involved example, where introducing a newtype to work around the restriction is not an option. Well, not as far as I can see now, anyway. Partially applied type synonyms are, in a sense, the anonymous functions at the type level, and one might argue that they deserve the same 'first-class member status' as the lambda at the value level. Kind regards, Arie Peterson

3 2

Profiling bug in 6.10.4
by Gregory Wright 01 Apr '10

01 Apr '10

Hi, I have a program (attached) that is relatively simple, but numerically intensive. It computes the abundances of the chemical elements generated by big-bang nucleosynthesis. At the moment, the executable takes no command line arguments, it simply runs the standard model. When I build the program without profiling, it produces the right answer. When I build it with profiling (runhaskell configure --enable-executable-profiling) it runs without error, but gives completely incorrect numerical results. I'm using ghc 6.10.4 built from source using MacPorts. The program is mostly self contained, but uses the hmatrix package to solve a linear system. Note also that the "Vector" type is hmatrix's Data.Packed.Vector and not the one from the more familiar "vector" package. I was wondering whether this profiling problem is known. Best Wishes, Greg

4 8

Plans for GHC 6.12.2
by Ian Lynagh 01 Apr '10

01 Apr '10

Hi all, This is a summary of our plans for GHC 6.12.2. We plan to put out a release candidate 6.12.2-rc1 shortly and, assuming there are no serious regressions found, 6.12.2 will follow soon after. The bugs that we're planning to fix for 6.12.2 are the high priority tickets in the 6.12.2 milestone: http://hackage.haskell.org/trac/ghc/query?status=new&status=assigned&status… If there is a bug not in that list that is important to you, please let us know. Thanks Ian

4 7

incorrect deprecation warning
by Peter Hercek 30 Mar '10

30 Mar '10

Hi, I got this deprecation warning: Warning: Module `GHC.Handle' is deprecated: use GHC.IO.Handle.Base instead But I think it should have been: Warning: Module `GHC.Handle' is deprecated: use GHC.IO.Handle instead There is no GHC.IO.Handle.BAse in my installation of GHC 6.12.1. The problem (it it was not intended) is there in the current head too: ~/haskell/ghc.head/libraries/base 836> darcs what -u hunk ./GHC/Handle.hs 18 -- #hide -module GHC.Handle {-# DEPRECATED "use GHC.IO.Handle.Base instead" #-} ( +module GHC.Handle {-# DEPRECATED "use GHC.IO.Handle instead" #-} ( withHandle, withHandle', withHandle_, wantWritableHandle, wantReadableHandle, wantSeekableHandle, ~/haskell/ghc.head/libraries/base 837>

2 1

trouble with Trac wiki
by nr＠cs.tufts.edu 28 Mar '10

28 Mar '10

I'm trying to log into the trac wiki, and I'm logging in OK, but it says my privileges are restricted until I verify my email address. However, the promised opportunity to verify never arrives. I've checked the spam folder and various other places---not finding it. I could be doing something stupid, but I think I need help. Whom should I ask for help with my trac wiki credentials? Norman

2 1

dblatex fails to escape backslashes
by Thanos Tsouanas 27 Mar '10

27 Mar '10

Hello list. I'm trying to compile ghc 6.12.1, but the documentation part fails because dblatex can't escape all the backslashes that it should. (I've tried dblatex-2.10, -2.11 and -2.12.) A similar problem has been discussed earlier [1], but even with Christiaan's suggested solution it fails at Cabal: "/home/thanos/local/bin/dblatex" libraries/Cabal/doc/Cabal.xml --ps -o libraries/Cabal/doc/Cabal.ps /home/thanos/local/lib/python2.6/site-packages/dbtexmf/dblatex/grubber/util.py:8: DeprecationWarning: the md5 module is deprecated; use hashlib instead import md5 Build the book set list... Build the listings... XSLT stylesheets DocBook - LaTeX 2e (0.2.12) =================================================== No template matches subtitle in article. Build Cabal.ps This is pdfTeX, Version 3.1415926-1.40.10 (PuffTeX-2009) entering extended mode latex failed Cabal.tex:1747: Undefined control sequence \Program. Cabal.tex:1747: leading text: \nolinkurl{C:\Program} Cabal.tex:1978: Undefined control sequence \Program. Cabal.tex:1978: leading text: } Cabal.tex:1978: Undefined control sequence \Haskell. Cabal.tex:1978: leading text: } Cabal.tex:1986: Undefined control sequence \Documents. Cabal.tex:1986: leading text: } Cabal.tex:1986: Undefined control sequence \user. Cabal.tex:1986: leading text: } Cabal.tex:1986: Undefined control sequence \Application. Cabal.tex:1986: leading text: } Cabal.tex:1986: Undefined control sequence \cabal. Cabal.tex:1986: leading text: } Cabal.tex:2035: Undefined control sequence \Program. Cabal.tex:2035: leading text: } Cabal.tex:2035: Undefined control sequence \Haskell. Cabal.tex:2035: leading text: } Unexpected error occured What version of dblatex and what tweeks have you people used to actually build the documentation successfully? (Please note, that the error is not breaking the process of make. make continues it's job ignoring this error.) [1] http://www.mail-archive.com/glasgow-haskell-users@haskell.org/msg17198.html -- Thanos Tsouanas http://mpla.math.uoa.gr/~thanos/

3 2

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

21 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

2 2

ANNOUNCE: haskell-platform on MacPorts
by Gregory Wright 20 Mar '10

20 Mar '10

Hi, The haskell-platform, version 2009.2.0.2, is now available from MacPorts. For those unfamiliar with MacPorts, it a build-from-source system for OS X similar to the port system used in BSD distributions. More information is available from http://macports.org. Once MacPorts is installed, you can build the haskell platform by typing > sudo port install haskell-platform On a reasonably fast MacBook, this takes an hour and a half to two hours. If you want to watch the excitement scroll past, try > sudo port -d install haskell-platform The platform contains an updated port of ghc-6.10.4 which now builds automagically on 32 and 64 bit Snow Leopard. (It can also be forced to build 32 bit on a 64 bit Snow Leopard by setting the "build_arch" variable to i386 in the macports.conf file.) The 64 bit port was cribbed from the excellent work of Barney Stratford for fink. Thanks as well to Marco Comini, Tom Hutchinson, Ian Lynagh, John Peterson, Ryan Schmidt and Falk Schramm for their help. Best Wishes, Greg Wright -- Gregory Wright Antiope Associates LLC 18 Clay Street Fair Haven, New Jersey 07704 USA gwright(a)antiope.com +1 (732) 924-4549 +1 (732) 345-8378 [fax]

1 0

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

19 Mar '10

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 documentation<http://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 results<http://code.haskell.org/containers-pqueue/bench-chart.pdf>are pretty supportive of my implementation. (Original timing data, outputted by Progression, is here<http://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

3 3

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

19 Mar '10

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 benchmarks<http://hackage.haskell.org/trac/ghc/attachment/ticket/3909/plot_2.png>were 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(a)gmail.com http://profiles.google.com/wasserman.louis

5 7