- Haskell-Cafe - Haskell.org

benchmarking c/c++ and haskell
by Vo Minh Thu 16 Sep '10

16 Sep '10

Hi, I would like to benchmark C/C++ and Haskell code. The goal is to improve the Haskell port[0] of smallpt[1]. To make sure my approach was reliable, I got the code of two programs (one in C, the other in Haskell) from a post[2] by Don. The code is reproduced below. When timing the execution of both program, I have a >4x difference. It is said on the blog the programs should have similar performance. I simply don't get the reason of such a difference. I've tried the code on my Atom netbook and also on an older centrino machine. The timing are similar (i.e. the C and Haskell program show >4x difference). Both machines have GHC 6.12.1 on Linux. Would you have an idea? [0] http://hackage.haskell.org/package/smallpt-hs [1] http://www.kevinbeason.com/smallpt/ [2] http://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-working-at-a-h… $ gcc -O2 mean.c -omean-c $ ghc --make -O2 mean.hs -o mean-hs $ time ./mean-c 1e8 50000000.500000 real 0m1.575s user 0m1.513s sys 0m0.000s $ time ./mean-hs 1e8 50000000.5 real 0m6.997s user 0m6.856s sys 0m0.013s -- file mean.hs module Main where import System.Environment import Text.Printf mean :: Double -> Double -> Double mean n m = go 0 0 n where go :: Double -> Int -> Double -> Double go s l x | x > m = s / fromIntegral l | otherwise = go (s+x) (l+1) (x+1) main = do [d] <- map read `fmap` getArgs printf "%f\n" (mean 1 d) /* file mean.c */ #include <stdio.h> #include <stdlib.h> int main (int argc, char **argv) { double d = atof(argv[1]); double n; long a; double b; for (n = 1, a = 0, b = 0; n <= d; b+=n, n++, a++) ; printf("%f\n", b / a); return 0; }

7 12

A question about "threading" state
by michael rice 16 Sep '10

16 Sep '10

I've been playing around with State Monads. Two I looked at earlier used *sequence* and *replicate* but when I came to this one I found myself puzzling over how to structure the problem when there was no predetermined count of how many times to thread the state. ============== Program 1 ============= import Control.Monad import Control.Monad.State type GeneratorState = State (Int, Int) -- lcf (largest common factor) -- lcf :: (Int, Int) -> ((Int, Int), Int) lcf (x, y) | x == y = ((x, y), x) | x < y = ((y, x), 0) | otherwise = ((y, x-y), 0) lcfstate :: GeneratorState Int lcfstate = State (\st -> lcf st) ============== Some output ========= {- *Main> runState lcfstate (24,18) (0,(18,6)) *Main> runState lcfstate (18,6) (0,(6,12)) *Main> runState lcfstate (6,12) (0,(12,6)) *Main> runState lcfstate (12,6) (0,(6,6)) *Main> runState lcfstate (6,6) (6,(6,6)) *Main> runState (sequence $ replicate 5 lcfstate) (24,18) ([0,0,0,0,6],(6,6)) -} {- *Main> evalState (sequence $ replicate 2 lcfstate) (24,18) [0,0] *Main> evalState (sequence $ replicate 3 lcfstate) (24,18) [0,0,0] *Main> evalState (sequence $ replicate 4 lcfstate) (24,18) [0,0,0,0] *Main> evalState (sequence $ replicate 5 lcfstate) (24,18) [0,0,0,0,6] -} =================================== Then I saw the same problem solved here http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm ============== Program 2 ============= import Control.Monad import Control.Monad.ST newtype StateTrans s a = ST( s -> (s, a) ) instance Monad (StateTrans s) where -- (>>=) :: StateTrans s a -> (a -> StateTrans s b) -> StateTrans s b (ST p) >>= k = ST( \s0 -> let (s1, a) = p s0 (ST q) = k a in q s1 ) -- return :: a -> StateTrans s a return a = ST( \s -> (s, a) ) applyST :: StateTrans s a -> s -> (s, a) applyST (ST p) s = p s type ImpState = (Int, Int) getX, getY :: StateTrans ImpState Int getX = ST(\(x,y)-> ((x,y), x)) getY = ST(\(x,y)-> ((x,y), y)) putX, putY :: Int -> StateTrans ImpState () putX x' = ST(\(x,y)->((x',y),())) putY y' = ST(\(x,y)->((x,y'),())) gcdST :: StateTrans ImpState Int gcdST = do x <- getX y <- getY (if x == y then return x else if x < y then do putY (y-x) gcdST else do putX (x-y) gcdST) greatestCommonDivisor x y = snd( applyST gcdST (x,y) ) ============== Some output ========= {- *Main> greatestCommonDivisor 24 18 6-} ==================================== Very impressive. Is this solution typical for problems where the number of times the state must be threaded is dependent on the state itself? Michael

1 0

Generating arbitrary functions with QuickCheck?
by Matias Eyzaguirre 16 Sep '10

16 Sep '10

Hi, I'v been reading a small paper/lesson on writing parser combinators in Haskell, and it seems more or less straightforward. In this case a parser is defined thusly: > type Parser a = String -> Maybe (a, String) And then it goes on to list some simple parsers, and then starts going on about combinators. I was wondering how one would write quickcheck properties for the items presented in the paper, and the answer seemed fairly straightforward for the actual parsers. But how on earth would you write a test for a combinator? Presumable one would need to make the type an instance of Arbitrary. I see two problems: Firstly, as far as i can tell, one cannot declare a type synonym to be an instance of a type class, thus how would you make it an instance of Arbitrary? Secondly, (and more importantly, or at least more interesting) I can see how one would make a generator for simple compound data types, but how on earth do you make a generator produce functions?

5 4

Scraping boilerplate deriving?
by Kevin Jardine 16 Sep '10

16 Sep '10

I have a set of wrapper newtypes that are always of the same format: newtype MyType = MyType Obj deriving (A,B,C,D) where Obj, A, B, C, and D are always the same. Only MyType varies. A, B, C, and D are automagically derived by GHC using the {-# LANGUAGE GeneralizedNewtypeDeriving #-} feature. I would like to use some macro system (perhaps Template Haskell?) to reduce this to something like defObj MyType I've read through some Template Haskell documentation and examples, but I find it intimidatingly hard to follow. Does anyone has some code suggestions or pointers to something similar? Alternatively, is there any way in standard Haskell to define some kind of union class: U = (A, B, C, D) and then using newtype MyType = MyType Obj deriving U which would at least be shorter?

12 19

[PREANNOUNCE] Crypto-API Major Version Bump (0.1.0.0)
by Thomas DuBuisson 16 Sep '10

16 Sep '10

All, Ironing out crypto-api, I have commited the below changes mostly intended to streamline crypto-api and focus it on the main purpose of connecting algorithm developers with slightly higher-level (and generic) function needed by crypto-users. Feel free to object, comment, or recommend additional alterations before 0.1 is released. Padding, NIST KATs for TwoFish, and a generalized/testable CFB mode might appear before release, but no promises. PROJECT MANAGEMENT: Homepage: http://trac.haskell.org/crypto-api/wiki Bug trac: http://trac.haskell.org/crypto-api/report/1 Repo: http://code.haskell.org/crypto-api/ API CHANGES * instance Monad (Either GenError) where ... * cereal >= 0.2 && < 0.3 (was == 0.2.*) * Test.{HMAC,SHA,AES} now exist / are split from Test.Crypto ** SHA and HMAC tests are new and from NIST CAVP KAT collection - no more rolling your own testing! * Test.ParseNistKATs doesn't use Parsec and has a barebones interface. * Crypto.Random does not export "AsRG" or "Splittable" (see change log, 'random' build dep removed) DEPENDENCIES While I've never had objections to dependencies (this is what cabal is for and removing unused code is what GHC+linkers are for), I feel this is a good minimum and hope others agree. Some potential users made noise about having both Binary and Cereal and just the number of deps in general. * deps removed: binary, parsec, random (and indirectly: time, old-locale) * deps remaining: base, tagged, bytestring, cereal, filepath, directory * indirect deps remaining: data-default, containers, arrays CHANGE LOG (since 0.0.0.2) * Bump 'cereal' version bound to include 0.3 * instance Monad (Either GenError) -- that was an obvious oversight * Remove the 'binary' dep. (cereal makes more sense and can be leveraged in Binary.{Get,Put} routines). * Removed the 'parsec' dep, which was only needed for Test.* but not even that now. * Updated the CPP tests for Windows in System.Random.Crypto (still need a tester) * Fixed up the testing infrastructure. Algorithms now use separate modules (Test.SHA, Test.HMAC, Test.AES). more NIST KATs included: ~1000 SHA tests, hundreds of SHA HMAC tests. * Fixed ugly bug for HMACs using keys > blockSize (eep! Obvious interop problem, but there was no-less security in the hmac result) * Removes the 'random' dep and by extension removes indirect deps on time and old-locale. Random was only used to provide trivial lifting of a newtype wrapped CryptoRandomGen instances into the RandomGen class, which was of questionable sense in the first place. TESTING I've been using the HEAD crypto-api, specifically Test.{HMAC,SHA,AES}, Crypto.{Classes,HMAC} and Benchmark.{BlockCipher,Hash}, with instances for SimpleAES, cryptohash, pureMD5, and SHA packages with good success. My HEAD DRBG (NIST SP 800-90) code uses Crypto.Random and Crypto.Classes libraries to good effect, thus far things seem to flow well. Cheers, Thomas

2 2

Simple Parsec example, question
by Peter Schmitz 16 Sep '10

16 Sep '10

Simple Parsec example, question I am learning Parsec and have been studying some great reference and tutorial sites I have found (much thanks to the authors), including: http://legacy.cs.uu.nl/daan/download/parsec/parsec.html#UserGuide http://legacy.cs.uu.nl/daan/download/parsec/parsec.html#ReferenceGuide http://book.realworldhaskell.org/read/using-parsec.html http://lstephen.wordpress.com/2007/06/19/first-go-with-parsec/ http://jonathan.tang.name/files/scheme_in_48/tutorial/overview.html http://www.defmacro.org/ramblings/lisp-in-haskell.html I'm having trouble coding a simple parser to count the number of lines in a text file. "lineCount" fails to compile; the compiler error text is below it. Any advice, code, etc. would be appreciated. For those using Gtk2Hs + Glade, I have included the glade file after the Haskell code, in case you want to try it. (You will need to remove the leading "> " and fix some lines that the email wrapped.) If you do wish to offer code, feel free to remove or rewrite: eol, textLines and lineCount entirely. I'm looking for the simplest way to code this. Thanks very much, -- Peter > -- A parsing demo, using: > -- Haskell + Gtk2Hs + Glade (GtkBuilder) + Parsec > module Main where > > -- import Data.IORef > import Graphics.UI.Gtk > import Graphics.UI.Gtk.Builder > import Graphics.UI.Gtk.Selectors.FileChooser > -- import System.Cmd -- e.g., for invoking a shell cmd > import System.Glib.GError > import Text.ParserCombinators.Parsec > > main :: IO () > main = do > initGUI > > -- create builder; load UI file > builder <- builderNew > handleGError (\(GError dom code msg) -> fail msg) $ > builderAddFromFile builder "demo.glade" > -- Error message would look something like: > -- app.exe: user error (Failed to open file 'app.glade': > -- No such file or directory) > > -- get widget handles (reduce boilerplate?) > mainWindow <- builderGetObject builder castToWindow "mainWindow" > pickFileButton <- > builderGetObject builder castToFileChooserButton "pickFileButton" > parseButton <- builderGetObject builder castToButton "parseButton" > exitButton <- builderGetObject builder castToButton "exitButton" > > -- signal handlers -- > > -- parse selected file > onClicked parseButton $ do > file <- fileChooserGetFilename pickFileButton > > case file of > Nothing -> do > putStrLn "\nPlease first select a file." > return () > Just file -> do > putStrLn $ "\nParsing file: " ++ show file > result <- parseFromFile lineCount file > case (result) of > Left err -> print err > Right x -> putStrLn $ "Line count = " ++ show x > return () > > -- exit > onDestroy mainWindow mainQuit > onClicked exitButton mainQuit > > -- go > widgetShowAll mainWindow > mainGUI > > ----------------- > eol = char '\n' > > -- from RWH; perhaps use in future: > -- eol = try (string "\n\r") > -- <|> try (string "\r\n") > -- <|> string "\n" > -- <|> string "\r" > -- <?> "end of line" > > textLines = endBy eol > > lineCount :: Parser Int > lineCount = do > xs <- textLines > return (length xs) > > > -- demo.hs:72:3: > -- Couldn't match expected type `GenParser Char () Int' > -- against inferred type `GenParser Char st sep -> b' > -- In a stmt of a 'do' expression: xs <- textLines > -- In the expression: > -- do { xs <- textLines; > -- return (length xs) } > -- In the definition of `lineCount': > -- lineCount = do { xs <- textLines; > -- return (length xs) } -- demo.glade follows -- > <?xml version="1.0"?> > <interface> > <requires lib="gtk+" version="2.16"/> >  > <object class="GtkWindow" id="mainWindow"> > <property name="visible">True</property> > <property name="title" translatable="yes">demo v.8</property> > <child> > <object class="GtkVBox" id="vbox1"> > <property name="visible">True</property> > <property name="border_width">6</property> > <property name="orientation">vertical</property> > <property name="spacing">10</property> > <child> > <object class="GtkLabel" id="label1"> > <property name="visible">True</property> > <property name="tooltip_text" translatable="yes">You can hover over the buttons below for some information about them. > > You can also resize this window, to make the buttons bigger. > </property> > <property name="label" translatable="yes">Demo: Haskell + Gtk2Hs + Glade (GtkBuilder) + Parsec > </property> > </object> > <packing> > <property name="position">0</property> > </packing> > </child> > <child> > <object class="GtkHBox" id="hbox1"> > <property name="visible">True</property> > <property name="spacing">5</property> > <child> > <object class="GtkFrame" id="pickFileframe"> > <property name="visible">True</property> > <property name="tooltip_text" translatable="yes">Use this File Chooser widget to select the file to parse. > </property> > <property name="label_xalign">0</property> > <property name="shadow_type">none</property> > <child> > <object class="GtkAlignment" id="alignment1"> > <property name="visible">True</property> > <property name="left_padding">12</property> > <child> > <object class="GtkFileChooserButton" id="pickFileButton"> > <property name="visible">True</property> > <property name="title" translatable="yes">Select file</property> > </object> > </child> > </object> > </child> > <child type="label"> > <object class="GtkLabel" id="pickFileLabel"> > <property name="visible">True</property> > <property name="label" translatable="yes"><b>Select file to parse:</b></property> > <property name="use_markup">True</property> > </object> > </child> > </object> > <packing> > <property name="position">0</property> > </packing> > </child> > <child> > <object class="GtkButton" id="parseButton"> > <property name="label" translatable="yes">P_arse</property> > <property name="visible">True</property> > <property name="can_focus">True</property> > <property name="receives_default">True</property> > <property name="tooltip_text" translatable="yes">Use this to parse the file you have selected.</property> > <property name="use_underline">True</property> > </object> > <packing> > <property name="position">1</property> > </packing> > </child> > <child> > <object class="GtkButton" id="exitButton"> > <property name="label" translatable="yes">E_xit</property> > <property name="visible">True</property> > <property name="can_focus">True</property> > <property name="receives_default">True</property> > <property name="tooltip_text" translatable="yes">Exit this program and close both windows.</property> > <property name="use_underline">True</property> > </object> > <packing> > <property name="position">2</property> > </packing> > </child> > </object> > <packing> > <property name="position">1</property> > </packing> > </child> > </object> > </child> > </object> > </interface> -- end --

3 4

try, seq, and IO
by Jeroen van Maanen 15 Sep '10

15 Sep '10

The past year I have been working on a port of my machine learning project named LExAu from Java to Haskell. I'm still very glad I took the jump, because the complexity curve appears to be log shaped rather than exp shaped. In one year I almost got to the functionality that had taken me five years to produce in Java (of course it helped a lot that I had a working prototype this time). There is one thing that still bothers me though: when I write seq or $! it doesn't seem to have any effect! Currently I am trying to add some exception handling to help me debug the system, but the code that I managed to produce depends on the logging statement to produce the desired result. :-( It looks like this, and only works when I uncomment the line '-- logger "Check sum": [...]', otherwise the exception is caught by the try around the body of the thread that this code runs in: do logger "Received update" [showString label, logs update] result <- try $! do maybeUpdatedModel <- return $ f update startModel theCheckSum <- return $ liftM checkSum maybeUpdatedModel -- logger "Check sum" [showString label, shows theCheckSum] return $! seq theCheckSum maybeUpdatedModel maybeNextModel <- case result of Right theMaybeNextModel -> return theMaybeNextModel Left exception -> do let exc :: SomeException exc = exception logger "Exception" [showString label, shows exception] return Nothing logger "Maybe next model" [showString label, logs maybeNextModel] For more context see: http://lexau.svn.sourceforge.net/viewvc/lexau/branches/totem/src/LExAu/Pipe… after line 241. Can someone explain why a few showStrings a shows and a putStrLn are more effective in forcing the check sum to be computed (which necessarily evaluates the complete updated model and reveals the lurking exception) than the seq on the line just below the logging statement? Cheers, Jeroen

4 3

Re: [Haskell-cafe] Set of Haskell programs
by Chris BROWN 15 Sep '10

15 Sep '10

Hi Ivan, HaRe itself is not Haskell 98, but for testing purposes we have used various Haskell 98 programs and test suites. One rather large full Haskell 98 program that we have used to test HaRe is nhc: http://www.cs.york.ac.uk/fp/nhc98/ nhc also comes with various Haskell 98 test suites, all of which were very useful to test various transformations (and this is all Haskell 98). Aside from nhc and its test suites, there are also exercises from Simon's text on Haskell from his webpage, that we have also used to test various refactorings: http://www.cs.kent.ac.uk/people/staff/sjt/craft2e/Code/code.html This includes some nice examples for Huffman encoding and parsing, which are all Haskell 98. I hope this helps, Kind regards, Chris. > > >> From: Ivan Lazar Miljenovic <ivan.miljenovic(a)gmail.com> >> Date: 15 September 2010 11:23:54 GMT+01:00 >> To: Enrique Martín <emartinm(a)fdi.ucm.es> >> Cc: haskell-cafe(a)haskell.org >> Subject: Re: [Haskell-cafe] Set of Haskell programs >> >> 2010/9/15 Enrique Martín <emartinm(a)fdi.ucm.es>: >>> Hello, >>> >>> I would want to ask if there is any set of "real" Haskell 98 programs >>> publicly available. I am working on a program transformation and I would >>> want to test it with several "real" programs. I think it is a good idea to >>> have a set of standard programs that people could use to check the >>> efficiency of their transformation/optimizations. >> >> HaRe is presumably. >> >> -- >> Ivan Lazar Miljenovic >> Ivan.Miljenovic(a)gmail.com >> IvanMiljenovic.wordpress.com >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >

1 0

Set of Haskell programs
by Enrique Martín 15 Sep '10

15 Sep '10

Hello, I would want to ask if there is any set of "real" Haskell 98 programs publicly available. I am working on a program transformation and I would want to test it with several "real" programs. I think it is a good idea to have a set of standard programs that people could use to check the efficiency of their transformation/optimizations. Thank you very much in advance, Enrique.

3 2

Stack traces in GHC
by Mihai Maruseac 15 Sep '10

15 Sep '10

Hi, Just did a preview of bug #3693 [1] and saw that there are a few patches issued there. Does this mean that the problem is solved and there would be stack traces in a future version of GHC? I'll test the patches in 24 hours, when I'll be back at home. -- Mihai [1]: http://www.khronos.org/webgl/wiki/Tutorial

2 2