- Libraries - Haskell.org

Stricter WriterT (Part II)
by Gabriel Gonzalez 20 May '13

20 May '13

I previously asked on this mailing list about getting a stricter WriterT added to transformers here: http://www.haskell.org/pipermail/libraries/2012-October/018599.html To recap, neither of the two WriterT implementations in transformers keep the accumulator strictly evaluated. In the previous request, I presented four implementations, only one of which runs in constant space, all of which are in this hpaste: http://hpaste.org/75837 To summarize the four implementations: Version #1: WriterT from Control.Monad.Trans.Writer.Strict Version #2: Same as Version1, except the monad bind strictly evaluates the mappended result Version #3: WriterT reimplemented as StateT, but no strictness annotations Version #4: Same as Version3, except 'tell' strictly evaluates the mappended result Only version #4 works and runs in constant space. Actually, not only does it run in constant space, but I failed to realize at the time that it also compiles to very efficient core when you add an `Int` type annotation to the summand. For example, if you try to sum 1 billion `Int`s in the naive way using Version #4: main :: IO () main = (print =<<) $ runWriterT4 $ replicateM_ 1000000000 $ tell4 $ Sum (1 :: Int) ... and compile it with -O2, it generates the following very nice core: $wa1 = \ (w_s25b :: Int#) (ww_s25e :: Int#) (w1_s25g :: State# RealWorld) -> case <=# w_s25b 1 of _ { False -> $wa1 (-# w_s25b 1) (+# 1 ww_s25e) w1_s25g; True -> (# w1_s25g, ((), (I# (+# 1 ww_s25e)) ) #) } ... and runs in 4.6 seconds on my netbook: time ./writer ((),Sum {getSum = 1000000000}) real 0m4.580s user 0m4.560s sys 0m0.008s ... which is about 4.6 nanoseconds per element. This is quite impressive when you consider it is factoring everything through the 'IO' monad. If you use `Identity` as the base monad: main4 = print $ runIdentity $ runWriterT4 $ replicateM_ n $ tell4 $ Sum (1 :: Int) ... then it gets slightly faster: real 0m3.678s user 0m3.668s sys 0m0.000s ... with an even nicer inner loop: $wa1 = \ (w_s25v :: Int#) (ww_s25y :: Int#) -> case <=# w_s25v 1 of _ { False -> $wa1 (-# w_s25v 1) (+# 1 ww_s25y); True -> (# (), (I# (+# 1 ww_s25y)) #) } The reason this stalled last time is that Edward and I agreed that I should first investigate if there is a "smaller" type that gives the same behavior. Now I'm revisiting the issue because I can safely conclude that the answer is "no". The StateT implementation is the smallest type that gives the correct behavior. To explain why, it helps to compare the definition of `(>>=)` for both WriterT and StateT: m >>= k = WriterT $ do (a, w) <- runWriterT m (b, w') <- runWriterT (k a) return (b, w `mappend` w') m >>= k = StateT $ \s -> do (a, s') <- runStateT m s runStateT (k a) s' The `WriterT` fails to run in constant space because of the pattern of binding the continuation before mappending the results. This results in N nested binds before it can compute even the very first `mappend`. This not only leaks space, but also punishes the case where your base monad is a free monad, since it builds up a huge chain of left-associated binds. The canonical solution to avoid this sort of nested bind is to use a continuation-passing-style transformation where you pass the second `runWriterT` a continuation saying what you want to do with its monoid result. My first draft of such a solution looked like this: newtype WriterT w m a = WriterT { unWriterT :: (w -> w) -> m (a, w) } m >>= k = WriterT $ \f -> do (a, w) <- runWriterT m f runWriterT (k a) (mappend w) tell w = WriterT $ \f -> return ((), f w) runWriterT m = unWriterT m id ... but then I realized that there is no need to pass a general function. I only ever use mappend, so why not just pass in the monoid that I want to mappend and let `tell` just supply the `mappend`: newtype WriterT w m a = WriterT { unWriterT :: w -> m (a, w) } m >>= k = WriterT $ \w -> do (a, w') <- runWriterT m f runWriterT (k a) w' tell w' = WriterT $ \w -> return ((), mappend w w') runWriterT m = unWriterT m mempty Notice that this just reinvents the StateT monad transformer. In other words, StateT *is* the continuation-passing-style transformation of WriterT, which is why you can't do any better than to reformulate WriterT as StateT internally. So I propose that we add an additional stricter WriterT (under say, "Control.Monad.Trans.Writer.Stricter") which is internally implemented as StateT, but hide the constructor so we don't expose the implementation: newtype WriterT w m a = WriterT { unWriterT :: w -> m (a, w) } instance (Monad m, Monoid w) => Monad (WriterT w m) where return a = WriterT $ \w -> return (a, w) m >>= f = WriterT $ \w -> do (a, w') <- unWriterT m w unWriterT (f a) w' And define `tell` and `runWriterT` as follows: tell :: (Monad m, Monoid w) => w -> WriterT w m () tell w = WriterT $ \w' -> let wt = w `mappend` w' in wt `seq` return ((), w `mappend` w') runWriterT :: (Monoid w) => WriterT w m a -> m (a, w) runWriterT m = unWriterT m mempty If we do that, then WriterT becomes not only usable, but actually competitive with expertly tuned code.

5 6

Re: Adding Applicative/Functor instances to all Monads in GHC
by wren ng thornton 18 May '13

18 May '13

On 5/16/13 7:33 AM, David Luposchainsky wrote: > I recently went through GHC's source, and discovered there are quite a > few instances of Monad that don't have Functor or Applicative instances. > Fixing this is very easy by adding the standard instances (pure = return > etc.), and will not break code. +1. If there're obviously superior definitions then those should be used instead, of course. -- Live well, ~wren

1 0

Traversable.mapM_ missing
by Andreas Abel 18 May '13

18 May '13

On some haskell list I read that for lists, mapM_ f l is more space-efficient that just void $ mapM f l Any reason why mapM_ is missing from Data.Traversable? Cheers, Andreas -- Andreas Abel <>< Du bist der geliebte Mensch. Theoretical Computer Science, University of Munich Oettingenstr. 67, D-80538 Munich, GERMANY andreas.abel(a)ifi.lmu.de http://www2.tcs.ifi.lmu.de/~abel/

4 4

proposal/RFC: add bSwap to base in Data.Bits
by Vincent Hanquez 18 May '13

18 May '13

Hi, I'm trying to expose some byte swapping (bSwap) capabilities in base, namely operation to allow to swap endianness on word{16,32,64}, i.e.: bswap16 :: Word16 -> Word16 bswap16 a = (a `shiftR` 8) .|. (a `shiftL` 8) ... I'ld want to propose to extends Bits to do so generically: class Bits a where ... bSwap : a -> a I'm attaching a patch that do as explained, and add a default implementation for bSwap, so that compatibility is assured for existing instances. -- Vincent

8 18

Re: Adding Applicative/Functor instances to all Monads in GHC
by Gabriel Gonzalez 16 May '13

16 May '13

+1

1 0

Re: HP 2013.2 home stretch, RC2 installers
by Mark Lentczner 15 May '13

15 May '13

Thanks for the report. Oh! That's a bug - though not a huge one.... It means that doc didn't generate for the packages random, primitive, and network. Looking into this (I have the build logs), they are all failures in finding #include files when Haddock is compiling the sources with GHC. Haven't found why those three cases are different from all the other projects haddock processed where the source uses #include.... I'm not worried that haskell-platform.haddock doesn't exist - it doesn't have any doc. But I'm not sure what the next missing message is about. Looking into this, and it might mean an RC3 for Mac OS X. It won't mean a turn for the source installers, or Windows. And the only difference for Mac will be the extra source. — Mark On Tue, May 14, 2013 at 5:41 PM, George Colpitts <george.colpitts(a)gmail.com>wrote: > 64 bit OS X installer worked great for me. > > Mac OS 10.8.3 > gcc -version > i686-apple-darwin11-llvm-gcc-4.2: > > > Also with the previous 2012 HP, despite uninstalling and reinstalling I > was unable to install criterion, threadscope and Simon Marlow's code > (parconc...) for his forthcoming book. With HP 2013 I was able to compile > those plus hlint, pandoc, ghc-mod, diagrams, hakyll etc. > > I assume the ghc-pkg check warnings below about haddock for the platform > are not important. > > ghc-pkg check > Warning: haddock-interfaces: > /Users/gcolpitts/Library/Haskell/ghc-7.6.3/lib/diagrams-0.6/doc/html/diagrams.haddock > doesn't exist or isn't a file > Warning: haddock-interfaces: > /Library/Haskell/ghc-7.6.3/lib/random-1.0.1.1/doc/html/random.haddock > doesn't exist or isn't a file > Warning: haddock-interfaces: > /Library/Haskell/ghc-7.6.3/lib/primitive-0.5.0.1/doc/html/primitive.haddock > doesn't exist or isn't a file > Warning: haddock-interfaces: > /Library/Haskell/ghc-7.6.3/lib/network-2.4.1.2/doc/html/network.haddock > doesn't exist or isn't a file > Warning: haddock-interfaces: /Library/Haskell/ghc-7.6.3/lib/* > haskell-platform-2013.2.0.0*/doc/html/haskell-platform.haddock doesn't > exist or isn't a file > Warning: haddock-html: /Library/Haskell/ghc-7.6.3/lib/* > haskell-platform-2013.2.0.0*/doc/html doesn't exist or isn't a directory > > > Thanks > George > > On Sat, May 11, 2013 at 1:55 PM, Mark Lentczner <mark.lentczner(a)gmail.com>wrote: > >> *We are in the home stretch for Haskell Platform 2013.2!* >> >> The Mac OS X RC2 installers are up: >> >> Haskell Platform 2013.2.0.0 32bit rc2.signed.pkg<http://www.ozonehouse.com/mark/platform/Haskell%20Platform%202013.2.0.0%203…> >> Haskell Platform 2013.2.0.0 64bit rc2.signed.pkg<http://www.ozonehouse.com/mark/platform/Haskell%20Platform%202013.2.0.0%206…> >> >> >> Only real difference in these from RC1 is packaging: the Cabal doc is now >> included. There is no update to source tarball RC1, which is still there >> too. I expect these to be renamed the official release within a week. >> >> *Packagers:* Please produce Release Candidates. The package version list >> shouldn't change, unless any of you find an issue. >> >> - Mark >> >> >> _______________________________________________ >> Haskell-platform mailing list >> Haskell-platform(a)projects.haskell.org >> http://projects.haskell.org/cgi-bin/mailman/listinfo/haskell-platform >> >> >

1 0

stm: newBroadcastTChan and friends (a proposal, and a question)
by wren ng thornton 13 May '13

13 May '13

Hello all, While looking through the pull requests for stm-chans I came across a discrepancy in the new stm. Namely, we have the following definitions: * stm == 2.4 newBroadcastTChan :: STM (TChan a) newBroadcastTChan = do dummy_hole <- newTVar TNil write_hole <- newTVar TNil read <- newTVar dummy_hole write <- newTVar write_hole return (TChan read write) newBroadcastTChanIO :: IO (TChan a) newBroadcastTChanIO = do dummy_hole <- newTVarIO TNil write_hole <- newTVarIO TNil read <- newTVarIO dummy_hole write <- newTVarIO write_hole return (TChan read write) * stm == 2.4.2 newBroadcastTChan :: STM (TChan a) newBroadcastTChan = do write_hole <- newTVar TNil read <- newTVar (error ...) write <- newTVar write_hole return (TChan read write) newBroadcastTChanIO :: IO (TChan a) newBroadcastTChanIO = do dummy_hole <- newTVarIO TNil write_hole <- newTVarIO TNil read <- newTVarIO dummy_hole write <- newTVarIO write_hole return (TChan read write) Thus, whoever changed the definition of newBroadcastTChan in 2.4.2 forgot to change newBroadcastTChanIO to keep it in sync. PROPOSAL: I propose changing newBroadcastTChanIO to match newBroadcastTChan. (Deadline: 2 weeks) QUESTION: Is there any way to re-implement these functions using only the public API of version 2.3? -- Live well, ~wren

3 2

Building the Platform
by Mark Lentczner 13 May '13

13 May '13

The current build of the platform has grown over the years to a somewhat convoluted collection of shell scripts, makefiles, autoconf, and some custom Haskell. It is further complicated by three distinct stages: making the source distribution, building the packages, bundling for distribution. Lastly, I suspect that each distribution (Mac, Windows, and n × unix-like) has it's own path through these stages. I've done some amount of rework on the process over the last two years, but I'm thinking it is time for wholesale replacement. I'm considering using Shake <http://community.haskell.org/~ndm/shake/> to replace all three stages as one build. Distributions could choose to either re-cast their process into this Shake program, or work from the source distribution. The source distribution currently contains scripts and other bits for generically building the platform from source. I currently have no way to know which parts of those bits people rely on for their distributions. This transition would substantially change what is shipped with the source release. *Packagers & Those of you that build the platform from source:* Can you tell me which of these three directions for the source distribution you'd like: - Bare: Just the package sources and a .cabal file, than you. - Scripted: Like the current distribution, shell/make/autoconf scripts that build the platform for some idealized unix-like system. - Programmatic: Include a Haskell program (perhaps Shake based) that builds the platform I'm interested in hearing how people use the source distribution, and/or if people use the repo directly to build. If I hear crickets, I'll take that as free-reign to hatch evil schemes! — Mark

4 3

ANN: stm-chans 2.0.0
by wren ng thornton 13 May '13

13 May '13

-------------------------------------------- -- stm-chans 2.0.0 -------------------------------------------- The stm-chans package offers a collection of channel types, similar to Control.Concurrent.STM.{TChan,TQueue} but with additional features. -------------------------------------------- -- Changes (since 1.3.1) -------------------------------------------- * (by kudah) Added TMQueue and TBMQueue, which are like the corresponding T*Chans except using the new T*Queue data types in stm >= 2.4. We use CPP to provide compatibility shims for older versions of stm. -------------------------------------------- -- Long description -------------------------------------------- In particular stm-chans offers the following data types: * Control.Concurrent.STM.TBChan: Bounded FIFO channels. When the channel is full, writers will block/retry. This ensures that the writers do not get too far ahead of the readers, which helps to make sure that memory and cpu resources are used responsibly. * Control.Concurrent.STM.TMChan: Closeable FIFO channels. * Control.Concurrent.STM.TMQueue: Closeable FIFO queues. Like TChan (Maybe a) but with a monotonicity guarantee that once Nothing is returned all future reads will be Nothing as well. * Control.Concurrent.STM.TBMChan: Bounded Closeable FIFO channels. * Control.Concurrent.STM.TBMQueue: Bounded Closeable FIFO queues. Combines the capabilities of TBChan and TMChan. In addition, the stm-chans package offers a (partial) compatibility layer for various changes to the stm package. These include backwards compatibility for the T*Queue types, as well as various API improvements (see ticket #5104 [1]). [1] http://hackage.haskell.org/trac/ghc/ticket/5104 -------------------------------------------- -- Links -------------------------------------------- Homepage: http://code.haskell.org/~wren/ Hackage: http://hackage.haskell.org/package/stm-chans Darcs: http://community.haskell.org/~wren/stm-chans Haddock (Darcs version): http://community.haskell.org/~wren/stm-chans/dist/doc/html/stm-chans -- Live well, ~wren

1 0

HP 2013.2 home stretch, RC2 installers
by Mark Lentczner 11 May '13

11 May '13

*We are in the home stretch for Haskell Platform 2013.2!* The Mac OS X RC2 installers are up: Haskell Platform 2013.2.0.0 32bit rc2.signed.pkg<http://www.ozonehouse.com/mark/platform/Haskell%20Platform%202013.2.0.0%203…> Haskell Platform 2013.2.0.0 64bit rc2.signed.pkg<http://www.ozonehouse.com/mark/platform/Haskell%20Platform%202013.2.0.0%206…> Only real difference in these from RC1 is packaging: the Cabal doc is now included. There is no update to source tarball RC1, which is still there too. I expect these to be renamed the official release within a week. *Packagers:* Please produce Release Candidates. The package version list shouldn't change, unless any of you find an issue. - Mark

1 0