September 2009 - Haskell-Cafe

better error message for "undefined"
by Andrew U. Frank 10 Sep '09

10 Sep '09

the haskell prelude introduces the type undefined and contains a remark to the effect that compilers are expected to intrudocue a meaningful error message. GHC just prints 'Prelude undefined' which is not very informativ. is there a way to have different kinds of undefined? such that i get a message which one was hit. something like writing in the code 'unefined 'my error 123' which prints 'undefined - my error 123' when it is accidentally hit. i searched the web, but found nothing. any suggestions? thanks a lot! andrew

3 2

Bounded parMap
by Anakim Border 10 Sep '09

10 Sep '09

Hi, lately I've been working on a parallel parser whose core is something like this: pMap parse blocks where pMap is a map-like function sparking independent computations over the elements of the "blocks" list. The actual implementation used Control.Parallel.Strategies: map parse blocks `using` parListChunk n rnf In a recent post [1], however, Edward Kmett noted that such code is cache oblivious because the "blocks" list is traversed independently by the map and by the sparks. It may therefore happen that the first spark starts to be evaluated when the map is already at the end of the list. Moreover, all the sparks are generated almost instantaneously even if only a few of them can be evaluated concurrently (I'm assuming here that the length of the list is bigger than the number of available native threads, but that seems reasonable). To solve this issue I imagined an alternative "par" primitive sparking a new computation in parallel when a native thread is free to perform its evaluation and otherwise blocking. It turns out it is possible to implement something like this in a library; have a look at the BoundedParMap module here: http://github.com/akborder/HsMakefileParser/ The code uses unsafe operations, so I'm not sure it can be completely trusted. Given however that the "boundedParMap" function combines deterministically the results of multiple applications of a pure function, it should remain referentially transparent. To measure performances I made two versions of my parser (Makefile.hs), one keeping Control.Parallel.Strategies as before and the other using BoundedParMap. I built them (ghc -O2 -threaded; ghc 6.11.20090907) and run them on a quad-core system (+RTS -N4) over a list generating 48 sparks. Running each implementation 10 times I got the following run times: Control.Parallel.Strategies: 1.328 +- 0.1 BoundedParMap: 1.095 +- 0.12 BoundedParMap seems to be faster, especially considering that the total number of sparks (48) is quite small. Do you think that the difference is actually due to better caching (both in the list traversing and because the runtime system deals with less sparks at any time) or to something else I'm missing? -- AB [1] http://www.haskell.org/pipermail/haskell-cafe/2009-September/066158.html

1 0

Re: Would you mind explain such a code ?
by oleg＠okmij.org 10 Sep '09

10 Sep '09

> I know myFoldl implements foldl using foldr. However i really donot know how > it can do it ? You will probably like Graham Hutton A Tutorial on the Universality and Expressiveness of Fold JFP, 1999. http://www.cs.nott.ac.uk/~gmh/fold.pdf Section 5.1 (actually, suml in Section 5) of the paper explains how the expression of foldl in terms of foldr can be _calculated_. The result is correct by construction.

1 0

Parallel parsing & multicore
by Anakim Border 10 Sep '09

10 Sep '09

Hi, I've put together a parser that works like this: - the full input is read into a strict ByteString; - such string is split into a number of lines; - each line is fed (independently) to a parser based on Parsec (version 3). Running the serial version of the parser (compiled with -O2 optimizations) on a rather large file, I get the following: $ ./Parser +RTS -s 2,175,464,100 bytes allocated in the heap 49,293,632 bytes copied during GC 5,297,560 bytes maximum residency (6 sample(s)) 1,406,800 bytes maximum slop 16 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 4140 collections, 0 parallel, 0.39s, 0.42s elapsed Generation 1: 6 collections, 0 parallel, 0.05s, 0.07s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 1.93s ( 1.99s elapsed) GC time 0.44s ( 0.48s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 2.37s ( 2.47s elapsed) %GC time 18.7% (19.5% elapsed) Alloc rate 1,127,336,508 bytes per MUT second Productivity 81.2% of total user, 78.1% of total elapsed The profile report: COST CENTRE MODULE %time %alloc >>=_a6OH Text.Parsec.Prim 20.6 13.0 tokenPrimEx Text.Parsec.Prim 16.5 20.8 fmap_a6Qj Text.Parsec.Prim 15.5 3.6 parserBind Text.Parsec.Prim 12.4 9.3 mplus_a6KS Text.Parsec.Prim 10.3 10.6 notFollowedBy Text.Parsec.Combinator 3.1 4.4 [...] shows that the biggest part of the execution time is spent in the parser (not in the read & line split operations, as expected). Given that each line is parsed independently, I used the following code: map parse lines `using` parListChunk 250 rnf to spark a separate computation for each group of 250 lines. I made the datatype used by the parser an instance of NFData, so that the "rnf" strategy should force a complete evaluation. The threaded version running on 2 cores is moderately faster than the serial one: $ ./Parser +RTS -s -N2 2,377,165,256 bytes allocated in the heap 36,320,944 bytes copied during GC 6,020,720 bytes maximum residency (6 sample(s)) 6,933,928 bytes maximum slop 21 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 2410 collections, 0 parallel, 0.33s, 0.34s elapsed Generation 1: 6 collections, 4 parallel, 0.06s, 0.05s elapsed Parallel GC work balance: 1.83 (2314641 / 1265968, ideal 2) Task 0 (worker) : MUT time: 2.43s ( 1.19s elapsed) GC time: 0.02s ( 0.02s elapsed) Task 1 (worker) : MUT time: 2.15s ( 1.19s elapsed) GC time: 0.29s ( 0.30s elapsed) Task 2 (worker) : MUT time: 2.37s ( 1.19s elapsed) GC time: 0.07s ( 0.08s elapsed) Task 3 (worker) : MUT time: 2.45s ( 1.19s elapsed) GC time: 0.00s ( 0.00s elapsed) INIT time 0.00s ( 0.00s elapsed) MUT time 2.06s ( 1.19s elapsed) GC time 0.39s ( 0.39s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 2.45s ( 1.58s elapsed) %GC time 15.7% (24.9% elapsed) Alloc rate 1,151,990,234 bytes per MUT second Productivity 84.2% of total user, 130.2% of total elapsed The speedup is smaller than what I was expecting given that each unit of work (250 input lines) is completely independent from the others. Changing the size of each work unit did not help; garbage collection times are small enough that increasing the minimum heap size did not produce any speedup either. Is there anything else I can do to understand why the parallel map does not provide a significant speedup? Thanks, AB

4 10

Fixed length list type?
by Job Vranish 10 Sep '09

10 Sep '09

Does anyone know of a hackage package that has fixed length list type that is an instance of Applicative, Foldable and Traversable? (a list type that somehow encodes its length in the type) I've found lots of fixed length list types, but non that are members of the common typeclasses. I've implement one here: http://github.com/jvranish/FixedList/blob/6c861a12ba5d17481fd22cdb1f90404ab… But am I just duplicating work that is already out there? Thanks, - Job

1 0

Darcs 2.3 and NFS
by Lewis-Sandy, Darrell 09 Sep '09

09 Sep '09

I am trying to set up darcs so that I can share patches between the many machines that I use for application development and testing. The machines have various operating systems (Windows XP, Windows 2000, Windows Vista, Ubuntu 9.04 32-bit, Ubuntu 64 bit, etc). I have a windows file share that is accessible to all the machines, and has been permanently mounted as a CIFS share on the Linux machines. I would like to use that drive for a centralized repository. Since all machines have access to that share I assumed that I could use darcs without setting up either http or ssh access. I have built darcs 2.3 on the Ubuntu 9.04 (Jaunty) 32 bit box and am able to execute darcs commands against any local folders, but am consistently getting an error message when I try to push or put to the NFS: darcs: ./_darcs/tentative_pristine-0:rename: already exists (File exists) Likewise when I navigate to the mounted share folder and attempt a get or pull. Has anyone else encountered this problem?

2 1

problems with HOC install from svn
by John Velman 09 Sep '09

09 Sep '09

I'm unable to build HOC from the svn read-only checkout. Here are some details of what I'm doing. I'm running OS X 10.5.8 on an intel iMac with Xcode is 3.1.3. Haskel and Cabal are from the Haskel platform, haskell-platform-2009.2.0.2-i386.dmg I got Parsec 3.0 from Hackage. I checked out HOC using the svn command at http://code.google.com/p/hoc/source/checkout and checked out revision 411. Configure goes OK except for the complaint: ---- Setup.hs:1:0: Warning: In the use of `defaultUserHooks' (imported from Distribution.Simple): Deprecated: "Use simpleUserHooks or autoconfUserHooks, unless you need Cabal-1.2 compatibility in which case you must stick with defaultUserHooks" ---- But when I try to build, I get, after a bunch of apparently successful things: ----------- Loading package binary-0.5.0.1 ... <command line>: can't load .so/.DLL for: HSbinary-0.5.0.1 (dlopen(libHSbinary-0.5.0.1.dylib, 9): image not found) ----------- I certainly can't find libHSbinary... of any version on my computer, dylib or not. Tried looking in the /Library/Frameworks/GHC.Framework stuff, also did a find . -iname "*libHS* and found libHSGLFW..., libHSparsec-3.0.0. (also tried this in my home directory). What is this, and how do I get it? Best, John Velman

2 4

ANNOUNCE: CCA-0.1
by Paul L 09 Sep '09

09 Sep '09

I'm pleased to annouce that a library for Causal Commutative Arrows (CCA) has been uploaded to Hackage DB. It implements CCA normalization using Template Haskell and a modified arrow pre-processor (based on arrowp) to generate outout that Template Haskell can parse. It's highly experimental since we are still fiddling with several design choices, and by no means we imply Template Haskell is the best choice to implement CCA. Any suggestion or comment is welcome! -- Regards, Paul Liu Yale Haskell Group http://www.haskell.org/yale

3 2

Deconstructing types
by Louis Wasserman 09 Sep '09

09 Sep '09

Yo, I don't know a thing about SYB, Data.Data, or Data.Typeable, mostly because I'm an efficiency fanatic. Nevertheless, I'd like to know whether or not there's a way to deconstruct a (mostly) arbitrary type, into tuples, unions, etc. using this framework. Any thoughts? Louis Wasserman wasserman.louis(a)gmail.com

3 8

Strange type error (tfp package + GADTs)
by Emil Axelsson 09 Sep '09

09 Sep '09

Hi Café, Can anyone explain why `add1` is rejected in the code below (which uses the tfp package): import Types.Data.Num data A n where A :: NaturalT n => Int -> A n getA :: A n -> Int getA (A n) = n add1 :: NaturalT (m:+:n) => A m -> A n -> A (m:+:n) add1 (A a) (A b) = A (a+b) add2 :: NaturalT (m:+:n) => A m -> A n -> A (m:+:n) add2 a b = A (getA a + getA b) add3 :: NaturalT (m:+:n) => A m -> A n -> A (m:+:n) add3 (A a) _ = A a `add2` and `add3` are accepted. As far as I can see, `add2` is equivalent to `add1` except that it delegates the pattern matching to the function `getA`. If I only pattern match on one of the arguments, as in `add3`, things are also fine. Thanks! / Emil

1 1