- Haskell-Cafe - Haskell.org

STM Skip list implementation
by Peter Robinson 18 Mar '10

18 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

Re: [Haskell-cafe] Parsec to parse tree structures?
by John Lato 17 Mar '10

17 Mar '10

Hi Dave, > From: david fries <djf(a)gmx.ch> > > 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. > > 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. Have you seen Edward Kmett's Parsing Trifecta talk/slides, available at http://comonad.com/reader/2009/iteratees-parsec-and-monoid/ ? I think a similar approach would allow you to parse this data structure. The trick is to create a data source that can read from arbitrary locations. Also see http://okmij.org/ftp/Haskell/Iteratee/Tiff.hs for an iteratee-based TIFF reader. TIFF files have a similar structure, so this code could apply pretty directly. The parsing is quite low-level, but you could use iteratee-parsec [1] or attoparsec-iteratee [2] to use parser combinators with this technique. [1] http://hackage.haskell.org/package/iteratee-parsec [2] http://hackage.haskell.org/package/attoparsec-iteratee

2 1

Mini-announce: AC-Color 1.1.3
by Andrew Coppin 17 Mar '10

17 Mar '10

I just uploaded a new version of the ever-unpopular AC-Colour package. (Yes, there's a country where it's spelled that way.) What it already did: Provides a simple strict unboxed RGB colour type, with arithmetic. The three channels can be either Double or Word8. (And there's some low-level hackery to convert between the two. For some reason just using "floor" is awesomely slow, but talking to GHC.Prim directly is much, much faster... which unfortunately makes this package far less portable than it should be!) What it does now: Colour maps. Give it some control points, and it'll (linearly) interpolate between them to give you a function Double -> Colour. (I haven't seen anything else on Hackage that will do this out-of-the-box. I've seen linear blends between two colours, but not fully automatic piece-wise linear maps like this.) Now obviously none of this is terribly earth-shattering. But I find myself needing this often enough that it's annoying to have to spend 10 minutes coding and debugging it every single time I want it. Maybe somebody else will find a use for it too. I paid special attention to trying to make the colour maps as general as possible. (E.g., the parameter range isn't limited to [0..1], it's arbitrary. Going off the end of the range produces sensible results. You can make the map loop. And so on.) Maybe if I'm feeling ambitious I'll try 2D colour maps. (Of course, the problem there is that your control points need not be coplanar - or even form a regular grid!)

2 2

ANNOUNCE: Mac and Windows installers for Leksah 0.8 prerelease available
by Hamish Mackenzie 17 Mar '10

17 Mar '10

We have uploaded first pass at Windows and OS X binaries for 0.8. They are both built using GHC 6.12.1. Installation: Make sure ghc 6.12.1 is installed. Take care that wget and grep are on your PATH. Please try them out if you can and let us know if you find any issues. http://leksah.org/news.html

2 1

compiler management for Haskell a la RVM?
by Mark Wotton 17 Mar '10

17 Mar '10

RVM (at http://rvm.beginrescueend.com) is a rather nice tool for managing multiple ruby installations - it gives support for switching between ruby environments (similar to gcc_select and friends), and also exporting lists of packages so that you can easily bring up a given set of gems in any of the interpreters. Do we have any similar system for ghc/cabal? I quite frequently find myself switching between 6.10 and 6.12 for various things, and it's always a bit painful to get your environment up to speed. Is there a golden road for this stuff, or do the compiler hackers here just munge the PATH? cheers Mark

4 3

th-kinds v0.0.0
by Louis Wasserman 17 Mar '10

17 Mar '10

I'm going to phrase this as a challenge, because I think that's likely to get the best response: I just released a package, th-kinds<http://hackage.haskell.org/package/th-kinds>, which attempts to automatically infer the kind of a specified type, type constructor, type family, type class, or pretty much anything else that has a kind. This package was developed in response to a sort-of challenge from Brent Yorgey on #haskell to create this functionality. So, uh, I stayed up last night until 5 am learning unification algorithms and implementing this...heh. It rolls its own kind inference, so I don't know if it's adequately powerful to handle all the wacky types you can construct. Things I have tested it on: - IO and ST - Many primitive types, including unboxed tuples and State# - mtl - newtype Fix f = Fix (f (Fix f)) - data Tree a = Leaf a | Bin (Tree a) (Tree a) - data Foo a b = a (tests proper defaulting behavior) - A type family from my old TrieMap package with kind -- I kid you not -- ((* -> *) -> ((* -> *) -> * -> *) -> (* -> *) -> * -> * -> *) Things that it will not work on, and that I don't think will change: - GADT types that cannot be reified by TH. Essentially, I think this is "the set of GADT data types that actually couldn't be implemented without GADTs." Not sure, though. In any event, at the moment, I don't think there's any hope of handling GADTs in TH at this point, so I don't really object to this problem. Anyway, y'all should attempt to break th-kinds. Tell me if you can construct a type for which my inference checker breaks, but not because you get an error message saying "Can't reify a GADT data constructor..." By the way, I'd like to bump these<http://hackage.haskell.org/trac/ghc/ticket/3916> tickets <http://hackage.haskell.org/trac/ghc/ticket/3920>. They're certainly related, but I'm not sure if they're genuinely equivalent. It's really irritating, though, that kind parsing is so broken in TH, and I think that a TH backend guru should be able to figure out where there's a foldr instead of a foldl... th-kinds includes a workaround to this bug, but if the bug is fixed, it'll break again. Yuck, bugs. Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

4 4

ANNOUNCE: AusHac2010
by Alex Mason 17 Mar '10

17 Mar '10

G'day all, Over the last few days, Ivan Miljenovic and I have been gauging interest in having an Australian Haskell Hackathon. After some rather encouraging interest, we've decided to get the ball rolling by making a wiki page that we can use to organise the event: [http://www.haskell.org/haskellwiki/AusHac2010] If you're interested in coming, please put your name down on the list (or email me and I'll do it for you if you don't have an account). The more people we can get, the better it will be, and the more productive our work will be. So if you want to come along, play with some cool code, help out the community, and just meet an awesome bunch of like minded people, then we want to hear from you! Cheers, Alex Mason

1 0

Proposal: Australian Hackathon
by Ivan Miljenovic 17 Mar '10

17 Mar '10

Would other Australians be interested in having our own Hackathon (why should all those northerners have all the fun)? I'm thinking about organising it to be in the July break between university semesters. There was a previous consideration a few years back to have an OzHaskell group (http://www.haskell.org/haskellwiki/OzHaskell) but nothing seems to have eventuated out of it. In terms of projects, here are some ideas: * A plotting library using Ben's newly released Gloss library (for people who can't or won't install Gtk2Hs to get Chart working; Alex Mason is interested in this) * Various graph-related project (graphviz, generic graph class, etc.; this assumes someone else apart from me cares about this stuff) * Hubris if Mark Wotton comes along * LLVM if David Terei comes So, at least as an initial listing, we'd need to have a listing of: 1) Who's interested 2) What dates are good 3) What projects people want to work on 4) Where we can host this Let's get the ball rolling! -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

9 11