April 2007 - Haskell-Cafe

A convenient way to deal with conditional function composition?
by Maxime Henrion 11 Apr '07

11 Apr '07

Hello all, I have found myself writing instances of Show for some types of mine, and I did so by defining the showsPrec function, for performance reasons. I ended up with code that I find quite inelegant. Here's an example: data Move = Move { movePiece :: PieceType, moveFile :: Maybe File, moveTarget :: Square, moveIsCapture :: Bool --movePromotion :: Maybe PieceType } deriving (Eq) instance Show Move where showsPrec _ Move { movePiece = p, moveFile = f, moveTarget = s, moveIsCapture = c } = (if p /= Pawn then shows p else id) . (maybe id shows f) . (if c then ('x':) else id) . shows s I considered writing a conditional composiion combinator to avoid all the 'if foo then f else id' code. Something looking like this: f .? True g = f . g f .? False g = f I'm not sure this is the best approach though, and I would be happy to hear about your suggestions for improving the style of this code, or any other comment that you think is appropriate. Thanks, Maxime

4 5

Profiling makes memory leak go away? Is Haskell a practical language?
by Oren Ben-Kiki 11 Apr '07

11 Apr '07

On Tue, 2007-04-10 at 12:14 +0200, apfelmus wrote: > Oren Ben-Kiki wrote: > > The code is in http://hpaste.org/1314#a1 if anyone at all is willing > > to take pity on me and explain what I'm doing wrong. > > There is an important point to note about streaming, namely that it > conflicts with knowing whether the input is syntactically correct or > not. True, this is the core issue. Think of a turing machine processing an infinite tape. It is writing output and producing a final result; it is possible to examine the output tape before knowing the final result. Haskell parsers insist on having the "output tape" live in memory until the final result is known, and then give it to you as one huge object when done (or discard it and just give you the error message). NOT a good idea if your input tape is a 200 MB file! > You've probably noticed this already and introduced rToken for that > reason but I'm not sure. The idea is that the parser generates a stream of tokens. If/when it hits an error, you get an error token at the end and parsing stops. > > Chasing down my memory leak I got into a weird situation where adding > > a magic manual SCC section and compiling with -prof makes the leak > > disappear. > > That sounds fishy. Note that manual SCC annotations + optimization > currently is a bit buggy in GHC, in the sense that optimization disturbs > correct cost attribution. Er... I just added '-prof'. No '-O' flag at all so no optimizations, right? > Does the program eat the output of yes 'a' without memory explosion > showed by "top"? If so, it could perhaps be a problem of the > optimization phase which maybe expands > > D.append parsed (case result of ...) > > to > > case result of { > Nothing -> D.append parsed D.empty > Just .. -> D.append parsed (D.singleton...) } > > The latter won't stream because of the reason noted above. Ah, but it *does* stream! This is the beauty of lazy evaluation. The "free" code is basically: reply = parse ... -- Lazily evaluated tokens = rTokens reply -- Has some values "immediately" list = D.toList tokens -- Has some values "immediately" mapM_ list print -- Start printing "immediately"! Where what "parse" does is: reply = Reply { rTokens = D.append concreteToken lazyTokens, -- "Immediate" rResult = lazyResult -- Only available at end of parsing } So every time the parser calls "D.append" into the tokens, the printing "D.toList" is able to extract, print and GC the token immediately. And this works perfectly, with constant memory consumption. The problem occurs when I peek at the final "rResult" field. The "leak" code says: reply = parse ... -- Lazily evaluated result = rResult reply -- Lazy; has value when parsing is done extra = case result ... -- Lazy; has value when parsing is done parsed = rTokens reply -- Has some values "immediately" tokens = D.append parsed extra -- Has some values "immediately" list = D.toList tokens -- Has some values "immediately" mapM_ list print -- Starts printing "immediately"! This *still* starts printing tokens immediately. However, while in the previous case the GC is smart enough to keep the program in constant memory size, in the second case it for some reasons starts missing more and more PAP objects so memory usage goes through the roof. > But it's > highly unlikely that GHC performs a transformation that changes > semantics this radically. You'd think... but the fact of the matter is that while the first version works fine, the second doesn't, UNLESS I add the magic SCC section: extra = {-# SCC "magic" #-} case result ... And compile with '-prof' (no '-O' flags). Then it somehow, finally, "get the idea" and the program runs perfectly well with constant memory consumption. Which, as you aptly put it, is very "fishy" indeed... > > I can achieve the results I want in very short elegant code... > > In my opinion, your streaming parser is not as elegant as it could be > which makes it hard to read the code. Well... one point is the above basically establishes two "threads", one printing tokens and one producing them. communicating through a sort of message queue (rTokens). I think that's pretty elegant compared to the hoops you need to jump through to do this in any other language :-) Another point is that this is a dumbed-down toy example. In the real program the parser does much more which justifies the awkwardness you point out. Specifically there are nifty ways to handle decision points (parsing isn't much good unless there are alternatives to be tested at each point :-). > With monad transformers, we almost > have > > Parser a ~= StateT State (WriterT (D.DList Token) Maybe) a > ~= State -> (D.DList Token, Maybe (a,State)) Monad transformers are a bit beyond my grasp at this point, but from the little I know about them I don't see how they would help me with the GC/memory problem. They definitely might make the code even more elegant... > Also, I'm really missing type signatures, especially for many. When > reading the code, I expected > > many :: Parser a -> Parser [a] > > but had to conclude > > many :: Parser a -> Parser () > > by inspecting its code. Sorry about that. Yes, all the "syntax" functions have this signature. I added these as www.hpaste.org/1314#a2. Is it possible I have hit on a bug in GHC's implementation, and adding '-prof' somehow caused it to work around it? Thanks, Oren Ben-Kiki

4 3

What I learned from my first serious attempt low-level Haskell programming
by Stefan O'Rear 11 Apr '07

11 Apr '07

As a learning excersize, I re-wrote and re-optimized Data.Binary.Builder yesterday. 1. Intuition is NOT your friend. Most obvious pessimizations I made were actually wins, and vice versa. 2. Parameters are very expensive. Our type of functions that build (ignoring CPS for the time being) was MBA# -> Int# -> [ByteString], where the Int# is the current write pointer. Adding an extra Int# to cache the size of the array (rather than calling sMBA# each time) slowed the code down ~2x. Conversely, moving the write pointer into the byte array (storing it in bytes 0#, 1#, 2#, and 3#) sped the code by 4x. 3. MBA# is just as fast as Addr#, and garbage collected to boot. 4. You can't keep track of which version of the code is which, what is a regression, and what is an enhancement. Don't even try. Next time I try something like this I will make as much use of darcs as possible. 5. State# threads clog the optimizer quite effectively. Replacing st(n-1)# with realWorld# everywhere I could count on data dependencies to do the same job doubled performance. 6. The inliner is a bit too greedy. Removing the slow-path code from singleton doesn't help because popSingleton is only used once; but if I explicitly {-# NOINLINE popSingleton #-}, the code for singleton itself becomes much smaller, and inlinable (15% perf gain). Plus the new singleton doesn't allocate memory, so I can use even MORE realWorld#s. And probably a few more I forgot about because of #4. The code is online at http://members.cox.net/stefanor/hackedbuilder if anyone cares (but see #4). Some parting numbers: (Builder7 is my current version, Builder1 is the unmodified rossp/kolmodin builder) stefan@stefans:~/hackedbuilder$ ghc -v0 --make -O2 -fforce-recomp -DBUILDER=Builder7 Bench.hs ; time ./Bench 2 10000000 330000000 real 0m5.580s user 0m5.540s sys 0m0.032s stefan@stefans:~/hackedbuilder$ ghc -v0 --make -O2 -fforce-recomp -DBUILDER=Builder7 -DUNROLL Bench.hs ; time ./Bench 2 10000000 330000000 real 0m2.948s user 0m2.908s sys 0m0.036s stefan@stefans:~/hackedbuilder$ ghc -v0 --make -O2 -fforce-recomp -DBUILDER=Builder1 Bench.hs ; time ./Bench 2 10000000 330000000 real 0m55.708s user 0m54.695s sys 0m0.208s stefan@stefans:~/hackedbuilder$ ghc -v0 --make -O2 -fforce-recomp -DBUILDER=Builder1 -DUNROLL Bench.hs ; time ./Bench 2 10000000 330000000 real 0m25.888s user 0m25.546s sys 0m0.156s stefan@stefans:~/hackedbuilder$ gcc -O2 -march=pentium4 CBuilder.c -o CBuilder ; time ./CBuilder 10000000 real 0m0.861s user 0m0.860s sys 0m0.000s Stefam

7 12

Compiling GHC
by Chris Witte 11 Apr '07

11 Apr '07

I'm tying to compile GHC under mingw (winxp with mingw no cygwin), everything appears to go OK but when I run make install it fails to copy some files cp -rp ./../include/* /usr/local/include/mingw cp: cannot stat `./../include/*': No such file or directory make: [install] Error 1 (ignored) cp -rp ./../lib/gcc-lib/mingw32/3.4.2/* /usr/local/gcc-lib cp: cannot stat `./../lib/gcc-lib/mingw32/3.4.2/*': No such file or directory make: [install] Error 1 (ignored) cp -rp ./../lib/gcc/mingw32/3.4.2/* /usr/local/gcc-lib cp: cannot stat `./../lib/gcc/mingw32/3.4.2/*': No such file or directory make: [install] Error 1 (ignored) cp -rp ./../libexec/gcc/mingw32/3.4.2/* /usr/local/gcc-lib cp: cannot stat `./../libexec/gcc/mingw32/3.4.2/*': No such file or directory make: [install] Error 1 (ignored) cp ./../lib/*.* /usr/local/gcc-lib cp: cannot stat `./../lib/*.*': No such file or directory make: [install] Error 1 (ignored) cp ./gcc.exe /usr/local cp: cannot stat `./gcc.exe': No such file or directory make: [install] Error 1 (ignored) cp ./as.exe /usr/local/gcc-lib cp: cannot stat `./as.exe': No such file or directory make: [install] Error 1 (ignored) cp ./ld.exe /usr/local/gcc-lib cp: cannot stat `./ld.exe': No such file or directory make: [install] Error 1 (ignored) cp ./dllwrap.exe /usr/local/gcc-lib cp: cannot stat `./dllwrap.exe': No such file or directory make: [install] Error 1 (ignored) cp ./dlltool.exe /usr/local/gcc-lib cp: cannot stat `./dlltool.exe': No such file or directory make: [install] Error 1 (ignored) cp /c/ghc/ghc-6.6/bin/../perl.exe /usr/local cp /c/ghc/ghc-6.6/bin/../perl56.dll /usr/local for i in ANNOUNCE LICENSE README; do \ /bin/install -c -m 644 $i /usr/local; \ done and then when I try and run, say, GHCi I get $ ghcii.sh ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.7.20070323, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base ... linking ... ghc.exe: unable to load package `base' ghc.exe: C:/msys/1.0/local/HSbase.o: unknown symbol `_gettimeofday' any ideas on what could be causing this. Cheers Chris Witte

5 5

Type error
by Alfonso Acosta 11 Apr '07

11 Apr '07

Hi all, I have a type problem in my code which I dont know how to solve (and I'm not really sure why is caused). I have made a simplified example, can anyone have a look at it? Thanks in advance, The error is: Example.hs:24:47: Ambiguous type variable `a' in the constraint: `HDPrimType a' arising from use of `supplySig' at Example.hs:24:47-55 Probable fix: add a type signature that fixes these type variable(s) Here is the code --- module Example where data HDSignal a = HDSignal class HDPrimType a where class PortIndex a where class SourcePort s where -- Plug an external signal to the port plugSig :: (HDPrimType a, PortIndex ix) => ix -> s -> (HDSignal a -> b) -> b class DestPort d where -- Supply a signal to the port supplySig :: (PortIndex ix, HDPrimType a) => HDSignal a -> ix -> d -> d -- Connect providing indexes connectIx :: (SourcePort s, PortIndex six, DestPort d, PortIndex dix) => six -> s -> dix -> d -> d -- This can seem ugly, -- it would be easier for us having different types for plugSig and supplySig -- but the final user would find it much more difficult to deal with -- supplysig connectIx six s dix d = plugSig six s $ (push2 supplySig) dix d push2 :: (a -> b -> c -> d) -> b -> c -> a -> d push2 f = (\b c a -> f a b c)

4 6

Re: [Haskell-cafe] Weaving fun
by Dave Feustel 10 Apr '07

10 Apr '07

Talk about synchronicity! I was just wondering whether 'weaving' of infinite lists is possible. eg weave the infinite lists [2,4..], [3,6..], [5,10..] to get [2,3,4,5,6,8,9,10,..] Is this kind of lazy evaluation possible? Thanks, Dave Feustel -----Original Message----- >From: Bas van Dijk <v.dijk.bas(a)gmail.com> >Sent: Apr 10, 2007 6:13 PM >To: haskell-cafe(a)haskell.org >Subject: [Haskell-cafe] Weaving fun > >Hello, > >For my own exercise I'm writing a function 'weave' that "weaves" a >list of lists together. For example: > > weave [[1,1,1], [2,2,2], [3,3]] ==> [1,2,3,1,2,3,1,2] > weave [[1,1,1], [2,2], [3,3,3]] ==> [1,2,3,1,2,3,1] > >Note that 'weave' stops when a list is empty. Right now I have: > > weave :: [[a]] -> [a] > weave ll = work ll [] [] > where > work ll = foldr f (\rst acc -> work (reverse rst) [] acc) ll > f [] g = \_ acc -> reverse acc > f (x:xs) g = \rst acc -> g (xs:rst) (x:acc) > >However I find this definition hard to read and I'm questioning its >efficiency especially due to the 'reverse' parts (how do they impact >performance and can they be removed?) > >So I'm wondering if 'weave' can be defined more "elegantly" (better >readable, shorter, more efficient, etc.)? > >happy hacking, > >Bas van Dijk >_______________________________________________ >Haskell-Cafe mailing list >Haskell-Cafe(a)haskell.org >http://www.haskell.org/mailman/listinfo/haskell-cafe http://RepublicBroadcasting.org - Because You CAN Handle The Truth! http://iceagenow.com - Because Global Warming Is A Scam!

3 2

Prettyprinting infix expressions with HughesPJ
by Alfonso Acosta 10 Apr '07

10 Apr '07

Hi all, I have to prettyprint infix expressions writing the least possible parenthesis (taking in account precedence and associativity). A simplified expression type could be: data Expr = Val String | -- Binary operators (using infix constructors) Expr :+: Expr | Expr :-: Expr | Expr :*: Expr | Expr :/: Expr | Expr :^: Expr | -- Unary operators Negate Expr I'm using HughesPJ for the rest of my AST (not just expressions) but the library doesn't provide any mechanism to help coding this kind of prettyprinter so I decided to simply use the standard showsPrec and then feed HughesPJ with the obtained text . showsPrec helps to take advantage of the precedence information. However, I don't find a way to remove parenthesis according to associativity. I'm sure this kind of prettyprinting has been already done zillions of times in Haskell. Any suggestions? Thanks in advance, Alfonso Acosta

2 3

Type checking and locating token with Parsec
by Joel Reymont 10 Apr '07

10 Apr '07

Folks, Imagine a language where Num + Num yields a Num and Str + Num yields a Str but Num + Str should not be allowed. I implemented parsing for such a language in OCaml with a yacc-based parser without an additional type-checking pass, entirely within the yacc grammar. I tried to take such an approach with Parsec but hit the roadblock with buildExpressionParser since it returns the same type as the token parser given to it. Rather than have numerical expressions, string expressions, etc., as separate types, I simplified things down to a single expression type that holds my booleans, strings and numbers. I now need to implement type checking of my parsed AST. The main issue is error reporting. I'm not sure where to get token location with Parsec and how to elegantly embed it in my AST. Has anyone implemented type checking on top of a Parsec-based parser? How did you locate your tokens? Thanks, Joel -- http://wagerlabs.com/

2 1

Re: [Haskell-cafe] Weaving fun
by Dave Feustel 10 Apr '07

10 Apr '07

I ask this question because I want to program a recently published algorithm for directly enumerating all prime numbers. The algorithm description uses infinite sets. The algorithm could possibly be programmed using lazy evaluation. -----Original Message----- >From: Ricardo Herrmann <rherrmann(a)gmail.com> >Sent: Apr 10, 2007 7:24 PM >To: Haskell-Cafe(a)haskell.org >Subject: Re: [Haskell-cafe] Weaving fun > >This reminded me of "interleaving" as in: > >Backtracking, Interleaving, and Terminating Monad Transformers >http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf > >On 4/10/07, Dave Feustel <dfeustel(a)mindspring.com> wrote: >> >> Talk about synchronicity! I was just wondering whether 'weaving' of >> infinite lists is possible. >> >> eg weave the infinite lists [2,4..], [3,6..], [5,10..] >> to get [2,3,4,5,6,8,9,10,..] >> >> Is this kind of lazy evaluation possible? >> >> Thanks, >> Dave Feustel http://RepublicBroadcasting.org - Because You CAN Handle The Truth! http://iceagenow.com - Because Global Warming Is A Scam!

1 0

operating on a hundred files at once
by Jefferson Heard 10 Apr '07

10 Apr '07

I have a series of NxM numeric tables I'm doing a quick mean/variance/t-test etcetera on. The cell t1 [i,j] corresponds exactly to the cells t2..N [i,j], and so it's perfectly possible to read one item at a time from each of the 100 files and compute the mean/variance etcetera on all cells that way. So what I propose to do is something along the lines of: openAndProcess filename = f <- readFile filename return (map (L.split ',') . lines $ f) main = do fs <- getArgs let items = map (map read) . map openAndProcess fs in do print . map (map $ mean) items print . map (map $ variance) items How close am I to doing the right thing here? As I understand it, this will result in one hundred IO [String] instances being returned by the call to (map openAndProcess $ filenames). Do I need to do something special to lift (read), (mean), and (variance), or even (map) into the IO monad so they can process the input as needed? Thanks in advance, -- Jeff

5 8