April 2011 - Libraries

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

ANNOUNCE: incremental-parser library package
by Mario Blažević 14 Apr '11

14 Apr '11

The first version of incremental-parser has been released on Hackage [1]. It's yet another parser combinator library, providing the usual set of Applicative and Monad combinators. Apart from this, it has three twists that make it unique. First, the parser is incremental. That means it can be fed its input in chunks, and in proper circumstances it can also provide the parsed output in chunks. For this to be possible the result type must be a Monoid. The complete parsing result is then a concatenation of the partial results. In order to make the incremental parsing easier, the combinator set is optimized for monoidal results. The usual combinator many1, for example, assumes the result type is a monoid and concatenates its components instead of constructing a list. In Parsec: > many1 :: Stream s m t => ParsecT s u m a -> ParsecT s u m [a] In incremental-parser: > many1 :: (Monoid s, Monoid r) => Parser s r -> Parser s r The second weirdness is that the the parser is generic in its input stream type, but this type is parameterized in a holistic way. There is no separate token type. Primitive parsers that need to peek into the input require its type to be an instance of a monoid subclass. In Parsec: > string :: Stream s m Char => String -> ParsecT s u m String > char :: Stream s m Char => Char -> ParsecT s u m Char > anyToken :: (Stream s m t, Show t) => ParsecT s u m t In Attoparsec: > string :: ByteString -> Parser ByteString > word8 :: Word8 -> Parser Word8 > anyWord8 :: Parser Word8 In incremental-parser: > string :: (LeftCancellativeMonoid s, MonoidNull s) => s -> Parser s s > token :: (Eq s, FactorialMonoid s) => s -> Parser s s > anyToken :: FactorialMonoid s => Parser s s The monoid subclasses referenced above provide methods for analyzing and subdividing the input stream. The classes are not particularly demanding, and any reasonable input stream should be able to accommodate them easily. The library comes with instances for lists, ByteString, and Text. > class Monoid m => MonoidNull m where > mnull :: m -> Bool > class Monoid m => LeftCancellativeMonoid m where > mstripPrefix :: m -> m -> Maybe m > class Monoid m => FactorialMonoid m where > factors :: m -> [m] > primePrefix :: m -> m > ... Finally, the library being implemented on the basis of Brzozowski derivatives, it can provide both the symmetric and the left-biased choice, <|> and <<|>. This is the same design choice made by Text.ParserCombinators.ReadP and uu-parsinglib. Parsec and its progeny on the other hand provide only the faster left-biased choice, at some cost to the expressiveness of the combinator language. [1] http://hackage.haskell.org/package/incremental-parser-0.1

6 7

Proposal: Improve the API for TChan, TMVar, and TVar
by wren ng thornton 09 Apr '11

09 Apr '11

I've found the following functions helpful for working with STM. Some of them are just filling out the API so that TVars, TMVars, and IORefs match better. And all the non-TVar functions can be optimized considerably by including them in the STM library rather than defining them externally. The implementations are obvious, so I'll just include the types here; see the patch if you're interested. -- | Non-blocking version of 'readTChan'. tryReadTChan :: TChan a -> STM (Maybe a) -- | Get the next value from the 'TChan' without removing it, -- blocking if the channel is empty. peekTChan :: TChan a -> STM a -- | Non-blocking version of 'peekTChan'. tryPeekTChan :: TChan a -> STM (Maybe a) -- | Non-blocking version of 'readTMVar'. tryReadTMVar :: TMVar a -> STM (Maybe a) -- | Like 'modifyIORef' but for 'TVar'. modifyTVar :: TVar a -> (a -> a) -> STM () -- | Strict version of 'modifyTVar'. modifyTVar' :: TVar a -> (a -> a) -> STM () -- | Like 'swapTMVar' but for 'TVar'. swapTVar :: TVar a -> a -> STM a Discussion period: 2 weeks. -- Live well, ~wren

4 10

ANN: SafeSemaphore, Proposal: replace QSem/QSemN
by Chris Kuklewicz 08 Apr '11

08 Apr '11

There is a leak in base. A leak in the semaphores. Drip, drip, drip. I would like to announce a new package SafeSemaphore, at > http://hackage.haskell.org/package/SafeSemaphore My intent is for this to supersede the implementation of semaphore in Control.Concurrent.QSem and Control.Concurrent.QSemN currently in the base package. This is needed because there is a quantity loss bug in QSem and QSemN. Any thread blocked while waiting might be killed. In this case a later signal will pass quantity to the dead thread. This quantity is never received and is thus lost to the program. This is logged in GHC's bug tracker at http://hackage.haskell.org/trac/ghc/ticket/3160 The MSem and MSemN modules in SafeSemaphore fix this problem and are extended replacement for QSem/QSemN with what I think is an improved and extended API. Under the hood a MSem/MSemN only ever allocates three MVars, instead of one MVar for every blocking waiter that QSem/QSemN allocate. The related Haskell wiki page at > http://haskell.org/haskellwiki/SafeConcurrent shows the included TestKillSem.hs file and its output. This shows how the QSem/QSemN bug can be triggered and shows that MSem/MSemN is immune to this leak. Cheers, Chris Kuklewicz

1 0

Re: Missing MaybeT MonadFix instance
by Ross Paterson 08 Apr '11

08 Apr '11

On Fri, Apr 01, 2011 at 08:51:52PM -0400, Job Vranish wrote: > Is there a particular reason that the transformers version of the > MaybeT monad does not have a MonadFix instance? I don't think so. The original MaybeT package had an instance instance (MonadFix m) => MonadFix (MaybeT m) where -- I hope this is correct. At a minimum, it typechecks. mfix f = MaybeT (mfix (maybe (return Nothing) (runMaybeT . f))) which would loop if f returned Nothing, while your instance, which is equivalent to instance (MonadFix m) => MonadFix (MaybeT m) where mfix f = MaybeT (mfix (runMaybeT . f . unJust)) where unJust = fromMaybe (error "mfix MaybeT: Nothing") is compatible with the MonadFix instance for Maybe, so it should probably go in. I see IdentityT is also missing a MonadFix instance, which is easily added: instance (MonadFix m) => MonadFix (IdentityT m) where mfix f = IdentityT (mfix (runIdentityT . f))

3 2

Re: Data.HashTable performance
by Johan Tibell 06 Apr '11

06 Apr '11

On Wed, Apr 6, 2011 at 1:13 PM, Manuel M T Chakravarty <mchakravarty(a)me.com> wrote: > Your package absolutely should go into the Haskell Platform! This is such essential functionality that we shouldn't leave it for people to find it on Hackage. I intend to flesh out the API a bit more during the next month, so it's on par with Data.Map. If I have the energy I'll make a proposal to add it to the HP at that point. Johan

2 1