April 2011 - Haskell-Cafe

RFC: Possible improvements to System.Random and Control.Monad.Random API
by Krzysztof Skrzętnicki 19 Apr '11

19 Apr '11

Today I answered a question on stackoverflow.com about behaviour of random data generation [1]<http://stackoverflow.com/questions/5714873/weird-performance-with-evalrandi…>. The code in question was as follows: import Control.Monad.Random inf :: (RandomGen g, Random a) => Rand g [a] inf = sequence $ repeat $ getRandom many :: (RandomGen g, Random a) => Int -> Rand g [a] many n = sequence $ replicate n $ getRandom main = do m <- evalRandIO $ many 1000000 :: IO [Bool] i <- evalRandIO $ inf :: IO [Bool] putStrLn $ show $ take 5 m putStrLn $ show $ take 5 i It triggered stack overflow if the stack wasn't set high enough. This was because to calculate i one has to first calculate the seed that results from evaluating many 1000000 :: IO [Bool]. Even worse, if we swap the order of execution like this: main = do i <- evalRandIO $ inf :: IO [Bool] m <- evalRandIO $ many 1000000 :: IO [Bool] putStrLn $ show $ take 5 m putStrLn $ show $ take 5 i We will get space leak and our code will never finish nor provide single bit of output. One possible solution is to make cell holding std gen strict. This would make behaviour more clear to the unsuspecting user. I think it might have other uses, but unfortunately this would also break some code. So I think another solution might be applicable here. In my response I provided solution based on the fact that StdGen is splittable. The essence of the solution is to have each call to evalRandIO run on different seed. main = do newGen' <- newStdGen m <- evalRandIO $ many 1000000 :: IO [Bool] setStdGen newGen' i <- evalRandIO $ inf :: IO [Bool] putStrLn $ show $ take 5 m putStrLn $ show $ take 5 i This code works as expected, i.e. very runs fast. It dawns on me that this solution might be useful as a general pattern. There are several ways to do that. One might define additional functions for random values generation. For example for Control.Monad.Random: randomSplitIO :: (Random a) => IO a randomSplitIO = do newGen <- newStdGen val <- randomIO setStdGen newGen return val But this is slightly unfortunate, as it grows the API considerably. I estimate that overall 5-10 new functions will be needed (both internal and external, that is). The best idea I have now is to add this function to System.Random: withSplitGen :: IO a -> IO a withSplitGen act = do newGen <- newStdGen val <- act setStdGen newGen return val Additional function will be needed for Control.Monad.Random, but I don't know how to write it. getSplit [2]<http://hackage.haskell.org/packages/archive/MonadRandom/0.1.6/doc/html/Cont…>will likely be involved in such function. The original program becomes this, and works as expected. main = do i <- withSplitGen $ evalRandIO $ inf :: IO [Bool] m <- withSplitGen $ evalRandIO $ many 1000000 :: IO [Bool] putStrLn $ show $ take 5 i putStrLn $ show $ take 5 m As a bonus this function could draw attention to the problem that otherwise might be overlooked. People would get better understanding of how StdGen works just by reading documentation of this function. Please comment on this idea. Perhaps there are some problems I didn't anticipate or some naming could be improved. Best regards, Krzysztof Skrzętnicki [1] http://stackoverflow.com/questions/5714873/weird-performance-with-evalrandi… [2] http://hackage.haskell.org/packages/archive/MonadRandom/0.1.6/doc/html/Cont…

1 0

Trac configuration error
by Andrew Pennebaker 19 Apr '11

19 Apr '11

Try to visit http://trac.haskell.org/ghc. <type 'exceptions.IOError'> Python 2.5.2: /usr/bin/pythonTue Apr 19 15:02:32 2011A problem occurred in a Python script. Cheers, Andrew Pennebaker www.yellosoft.us

1 0

Confusing performance variation while optimising a tight loop
by Patai Gergely 19 Apr '11

19 Apr '11

Hello all, I've been trying to improve the performance of Hemkay, my MOD player. The mixing routines are in a separate library with no special dependencies. Most of the time is spent in a small loop in the mixToBuffer function [1] (note that this version is not the master branch in case you give it a try). Each iteration does the following: it advances a pointer in a waveform (float vector) with a fractional amount (depending on the frequency at which it's played back), multiplies it by the desired volume and distributes it over the two channels (two more multiplication). The case where the step is less than zero is special cased for efficiency (lines 170-183), but commenting that out won't affect the output, just make it take about 15% more time. The isEmpty and stepWave' functions come from the Music module. The confusion is the following: a waveform can be of three kinds (empty, single-shot or looped), which is represented by a plain sum type. In the fastest version I match this pattern twice for every sample output (through the isEmpty and stepWave' functions). Since the kind of waveform doesn't change during this tight loop, I figured I could speed it up by moving the pattern match out of the loop and only increasing the index into the vector, thereby doing strictly less work per sample. This is the version on lines 204-234. However, this modification makes the program twice as slow as the original, and I simply don't understand what I'm doing wrong or what could possibly cause this! The speed test is a self-contained program in the test directory, you can compile it after installing the library. If you pass it a MOD music file, it'll perform mixing and quit immediately afterwards. Gergely [1] https://github.com/cobbpg/hemkay-core/blob/vector/Sound/Hemkay/Mixer.hs -- http://www.fastmail.fm - The professional email service

1 0

deriving instances in GHC 7.*
by Alberto G. Corona 18 Apr '11

18 Apr '11

By my little experience with GHC 7.* it seems that this version is more "deterministic" when deriving instances. For example if there is a general instance declaration such is: instance C1 x=> C2 x where .... then the absence of the C1 instance becomes an error. C1 instance becomes a prerequisite for any C2 instance, where in previous versions, that was just a overlapping instance in collision with any other less general instance of the C2 class, so it could be overcomed with the "OverlappingInstances" flag. Given that is not possible to hide instances, this is annoying. I´m not saying that this is wrong or even If this is so, because this could be a misinterpretation on my side based on the tests I have done. Where can I read about the rationale of this change?. General Instance derivations rules, as any rule system seem to me naturally flexible and with different degrees of generalization rather tan rigid.

1 1

Errata for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell
by KC 18 Apr '11

18 Apr '11

Errata for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell smallest :: (Ord a) => Int -> (Array Int a, Array Int a) -> a smallest k (xa,ya) = search k (0,m+1) (0,n+1) where (0,m) = bounds xa (0,n) = bounds ya search k (lx,rx) (ly,ry) | lx == rx = ya ! (k+ly) | ly == ry = xa ! (k+lx) | otherwise = case (xa ! mx < ya ! my, k <= mx-lx+my-ly) of (True, True) -> search k (lx,rx) (ly,my) (True, False) -> search (k-(mx-lx)-1) (mx+1,rx) (ly,ry) (False, True) -> search k (lx,mx) (ly,ry) (False, False)-> search (k-(my-ly)-1) (lx,rx) (my+1,ry) where mx = (lx+rx) `div` 2 my = (ly+ry) `div` 2 -- -- Regards, KC

1 0

ANNOUNCE: floatshow-0.1 faster String representations for Double and Float
by Daniel Fischer 18 Apr '11

18 Apr '11

The Show instances for RealFloat types provided in base are very elegant, as they produce the shortest string which 'read' converts back to the original number. That, however, involves a check after each digit has been determined and arithmetic of usually fairly large Integers, which makes these Show instances rather slow. For cases where having the conversion fast is more important than having it produce elegant output, the floatshow package provides alternative conversions, which avoid the checks and reduce the occurrences of large Integers by just producing a sufficiently long output string. The speed gain can be substantial if the numbers have exponents of large absolute modulus, but for the more common case of numbers whose exponents have small absolute modulus, the difference is (although still significant for Double) too small in my opinion to seriously consider replacing the Show instances. Therefore I've put these functions into their own package. In my benchmarks, the speed gain ranges from 4x to 10x for Double and from 1.25x to 5x for Float, so the package may be a useful alternative for tasks requiring the output of many floating point numbers. Sadly, floatshow is non-portable and requires ghc >= 6.12.

1 0

Re: [Haskell-cafe] [Haskell] select(2) or poll(2)-like function?
by Don Stewart 18 Apr '11

18 Apr '11

Redirecting to haskell-cafe@, where this kind of long discussion belongs. On Mon, Apr 18, 2011 at 9:07 AM, Colin Adams <colinpauladams(a)googlemail.com> wrote: > > > On 18 April 2011 16:54, Ertugrul Soeylemez <es(a)ertes.de> wrote: >> >> > >> > Well, *someone* has to worry about robustness and scalability. Users >> > notice when their two minute system builds start taking four minutes >> > (and will be at my door wanting me to fix it) because something didn't >> > scale fast enough, or have to be run more than once because a failing >> > component build wasn't restarted properly. I'm willing to believe that >> > haskell lets you write more scalable code than C, but C's tools for >> > handling concurrency suck, so that should be true in any language >> > where someone actually thought about dealing with concurrency beyond >> > locks and protected methods. The problem is, the only language I've >> > found where that's true that *also* has reasonable tools to deal with >> > scaling beyond a single system is Eiffel (which apparently abstracts >> > things even further than haskell - details like how concurrency is >> > achieved or how many concurrent operations you can have are configured >> > when you start an application, *not* when writing it). Unfortunately, >> > Eiffel has other problems that make it undesirable. >> >> I can't make a comparison, because I don't know Eiffel. > > I do, and I don't recognize what the OP is referring to - I suspect he meant > Erlang. > > -- > Colin Adams > Preston, Lancashire, ENGLAND > () ascii ribbon campaign - against html e-mail > /\ www.asciiribbon.org - against proprietary attachments > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell > >

2 1

Adjoint Folds and Unfolds Or: Scything through the Thicket of Morphisms
by KC 18 Apr '11

18 Apr '11

Just tripped over this: Adjoint Folds and Unfolds Or: Scything through the Thicket of Morphisms Folds and unfolds are at the heart of the algebra of programming. They allow the cognoscenti to derive and manipulate programs rigorously... Ralf Hinze Lecture Notes in Computer Science, 2010, Volume 6120, Mathematics of Program Construction, Pages 195-228 -- -- Regards, KC

1 0

Adjoint Folds and Unfolds Or: Scything through the Thicket of Morphisms
by KC 18 Apr '11

18 Apr '11

Just tripped over this: Adjoint Folds and Unfolds Or: Scything through the Thicket of Morphisms Folds and unfolds are at the heart of the algebra of programming. They allow the cognoscenti to derive and manipulate programs rigorously... Ralf Hinze Lecture Notes in Computer Science, 2010, Volume 6120, Mathematics of Program Construction, Pages 195-228 -- -- Regards, KC

1 0

Summer school on Applied Functional Programming at Utrecht University; deadline for registration May 15
by S. Doaitse Swierstra 18 Apr '11

18 Apr '11

Again we will teach an "Applied Functional Programming Summer in Haskell" school this year at Utrecht University. In the previous two occasions students were all very happy with the school and we plan to repeat this success this year. The intended audience are prospective master students who have been in contact with Functional Programming, e.g. by taking a general course on programming languages, and want to learn more about Haskell and its typical programming patterns. In the previous two years we have taught an introductory part (advanced bachelor level), an advanced part (beginning master level) and a shared part for both groups. Topics covered are, besides some examples of domain specific languages, also monads, monad transformers, arrows, parser combinators and self-analysing programs, underlying principles, type inferencing, etc. Half of the course time is spent on a larger programming exercise; you can also come with a problem of your own if you want, and get help from the Utrecht University Software Technology group in finding the proper Haskell idioms, tools and libraries, for solving it. Important links: -- our own page where we supply information based on questions asked http://www.cs.uu.nl/wiki/bin/view/USCS2011/WebHome -- the poster you can print and hang somewhere (why not your office door): http://www.cs.uu.nl/wiki/pub/USCS2011/WebHome/USCSpos11.pdf -- the official summerschool site where you can register: http://www.utrechtsummerschool.nl/index.php?type=courses&code=H9 Furthermore we ask for your cooperation to bring this announcement under the attention of potential participants. Best, Doaitse Swierstra PS: apologies if you get this mail more than once

1 0