- Libraries - Haskell.org

A paper relating to Data.Set and Data.Map
by Kazu Yamamoto 19 Apr '11

19 Apr '11

Hello libraries and cafe, We (Hirai and I) would like to tell you our paper relating to Data.Set and Data.Map. "Balancing Weight-Balanced Trees" is now accepted and will appear in Journal of Functional Programming. The camera-ready version of the paper is available from: http://www.mew.org/~kazu/proj/weight-balanced-tree/ Please recall that Taylor Campbell reported a bug of Data.Map in last Summer. In some cases, the balance of Data.Map is broken after delete operations. This triggered our research. http://article.gmane.org/gmane.comp.lang.haskell.libraries/13444 Though Data.Set/Data.Map are based of a variant Weight-Balanced tree by Adams, we target the original Weight-Balanced tree by Nievergelt and Reingold. They are parameterized algorithms and the difference of two algorithms is quite small. But the original has smaller conditions which are gentle for proof. We identified the valid area of two parameters of the original Weight-Balanced tree and showed <3,2> is only one integer solution. Soundness is proved in Coq and completeness is verified with four algorithms to generate counterexamples for the outside of the valid area. "wttree.scm" of MIT/GNU Scheme and slib have already incorporated our fixes. When I offered our fixes to MIT/GNU Scheme, Taylor Campbell appeared again. I understand that he is an MIT/GNU Scheme guy and found the bug of Data.Map when re-implementing "wttree.scm" consulting Data.Map. :-) We think it's Haskell community turn now. Data.Set/Data.Map are still based on the variant whose soundness is not proved yet. If interested, let's discuss whether or not we should replace the variant with the original in Data.Set/Data.Map. We guess that Milan Straka, a big contributer of the container package, has his opinion. We welcome opinions from other people, two. Regards, --Kazu

2 1

Re: How to contact OpenGL package maintainer (where is Sven?)
by Jason Dagit 19 Apr '11

19 Apr '11

On Mon, Apr 18, 2011 at 6:21 PM, Jens Petersen <juhp(a)community.haskell.org>wrote: > On 7 April 2011 06:51, Don Stewart <dons00(a)gmail.com> wrote: > > Moving those modules under OpenGL.*.*.StateVar etc would remove the > > problems with upgrading to the HP. > > Perhaps it would be a good time now to revisit again whether > we really need to include OpenGL support inside HP or not. > > I grant that it may be convenient for users who might find it > hard to build OpenGL and GLUT with cabal-install; on the other hand > not that many haskell packages actually need those libraries AFAICT > so I am still not convinced that they really belong in HP. > Let's look at some numbers: http://www.galois.com/~dons/hackage/march-2011/mar-10-to-feb-11.txt <http://www.galois.com/~dons/hackage/march-2011/mar-10-to-feb-11.txt>Search for opengl and you'll see that it's in the top 25, meaning it's used by a relatively high number of packages. That means we're discussing a library that provides a unique capability (opengl support) that is in the top 25 of the Haskell libraries. Not making it easy to get seems like a bit of a strategic error to me. The reverse package index shows what depends on it: http://bifunctor.homelinux.net/~roel/cgi-bin/hackage-scripts/revdeps/OpenGL… And some things depend on the raw bindings instead: http://bifunctor.homelinux.net/~roel/cgi-bin/hackage-scripts/revdeps/OpenGL… Additionally, I've had 1 person contact me off list saying that they wouldn't even be a Haskell programmer if the opengl bindings were not in the HP. If there had been any barrier to getting good opengl support when they started learning Haskell that would have been a show stopper for them. Jason

1 1

Re: How to contact OpenGL package maintainer (where is Sven?)
by Don Stewart 19 Apr '11

19 Apr '11

There's a ticket to track discussion around removal here: * http://trac.haskell.org/haskell-platform/ticket/57 Removing large C library dependencies is generally a good thing; however, removing functionality is bad. And we don't have a good track record for adding functionality yet. On Mon, Apr 18, 2011 at 6:21 PM, Jens Petersen <juhp(a)community.haskell.org> wrote: > On 7 April 2011 06:51, Don Stewart <dons00(a)gmail.com> wrote: >> Moving those modules under OpenGL.*.*.StateVar etc would remove the >> problems with upgrading to the HP. > > Perhaps it would be a good time now to revisit again whether > we really need to include OpenGL support inside HP or not. > > I grant that it may be convenient for users who might find it > hard to build OpenGL and GLUT with cabal-install; on the other hand > not that many haskell packages actually need those libraries AFAICT > so I am still not convinced that they really belong in HP. > > Maybe if hopengl provided upstream binaries for current Windows and Mac HP > that might lessen the burden on the HP binary maintainers too? > > Jens >

1 0

How to contact OpenGL package maintainer (where is Sven?)
by Jason Dagit 18 Apr '11

18 Apr '11

I sent the message below to Haskell-Cafe about a week ago. I got one response saying that Sven has disappeared in the past but reappeared when updates were necessary. I still haven't heard from Sven. Now I'm widening my search. My original email to Sven was on March 11th. It looks like the OpenGL packages on hackage[1,2,3,4] have not been updated in some time. No updates later than Oct 2009. I tried to email Sven directly using the email address listed on hackage but after over two weeks I still haven't heard from him. I sent some patches to the opengl list about a week ago but I noticed that Sven hasn't posted on that list since Oct 2009 when he released the current version of OpenGLRaw. None of the public darcs repos have patches newer than Oct 2009. Also, the homepage url listed in the packages is a 404: http://www.haskell.org/HOpenGL/ My concern is that Sven has disappeared for some reason. I hope he's well. He has always done top notch work in the past maintaining these libraries. Perhaps he's simply busy or lost interest? Does anyone know if he was looking for a new maintainer? Perhaps you've heard from him more recently than Oct 2009? If a new maintainer is needed, I would consider nominating myself :) Thanks, Jason [1] http://hackage.haskell.org/package/OpenGLRaw [2] http://hackage.haskell.org/package/OpenGL [3] http://hackage.haskell.org/package/GLURaw [4] http://hackage.haskell.org/package/GLUT

6 15

MTL Upgrade Problem
by Dominic Steinitz 17 Apr '11

17 Apr '11

Hi, I have > dom1@fourier:~/asn1_0> ghc-pkg list --user > /home/dom1/.ghc/i386-linux-6.12.1/package.conf.d > mtl-1.1.0.2 > mtl-2.0.1.0 > But I get the following error: > [4 of 6] Compiling LatticeMod ( LatticeMod.hs, interpreted ) > [5 of 6] Compiling ConstraintGeneration ( ConstraintGeneration.lhs, > interpreted ) > > ConstraintGeneration.lhs:781:6: > Overlapping instances for Monad (Either String) > arising from a use of `return' > at ConstraintGeneration.lhs:(781,6)-(782,69) > Matching instances: > instance (Error e) => Monad (Either e) > -- Defined in Control.Monad.Trans.Error > instance (mtl-1.1.0.2:Control.Monad.Error.Class.Error e) => > Monad (Either e) > -- Defined in mtl-1.1.0.2:Control.Monad.Error > In the expression: > return > (ExtensibleConstraint > (ResStringConstraint v top) (ResStringConstraint top top) b) > In the definition of `pvPermittedAlphabetElements': > pvPermittedAlphabetElements (S (SV v)) b > = return > (ExtensibleConstraint > (ResStringConstraint v top) > (ResStringConstraint top top) > b) > Failed, modules loaded: ASNTYPE, LatticeMod, > Language.ASN1.PER.Integer, Language.ASN1.PER.IntegerAux. If I do > dom1@fourier:~/asn1_0> ghc-pkg hide mtl-2.0.1.0 Then the error goes away. But if I do > ghc-pkg hide mtl-1.1.0.2 Then I still get the error. Is there a wiki page that tells me what to do to upgrade from mtl-1 to mtl-2? Or perhaps someone can tell me what to do? Many thanks, Dominic.

2 2

Haskell Platform 2011.2.0.1 now available
by Don Stewart 16 Apr '11

16 Apr '11

We're pleased to announce the 2011.2.0.1 release of the Haskell Platform: a single, standard Haskell distribution for everyone. Download the Haskell Platform 2011.2.0.1: http://haskell.org/platform/ This release adds support for GHC 7.0.3, and significant improvements for Mac OS X users. The specification, along with installers (including Windows, Mac and Unix installers for a full Haskell environment) are available. The Haskell Platform is a single, standard Haskell distribution for every system, in the form of a blessed library and tool suite for Haskell distilled from the thousands of libraries on Hackage, along with installers for a wide variety of systems. It saves developers work picking and choosing the best Haskell libraries and tools to use for a task. When you install the Haskell Platform, you get the latest stable compiler, an expanded set of core libraries, additional development tools, and cabal-install – so you can download anything else you need from Hackage. This release ships with GHC 7.0.3. What you get is specified here: http://hackage.haskell.org/platform/contents.html Thanks! -- The Platform Infrastructure Team P.S. a big thanks to Mark Lentczner and Mikhail Glushenkov who built the Mac and Windows installers!

2 2

Proposal: Faster conversion between Rational and Double/Float
by Daniel Fischer 15 Apr '11

15 Apr '11

Currently, the conversions between Rational and Double resp. Float are rather slow: Converting 10,000 (pseudo-random) Doubles (from an unboxed array) to Floats and summing: Range -1e308 to 1e308: - double2Float: mean: 4.343703 ms, lb 4.324399 ms, ub 4.382361 ms, ci 0.950 - uncurry encodeFloat . decodeFloat: mean: 6.449336 ms, lb 6.427503 ms, ub 6.488190 ms, ci 0.950 - fromRational . toRational: mean: 875.3696 ms, lb 874.4413 ms, ub 876.6326 ms, ci 0.950 Range -1e37 to 1e37: - double2Float: mean: 547.6073 us, lb 544.3635 us, ub 559.5245 us, ci 0.950 - uncurry encodeFloat . decodeFloat: mean: 2.754600 ms, lb 2.749209 ms, ub 2.768121 ms, ci 0.950 - fromRational . toRational: mean: 287.4107 ms, lb 286.9602 ms, ub 288.0782 ms, ci 0.950 So all conversions suffer from large/out of range values, the primop most. The conversion via fromRational . toRational takes 200 - 500 times as long (subtracting array reads and addition, it would probably be much more for the conversion itself). The conversion via the proposed new implementations of toRational and fromRational took - large range: mean: 10.89560 ms, lb 10.86049 ms, ub 10.97370 ms, ci 0.950 - small range: mean: 7.015212 ms, lb 6.993312 ms, ub 7.068088 ms, ci 0.950 It suffers much less from large/out of range values and is 40 - 80 times faster than the old (probably a little more, subtracting array reads and additions). Converting 10,000 Floats to Doubles: - float2Double: mean: 540.6598 us, lb 539.0135 us, ub 545.1019 us, ci 0.950 - uncurry encodeFloat . decodeFloat: mean: 1.886183 ms, lb 1.882036 ms, ub 1.896018 ms, ci 0.950 - fromRational . toRational: mean: 280.6127 ms, lb 280.2228 ms, ub 281.1654 ms, ci 0.950 - new implementation: mean: 5.909890 ms, lb 5.892503 ms, ub 5.961752 ms, ci 0.950 ==================================================== One of the key factors for a fast fromRational is a fast integer logarithm to base 2. Since GHC can be built with integer-gmp or integer-simple and a fast implementation requires exploiting the low-level representation of Integers, I deemed it better to add modules to those packages implementing logarithms than adding different source directories to base to choose the appropriate one based on a flag, therefore in addition to the patch to base, this proposal includes patches to integer-gmp and to integer-simple, providing some integer logarithm functions. All functions have been tested to satisfy the appropriate conditions (fromRational (toRational x) == x for x Float/Double not NaN; toRational/fromRational yield the same values as the old implementation; base ^ integerLogBase base num <= num && num < base ^ (integerLogBase base num + 1) for base > 1, num > 0), both with pseudo-random input and selected special cases. The patches have been validated against ghc-7.1.20110329 (no unexpected failures in the testsuite which aren't identical without the patches). Since I have a 32-bit system, it is conceivable that I have a glitch in the 64-bit code, I'd appreciate testing. Summary: I propose - adding modules implementing integer logarithm functions to integer-gmp and integer-simple - changing the implementation of toRational and fromRational for Double and Float using those to become significantly faster. Period of discussion: two weeks (until 14th April). Cheers, Daniel

3 4

Re: Relocatable libraries in windows
by Jake Foell 15 Apr '11

15 Apr '11

Dear haskell rascals, In an attempt to create a relocatable repository of development tools, I created this simple script to configure/build/install packages from hackageDB. This script is meant to be used in an 'msys' environment on a windows machine. To quote the Cabal User's Guide (sec 4.1.2.3) > A library cannot (currently) be prefix-independent, because it will be > linked into an executable whose file system location bears no relation to > the library package > So far, this attempt has been successful for me. Improvements, criticism, and other solutions are welcome. Thanks. jake >

1 1

Proposal: Replace QSem, QSemN, SampleVar in base
by Chris Kuklewicz 14 Apr '11

14 Apr '11

This is my first proposal to change some things in "base" and I trust that my request is not going to be perfect. The packages that I am proposing to change are all in Control.Concurrent and build on MVars: QSem, QSemN, and SampleVar. I wish to change them because this will fix an important bug they have in common. Who needs to approve of the following proposed change? Additional URLS: http://hackage.haskell.org/trac/ghc/ticket/3160 http://hackage.haskell.org/package/SafeSemaphore http://haskell.org/haskellwiki/SafeConcurrent All three of QSem, QSemN, and SampleVar create an abstraction and attempt to maintain an invariant or behavior. QSem and QSemN present the abstraction of a conserved quantity. SampleVar wishes to maintain a single updatable value. All three have in common that waiting on a semaphore or read the sample var will block if there is no quantity or value present. There can be many thread blocked in this way. All three abstractions fail to maintain their integrity in the case where one of the blocked waiters gets interrupted. This is not a random or rare failure, they abstraction always fails after the first waiter dies. Thus the root cause of the problem is that these modules were written with the unenforced and undocumented assumption that none of the waiters can be interrupted. The specific failure with QSem and QSemN is that signaling the semaphore will pass quantity to the already interrupted waiter. This quantity leak cannot be prevented by the user of module with clever exception handling. This leak will likely cause some or all future attempts to wait on the semaphore to block indefinitely. The specific failure with SampleVar is that writeSampleVar and emptySampleVar will trust the no longer correct count of blocked readers. These methods can then block indefinitely. This is triggered by: newEmptySampleVar, readSampleVar, kill the blocked reader, writeSampleVar, writeSampleVar. The writeSampleVar should never more than momentarily block, so this indefinite block turns the SampleVar into acting like a regular MVar. Also, isEmptySampleVar will no longer ever read full once the SampleVar is broken. All of these three modules can be replaced with MSem, MSemN, and MSampleVar in the SafeSemaphore package (on hackage). These allow the same operations as those in base but without the above flaw. If a waiter dies in the new modules then the waiter will have had no effect on the quantity or value. Slightly surprisingly, these improved modules all have simpler implementations. I have also expanded the APIs to expose additional useful operations that can be performed. Finally, I have changed the names in the new modules to be less verbose as the community style has evolved to use qualified imports. There is a vanishingly small change someone depends on the flawed behavior of the base modules. I propose to ignore this possibility and replace the old modules with thin layers around SafeSemaphore.

3 3

mtl: Context of execWriterT
by Daniel Díaz 14 Apr '11

14 Apr '11

Hi, I have a question about the context of the execWriterT function, in Control.Monad.Writer of the mtl package. The current context forces the containter type to be a Monad, while is enough a Functor. Yes, WriterT is a monad transformer, so this is not a problem, but I have as a law to write the less restrictive context for every function. So, is there any reason to do this context more restrictive? If not, the obvious way to do it may be: execWriterT :: Functor m => WriterT w m a -> m w execWriterT = fmap snd . runWriterT However, I thought that there must be a reason explaining this fact.

3 2