- Haskell-Cafe - Haskell.org

Weaving fun
by Dominic Steinitz 11 Apr '07

11 Apr '07

I've been dying to do this all day but work and then family intervened. Dominic. import Data.List weave = unfoldr f where f ([],_,_) = Nothing f (x:xs,[],zs) = Just (x,([],[],[])) f (x:xs,ys,zs) = Just (x,(ys,zs,xs))

1 0

Skipping keywords with Parsec
by Joel Reymont 11 Apr '07

11 Apr '07

Is there a way to have any Parsec combinator skip a certain set of keywords? I tried lexeme = P.lexeme lexer . (skip >>) but I don't think lexeme is called for every keyword. Thanks, Joel -- http://wagerlabs.com/

1 1

Re: [Haskell-cafe] Why Perl is more learnable than Haskell
by David Tolpin 11 Apr '07

11 Apr '07

> > If you first language is LISP probably you find easy Haskell and difficult > pearl. Hi, my first programming language is lisp (that is, the language I am most fluent in -- recently Common Lisp, earlier Scheme) and I find Haskell a problematic programming language (this is a fresh experience -- I am writing a syndrome-networks based DSS in Haskell now) because it is not a language. Lisp is a language and Haskell is not, in the sense that lisp allows to write programs that can be read aloud and understood from reading the code. Haskell is a notation that is not a literature by itself, and for Haskell, literate programming, that is, writing more comments than code, is a must; while for lisp it is a rather exotic practice. David

1 0

GHC 6.6 hangs
by Gleb Alexeyev 11 Apr '07

11 Apr '07

Dmitry Antonyuk (lomeo) came up with a piece of code that hung GHC 6.6: newtype Foo a = Foo (Foo a -> a) bar x@(Foo f) = f x baz = bar (Foo bar) See the original discussion (in Russian) at: http://lomeo.livejournal.com/35674.html

2 2

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 11 Apr '07

11 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