- Haskell-Cafe - Haskell.org

Adjoint Folds and Unfolds Or: Scything through the Thicket of Morphisms
by caseyh＠istar.ca 19 Apr '11

19 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

1 0

Re: [Haskell-cafe] [Haskell] select(2) or poll(2)-like function?
by Henning Thielemann 19 Apr '11

19 Apr '11

On Sun, 17 Apr 2011, Matthias Kilian wrote: > is there something like select(2) or poll(2) available in the > standard (HP) libraries? I hoogled around a little bit but didn't > find anything. (Something like this will be crucial for networking > stuff listening on v4 and v6 sockets at the same time) A very basic thing to start from: http://code.haskell.org/~thielema/poll/ It is still subject to change. We are planning to use this in alsa-seq.

1 0

Errata for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell
by caseyh＠istar.ca 19 Apr '11

19 Apr '11

-- Errata for "Pearls of Functional Algorithm Design" by Richard Bird, -- 2010, page 25 #Haskell -- I don't like this solution it suffers from "indexitis" which -- Bird talks about in the chapter on Sudoku. -- I can see why lists are liked, they avoid "indexitis" at -- the cost of chopping and concatenating them. -- One of the advantages of functional programming is supposed to be less bookkeeping. 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

1 0

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

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 19 Apr '11

19 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