March 2010 - Haskell-Cafe

Parsec to parse tree structures?
by david fries 18 Mar '10

18 Mar '10

Hello Café Some time ago I wrote a parser for a project of one our customers. The format was proprietary and binary. The data was structured as a tree with tables pointing to sub tables farther in the file. (Well actually there was one or two cases where branches joined together, so I guess it was a directed graph.) Also it had no defined endianess, some tables were bigendian others were little endian and some were in their very own in-house-endianess. All in all, the typical binary data structure that has been in use and continuously extended for the last 15 years. You know the kind. Oddly enough, our customer never bothered to write a parser of their own. I wonder why. My parser was written in C# and wasn't particularly elegant, but it worked reliably. I was wondering how you would parse tree-like structures with Parsec (or other functional parsers)? Up to know, all examples I've seen were of sequential data. To parse trees, you'd essentially need to be able to follow pointers, parse whatever is there and then jump back. I guess I'd have to mess around with the internal state of the parser to do that, which is something I'd rather avoid. regards, dave

5 10

How to improve its performance ?
by zaxis 18 Mar '10

18 Mar '10

import Data.List combination :: [a] -> [[a]] combination [] = [[]] combination (x:xs) = (map (x:) (combination xs) )++ (combination xs) samp = [1..100] allTwoGroup = [(x, samp\\x) | x <- combination samp] The above code is used to calculate all the two groups from sample data ? It is very slow ! Sincerely! ----- fac n = let { f = foldr (*) 1 [1..n] } in f -- View this message in context: http://old.nabble.com/How-to-improve-its-performance---tp27940036p27940036.… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 10

Parsec monad transformer with IO?
by Stefan Klinger 18 Mar '10

18 Mar '10

Hello! Nice, Parsec 3 comes with a monad transformer [1]. So I thought I could use IO as inner monad, and perform IO operations during parsing. But I failed. Monad transformers still bend my mind. My problem: I don't see a function to actually lift the IO operation into the ParsecT. It should be something like lift :: IO a -> ParsecT s u IO a The following is a toy example, I just could not make something smaller: Let's parse command line arguments (tokens are Strings), and execute them while parsing. > import Text.Parsec.Prim > import Text.Parsec.Pos > import Text.Parsec > import System.Environment ( getArgs ) Command line interface parser (Clip) type: Inner monad IO, user state u, tokens are Strings, returns something typed a. > type Clip u a = ParsecT [String] u IO a Source code position for command line arguments: The line is always 1, column n represents the n-th command line argument. > nextPos p _ _ = incSourceColumn p 1 Two primitive parsers, one for flags (with a dash) and one for other arguments: clipFlag "x" accepts the command line flag "-x", and returns "x". > clipFlag :: String -> Clip u String > clipFlag x > = tokenPrim > id > nextPos > (\y -> if '-':x == y then Just x else Nothing) clipValue accepts any command line argument that does not tart with a dash '-'. > clipValue :: Clip u String > clipValue > = tokenPrim id nextPos test > where > test ('-':_) = Nothing > test other = Just other Now the test program: Load files given on the command line, and sum up their word count, until -p is given. -p prints the current word count and sets the counter to zero. Further files may be processed then. At the end, show the sum of all word counts. Example: foo has 12 words, bar has 34 words: main foo -p bar -p foo bar -p Counted 12 words, reset counter. Counted 34 words, reset counter. Counted 46 words, reset counter. Grand total: 92 > type CurrentCount = Int -- the user state used with Clip/ParsecT. root implements the command line grammar (<filename>+ "-p")* and returns the sum of all word counts. > root :: Clip CurrentCount Int > root > = do ns <- many (many1 loadFile >> printSize) > eof > return $ sum ns Interprets each non-flag on the command line as filename, loads it, counts its words, and adds the count to the state. > loadFile :: Clip CurrentCount () > loadFile > = do -- expect a filename > filename <- clipValue > -- load the file: IO > content <- lift $ readFile filename > -- add wordcount to state > modifyState ((+) (length $ words content)) If -p shows up on the command line, print accumulated count, reset counter to cero and return count for grand-total calculation. > printSize :: Clip CurrentCount Int > printSize > = do -- expect flag -p > clipFlag "p" > -- print current word count: IO > n <- getState > lift . putStrLn $ "Counted "++show n++" words, reset counter." > -- reset user state to zero, return word count for grand total > putState 0 > return n main just runs the root parser on the command line arguments and checks the result. > main > = do result <- getArgs >>= runParserT root 0 "command line" > case result of > Left err -> error $ show err > Right n -> putStrLn $ "Grand total: "++show n So where is the lift function? Does it exist? Here, I need your help. > lift :: IO a -> ParsecT s u IO a > lift = undefined Any comments are appreciated. Thank you! Stefan ____________________ [1] http://hackage.haskell.org/packages/archive/parsec/3.0.0/doc/html/Text-Pars… -- Stefan Klinger o/klettern /\/ bis zum send plaintext only - max size 32kB - no spam \ Abfallen http://stefan-klinger.de

7 8

Happstack/Apache configuration problem
by Maciej Podgurski 18 Mar '10

18 Mar '10

Hi, I'm not sure if this is the right place to ask because the problem may lay in my Apache or system configuration. I use the Apache proxy module to forward a HTTP request from port 80 to a Happstack application listening on port 8000 via `ProxyPass / http://localhost:8000/' on Windows XP. When calling http://my_domain in the browser, I get `503 service temporarily unavailable' and in the apache logs `proxy: HTTP: attempt to connect to 127.0.0.1:8000 (localhost) failed'. So I tried to access http://127.0.0.1:8000 manually in the browser but got a connection error, while http://[::1]:8000/ works perfectly and displays the content returned from the Happstack application. Maybe I'm wrong, but isn't the problem here that Happstack only accepts IPv6 addresses, while Apache forwards an IPv4 request? Best wishes, Maciej

1 0

Re: searching a function by providing examples of input/ouput pairs
by Janis Voigtländer 18 Mar '10

18 Mar '10

Paul Brauner schrieb: > Hi, > > I was looking at hoogle documentation when I remembered that there is > some nice, but quite unusable, feature of squeak (smalltalk) which > allows you to search function in the library by giving a list of pairs > of inputs/ouputs. > > When I'm saying that it is quite unusable, I mean that squeak has to try > _every_ function, some of which may be very slow to deliver a result, or > require some side effects. > > But, piggibacking such a feature on top of hoogle would surely be more > efficient: > > 1. infer types for arguments and outout > 2. look for matching functions using google > 3. test them > > Has anyone tried that before? If not I would be glad to. Sounds like something useful to have. And you could even have the system use a list of pairs of inputs/outputs to give you functions that are *not* yet in any library. :-) http://www.haskell.org/communities/11-2009/html/report.html#sect6.11.1 -- Jun.-Prof. Dr. Janis Voigtländer http://www.iai.uni-bonn.de/~jv/ mailto:jv@iai.uni-bonn.de

2 1

Call for community volunteers
by Malcolm Wallace 18 Mar '10

18 Mar '10

As you may know, community.haskell.org (also hosting code.h.o, trac.h.o, etc) exists as a resource to enable Haskellers to publish and collaborate on open source projects. The current admin team for this virtual host finds itself with a lack of time (and occasionally expertise) to maintain the services and respond to user requests. Hence, we are calling for new volunteers to join the c.h.o admin team. Ideally, you will have some skills in administering one or more of trac mail servers apache web server debian/linux systems and the willingness to learn the others, plus a hour or two a week to deal with requests, either coming in through the ticket system, or in the case of some failures, email or IRC. (There is a backlog of outstanding tickets to resolve too.) Apply to admin(a)community.haskell.org telling us how you think you can help. Regards, Malcolm

1 0

[Announcement] Fedora 12 rpms for leksah 0.8.0.1 now available
by Lakshmi Narasimhan 18 Mar '10

18 Mar '10

Leksah - 0.8.0.1 rpms for Fedora 12 now available <goog_1268906153764>http://leksah.org/download.html About Leksah: *Leksah* is the Haskell IDE of choice. It is written in Haskell, uses Gtk, and runs on Linux, Windows and Mac OS X. Leksah is a practical tool to support the Haskell development process. It requires the Glasgow Haskell Compiler (GHC). *Installation Instructions * *Procedure for x86 platform* Before proceeding to install the leksah rpms, Uninstall leksah-0.6.1, ghc-binary-devel packages, incase you have installed them from the leksah download page. Use the following command yum remove leksah ghc-binary-devel Download this tar.gz package http://leksah.org/packages/dependencies-0.8.0.1.fc12.i386.tar.gz Extract the rpms from the tar.gz file. Download the following two rpms (links below) and put the rpms into the directory where the dependencies are located. http://leksah.org/packages/leksah-0.8.0.1-1.fc12.i386.rpm http://leksah.org/packages/leksah-server-0.8.0.1-1.fc12.i386.rpm Select the rpms, right click and select Install. To install from command line, change into the extracted directory, become superuser and type yum --nogpgcheck install ghc-binary-devel-0.5.0.2-1.fc12.i386.rpm ghc-deepseq-devel-1.1.0.0-1.fc12.i386.rpm ghc-ltk-devel-0.8-1.fc12.i386.rpm ghc-binary-shared-devel-0.8-1.fc12.i386.rpm ghc-hslogger-devel-1.0.10-1.fc12.i386.rpm haddock-leksah-2.5.0-1.fc12.i386.rpm leksah-0.8.0.1-1.fc12.i386.rpm leksah-server-0.8.0.1-1.fc12.i386.rpm *Procedure for x86_64 platform* Download this tar.gz package. http://leksah.org/packages/dependencies-0.8.0.1.fc12.x86_64.tar.gz Extract the rpms from the tar.gz file. Download the following two rpms (links below) and put the rpms into the directory where the dependencies are located. http://leksah.org/packages/leksah-0.8.0.1-1.fc12.x86_64.rpm http://leksah.org/packages/leksah-server-0.8.0.1-1.fc12.x86_64.rpm Select the rpms, right click and select Install. To install from command line, change into the extracted directory, become superuser and type yum --nogpgcheck install ghc-binary-devel-0.5.0.2-1.fc12.x86_64.rpm ghc-hslogger-devel-1.0.10-1.fc12.x86_64.rpm ghc-binary-shared-devel-0.8-1.fc12.x86_64.rpm ghc-ltk-devel-0.8-1.fc12.x86_64.rpm ghc-deepseq-devel-1.1.0.0-1.fc12.x86_64.rpm haddock-leksah-2.5.0-1.fc12.x86_64.rpm leksah-0.8.0.1-1.fc12.x86_64.rpm leksah-server-0.8.0.1-1.fc12.x86_64.rpm *Running leksah *Once installation is completed, leksah menu item appears under * Applications->Programming* (in GNOME) and *Development* menu of KDE. -- Regards Lakshmi Narasimhan T V

2 1

STM Skip list implementation
by Peter Robinson 17 Mar '10

17 Mar '10

I've implemented a skip list that works in the STM monad. A skip list is a probabilistic data structure similar to a balanced tree. The main advantage of a skip list is that it doesn't require rebalancing, making it particularly suitable for concurrent programming. Here are the docs: http://darcs.monoid.at/tskiplist/dist/doc/html/tskiplist/Control-Concurrent… It's not yet on hackage as the implementation is very incomplete and mostly untested. However, you can download a cabalized package from here: http://darcs.monoid.at/tskiplist/dist/tskiplist-0.0.0.tar.gz Darcs repository: http://darcs.monoid.at/tskiplist/ Peter

3 3

Iteratee performance
by Vasyl Pasternak 17 Mar '10

17 Mar '10

Hi Cafe, Yesterday I played with iteratee package, and wanted to check its performance. I tried to count lines in a file, as Oleg in his famous lazy_vs_correct[1] article. The results somewhat disappointed me. The statistics and code follows, but shortly: lazy bytestring is the fastest, iteratee with bytestrings 10 times slower than lazy bytestring. When comparing lazy string and iteratee with [Char], than their results were close, but lazy string reading uses less memory and was a bit faster (20%). I performed test on 250Mb file with 5 millions lines. Now I am figuring out, is these tests are correct and this is ordinary behavior, so iteratee not so fast as I thought, or there is some mistake in my code. [1] http://okmij.org/ftp/Haskell/Iteratee/Lazy-vs-correct.txt --------------------- TIMING RESULTS ---------------------- $ time wc -l 5000000.txt 5000000 5000000.txt real 0m0.314s user 0m0.184s sys 0m0.124s $ time ./bytestring_test 5000000.txt 5000000 real 0m0.817s user 0m0.616s sys 0m0.200s $ time ./bytestring_iteratee_test 5000000.txt real 0m7.801s user 0m7.552s sys 0m0.252s $ time ./string_test 5000000.txt 5000000 real 0m47.427s user 0m46.675s sys 0m0.648s $ time ./string_iteratee_test 5000000.txt 5000000 real 0m59.225s user 0m57.680s sys 0m0.840s -------------------------- RTS INFO -------------------------------- ./bytestring_test 5000000.txt +RTS -sbs.out 807,225,096 bytes allocated in the heap 122,240 bytes copied during GC 59,496 bytes maximum residency (1 sample(s)) 22,424 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 1540 collections, 0 parallel, 0.03s, 0.02s elapsed Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 0.59s ( 0.79s elapsed) GC time 0.03s ( 0.02s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 0.62s ( 0.82s elapsed) %GC time 4.5% (2.8% elapsed) Alloc rate 1,372,743,081 bytes per MUT second Productivity 95.5% of total user, 72.1% of total elapsed ----- ./bytestring_iteratee_test 5000000.txt +RTS -siter.out 11,024,100,312 bytes allocated in the heap 893,436,512 bytes copied during GC 95,456 bytes maximum residency (1 sample(s)) 23,216 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 21030 collections, 0 parallel, 2.51s, 2.45s elapsed Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed INIT time 0.00s ( 0.02s elapsed) MUT time 6.37s ( 6.66s elapsed) GC time 2.52s ( 2.45s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 8.88s ( 9.12s elapsed) %GC time 28.3% (26.9% elapsed) Alloc rate 1,731,061,437 bytes per MUT second Productivity 71.7% of total user, 69.8% of total elapsed ----- ./string_test 5000000.txt +RTS -sstr.out 38,561,155,264 bytes allocated in the heap 9,862,623,816 bytes copied during GC 223,080 bytes maximum residency (5026 sample(s)) 47,264 bytes maximum slop 2 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 68525 collections, 0 parallel, 22.50s, 22.51s elapsed Generation 1: 5026 collections, 0 parallel, 1.38s, 1.36s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 22.80s ( 23.55s elapsed) GC time 23.87s ( 23.87s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 46.67s ( 47.42s elapsed) %GC time 51.1% (50.3% elapsed) Alloc rate 1,691,170,222 bytes per MUT second Productivity 48.9% of total user, 48.1% of total elapsed ----- ./string_iteratee_test 5000000.txt +RTS -sstriter.out 40,164,683,672 bytes allocated in the heap 7,108,638,256 bytes copied during GC 212,624 bytes maximum residency (821 sample(s)) 50,264 bytes maximum slop 2 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 75791 collections, 0 parallel, 33.14s, 33.75s elapsed Generation 1: 821 collections, 0 parallel, 0.56s, 0.63s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 23.99s ( 24.84s elapsed) GC time 33.69s ( 34.38s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 57.68s ( 59.22s elapsed) %GC time 58.4% (58.1% elapsed) Alloc rate 1,674,540,397 bytes per MUT second Productivity 41.6% of total user, 40.5% of total elapsed ------------------ SOURCECODE ----------------------------- $ cat bytestring_test.hs import System.Environment import Control.Monad import qualified Data.ByteString.Lazy.Char8 as B count s = liftM (length . B.lines) (B.readFile s) main = do [f] <- getArgs print =<< count f --------------- $ cat bytestring_iteratee_test.hs import qualified Data.Iteratee.IO as I import qualified Data.Iteratee as I import qualified Data.Iteratee.Char as I import qualified Data.Iteratee.WrappedByteString as I import System.Environment import Control.Monad count s = I.fileDriverRandom (cnt) s cnt :: (Monad m, Functor m) => I.IterateeG I.WrappedByteString Char m Int cnt = I.joinI $ I.enumLines I.length main = do [f] <- getArgs print =<< count f ------------------ $ cat string_test.hs import System.Environment import Control.Monad count s = liftM (length . lines) (readFile s) main = do [f] <- getArgs print =<< count f ---------------------- $ cat string_iteratee_test.hs import qualified Data.Iteratee.IO as I import qualified Data.Iteratee as I import qualified Data.Iteratee.Char as I import qualified Data.Iteratee.WrappedByteString as I import System.Environment import Control.Monad count s = I.fileDriverRandom (cnt) s cnt :: (Monad m, Functor m) => I.IterateeG [] Char m Int cnt = I.joinI $ I.enumLines I.length main = do [f] <- getArgs print =<< count f Best regards, Vasyl

6 6

compiling 32 bits haskell program on 64 bits linux
by Vincent Hanquez 17 Mar '10

17 Mar '10

Hi Cafe, I was looking for a way to generate 32 bits haskell binary on a 64 bits linux. I've looked at the user guide and tried to use the -fvia-C with -optc -m32 but the generated C file doesn't compile with lots of error messages like the following: $ ghc -o hello hello.hs -fvia-C -optc "-m32" In file included from /usr/lib/ghc-6.10.4/include/Stg.h:206, from /tmp/ghc15772_0/ghc15772_0.hc:3:0: /usr/lib/ghc-6.10.4/include/Regs.h:235:0: error: invalid register name for ‘R4’ I can't find any others parameters that seems to do anythings about the code generation or around the C compiler. so, does anyone knows if it's possible ? or have some documentation/link about this kind of things ? Thanks, -- Vincent

4 5