May 2006 - Glasgow-haskell-users

Constructing a binary tree from a postorder visit
by Nuno Santos 24 May '06

24 May '06

Hi, I have this datatype: data PeAux a = Folha Char | Nodo Char (PeAux a) (PeAux a) deriving Show And i need to reconstruct a tree from its post order visit.... example "12H3V" |'m trying something like this to create the nodes and leave what lefts: converteAux [] (x,y) = (x,y) converteAux (a:t) (x,y) | ((length (a:t))<3) = converteAux [] (x,y ++ (a:t)) converteAux (a:b:t) (x,y) | ((length (a:b:t))<3) = converteAux [] (x,y ++ (a:b:t)) converteAux (a:b:c:t) (x,y) | (isNumber a) && (isNumber b) && (isLetter c) = converteAux t (x ++ [(Nodo c (Folha a) (Folha b))],y) | otherwise = converteAux (b:c:t) (x,y++[a]) and i'm trying this to rebuild the tree but i dont know what to do in the case of [] since i dont have a empty constructer preenche (x:xs) = Nodo 'H' (preenche xs) x Can anyone help me? Many thx, Nuno

1 0

Space leak due to pairs
by Shin-Cheng Mu 24 May '06

24 May '06

Hi, I am trying to fix a space leak which I suspected to be caused by an old problem involving lazy pattern matching for pairs. P. Wadler and J. Sparud each suggested fixes to the compiler to resolve the space leak. I was wondering whether they are implemented in GHC. In the GHC Users mailing list archive I found a message in 2004 from Simon Peyton Jones saying that GHC does have the fix, but its effects are fragile when mixed with other optimisations: http://www.haskell.org/pipermail/glasgow-haskell-users/2004-August/ 007023.html I am wondering what the situation is now, and whether there is a way to make the fix work for my code. * * * The problematic code looks like: idX (StartEvent a : strm) = let (ts, strm') = idX strm (us, strm'') = idX strm' in (StartEvent a : ts ++ EndEvent a : us, strm'') The program processes a stream of XML events, and in this case it simply returns the stream itself with a minimal amount of validation. The intention of the code was to thread "strm" through the recursive calls and free the items in strm as soon as they are processed. So the program should use constant space in the heap (and stack space proportional to the depth of the XML tree). However, with this definition I needed about 8Mb of heap for a 1Mb input file. The situation is the same even if I do not use -O or -O2. So it seems that the GC fix did not work for this case. Is there a way to make it work? If I do have to alter the code to avoid the space leak, what is the best way to do it? * * * Without the GC fix there are still ways to alter the code to plug the space leak. The result is quite ugly, therefore I'd wish that the compiler could do it for me. I will present the code below. They may serve as evidence that the space leak does come from the lazy pattern problem. Also, if there is a better way to code it, please let me know. Since I suspected that delayed evaluation of us and strm'' keeps the pointer to strm around for too long, the natural solution seems to be forcing their evaluation. So I tried: idX (StartEvent a : strm) = case idX strm of (ts, strm') -> case idX strm' of (us, strm'') -> (StartEvent a : ts ++ EndEvent a : us, strm'') which made things worse. The heap size increased a bit more and I get a typical "bell" shaped heap profile which seems to suggest that idX cannot output anything before processing the whole input. So I have to allow idX to output something while consuming the input. What eventually worked was this messy mixture of let and case: idX (StartEvent a : strm) = let (xs, rest) = case idX strm of (ts, strm') -> let (ws, rest) = case idX strm' of (us, strm'') -> (us, strm'') in (ts ++ EndEvent a : ws, rest) in (StartEvent a : xs, rest) The heap residency reduced from about 8MB to around 80Kb. This is rather tricky, however. The following "nicer looking" version has a heap profile as bad as the worse case. idX (StartEvent a : strm) = let (ts,us,strm'') = case idXsp strm of (ts, strm') -> case idXsp strm' of (us, strm'') -> (ts, us, strm'') in (StartEvent a [] : ts ++ EndEvent a : us, strm'') And I cannot quite explain why... * * * If you'd like to download the code to do some profiling, here it is: http://www.psdlab.org/~scm/hx.tar.gz It includes and uses HXML, a library by Joe to do the parsing. The main program is hxpc.hs. There is a 1 MB sized sample input file size1m.xml. There are two simple scripts "recompile" and "runhxpc" for compiling and running the program. sincerely, Shin-Cheng Mu

2 1

Re: [Haskell] GHC Hackathon
by Malcolm Wallace 23 May '06

23 May '06

> > I think many would be grateful if a podcast were made of this event > > such that those who missed it can still watch the presentations. > > +1. A podcast would be perfect, posting minutes would be next in line. If the Hackathon goes ahead, recording a video podcast of the event should be straightforward. (I've been playing with streaming web media lately, and can volunteer to do that side of things. The quality can be surprisingly good.) Mind you, even the compressed web streams will not be small - approx 150Mb per hour. A one day tutorial could easily stretch to over 1Gb. Regards, Malcolm

1 0

GHC 6.4.2 on OS X
by Peter Gammie 23 May '06

23 May '06

Hello, I am wondering if the following patch (or equivalent) made it into GHC 6.4.2. I was hoping it would fix my problem: > mjollnir ~/src/ghc/ghc-6.4.2$ ghci `hbdd-config --cudd-libs` > ___ ___ _ > / _ \ /\ /\/ __(_) > / /_\// /_/ / / | | GHC Interactive, version 6.4.2, for > Haskell 98. > / /_\\/ __ / /___| | http://www.haskell.org/ghc/ > \____/\/ /_/\____/|_| Type :? for help. > > Loading package base-1.0 ... linking ... done. > Loading package haskell98-1.0 ... linking ... done. > Loading package boolean-0.3.0 ... linking ... done. > Loading package unix-1.0 ... linking ... done. > Loading package cudd-0.3.0 ... linking ... ghc-6.4.2: > /Users/peteg/lib/hbdd-0.3.0/ghc-6.4.2/cudd//hutil.o: unknown symbol > `_fprintf$LDBLStub' > ghc-6.4.2: unable to load package `cudd-0.3.0' It is a problem with GCC 4.0 and GHCi - GHC works fine. > mjollnir ~/src/ghc/ghc-6.4.2$ gcc --version > powerpc-apple-darwin8-gcc-4.0.1 (GCC) 4.0.1 (Apple Computer, Inc. > build 5247) > Copyright (C) 2005 Free Software Foundation, Inc. > This is free software; see the source for copying conditions. > There is NO > warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR > PURPOSE. Can you give me some idea how to fix it? (The use of fprintf is inessential for my purposes but I'd prefer not to hack the C library too much.) cheers peter Begin forwarded message: > From: Wolfgang Thaller <wolfgang(a)haskell.org> > Date: 15 July 2005 12:00:16 PM > To: cvs-fptools(a)haskell.org, cvs-ghc(a)haskell.org > Subject: cvs commit: fptools configure.ac fptools/ghc/rts Linker.c > > wolfgang 2005/07/14 19:00:15 PDT > > Modified files: > . configure.ac > ghc/rts Linker.c > Log: > Mac OS X/PowerPC: Make GHCi deal with the additional statically > linked > symbols from libSystemStub.a on Tiger (printf$LDBLStub and friends). > > MERGE TO STABLE > > Revision Changes Path > 1.114 +15 -0 fptools/configure.ac > 1.201 +51 -0 fptools/ghc/rts/Linker.c > _______________________________________________ > Cvs-ghc mailing list > Cvs-ghc(a)haskell.org > http://www.haskell.org/mailman/listinfo/cvs-ghc

2 2

Help tracking down a bug
by J. Garrett Morris 19 May '06

19 May '06

Hello, For the past couple of weeks, since downloading 6.4.2, I've been running into occasion panics: ghc-6.4.2: panic! (the `impossible' happened, GHC version 6.4.2): tcIfaceTyVar a{tv} Consistently, changing certain files causes this error. Which files in particular cause it vary by machine - unfortunately, I don't have a very wide variety of machines to test it on. My concern is that this is occuring in about 5000 lines of proprietary code, and I'm not sure where to start in trying to create a repro case. Any guidance? Thanks. /g

1 0

Re: [Haskell-cafe] Re: Existentially-quantified constructors: Hugs is fine, GHC is not?
by Ross Paterson 19 May '06

19 May '06

On Thu, May 11, 2006 at 01:46:43PM +0100, Ben Rudiak-Gould wrote: > Otakar Smrz wrote: > > data ... = ... | forall b . FMap (b -> a) (Mapper s b) > > > > ... where FMap qf qc = stripFMap f q > > > >the GHC compiler as well as GHCi (6.4.2 and earlier) issue an error > > > > My brain just exploded. > > I can't handle pattern bindings for existentially-quantified > > constructors. > > The problem here is a tricky interaction between irrefutable pattern > matching and existential tuples. In Core, the FMap constructor has a third > field which stores the type b, and when you match against the pattern (FMap > qf qc) you're really matching against (FMap b qf qc). (stripFMap f q) might > evaluate to _|_, in which case, according to the rules for irrefutable > matching, all of the pattern variables have to be bound to _|_. But type > variables (like b) can't be bound to _|_. > > From an operational standpoint, the problem is that the (fully-evaluated) > value of b has to be available in the body of the let statement, which > means that (stripFMap f q) must be evaluated before the body, and the let > statement must diverge without reaching the body if (stripFMap f q) > diverges, since no value can be assigned to b in that case. But the > semantics of let clearly require that execution always proceed to the body > no matter what (stripFMap f q) evaluates to. > > So I'm not convinced that your program is well-typed, even though it looks > fine at first. I'm not sure what happens to Haskell's semantics when you > allow type variables to be bound to _|_. The fact that Hugs allows it may > be a bug. Why would a type variable be present at runtime, let alone bound to _|_? I believe the Hugs behaviour was intentional. It's particularly handy with single-constructor data types, e.g. representing objects. It does complicate the formal specification of pattern matching a bit, but I don't think it's unsound in any way.

2 1

Problems compiling
by Nuno Santos 18 May '06

18 May '06

Hi, I'm very lame in Haskell and compiling is very new to me. I have this problem when compilng a program that runs without error: MACKIE:/Volumes/DADOS/LESI/4 Ano/SSDI lpx$ ghc polish.hs compilation IS NOT required /usr/bin/ld: Undefined symbols: _ZCMain_main_closure ___stginit_ZCMain collect2: ld returned 1 exit status Do i need to add extra parameters to ghc? I need to know or thing... I need to obtain the arguments of a haskell program and then treat those arguments as a list inside the program example: polish [(1,(2,3)),(2,(3,4)),(3,(5,6))] And then i want to have that list inside the program. How can i do that? For now i have the following code: main :: IO () main = do args <- getArgs print args Well, i hope someone can answer me these questions. Many thx, Nuno Santos

3 4

RE: [Haskell] My brain just exploded
by Simon Peyton-Jones 17 May '06

17 May '06

[Redirecting to GHC users] Yes, GHC insists that you use 'case' when unpacking data constructor that bind existential type variables. http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions. html#existential-quantification (look at 7.4.1.4.3) It's not clear (to me) how to write the typing rule for pattern matching in lets when existentials are involved. Simon | -----Original Message----- | From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Dominic | Steinitz | Sent: 14 May 2006 09:03 | To: haskell(a)haskell.org | Subject: [Haskell] My brain just exploded | | What a great error message: | | qcgadt.hs:115:7: | My brain just exploded. | I can't handle pattern bindings for existentially-quantified constructors. | In the binding group | (Rep x) = uncompressRep s | In the definition of `uncompressRep': | uncompressRep (0 : 1 : 0 : s) = let (Rep x) = uncompressRep s in Rep | (RList x) | Failed, modules loaded: none. | | Here's the offending line: | | uncompressRep (0:1:1:s) = | let (Rep x) = uncompressRep s in | Rep (RList x) | | But this works: | | uncompressRep (0:1:0:s) = | let x = uncompressRep s in | case x of | (Rep y) -> Rep (RList y) | | Can someone explain this? | | Thanks, Dominic. | | | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell

1 0

ghc api / calling functions?
by Maarten 16 May '06

16 May '06

Dear all, Is there a way to use the ghc api to call functions directly instead of evaluating statements (more or less similar to hs-plugins)? So far, thanks to some info pages, I have been able to load sessions and make modules, however there seems to be little or no documentation on calling functions directly. Any info/pointers appreciated. Thanks. Kind regards, Maarten

2 4

HEAD: Problem Linking genapply in 6.5.20060510
by Reilly Hayes 15 May '06

15 May '06

I'm continuing in my quest to produce a clean build of GHC for Mac intel. I'm using registerised .hc files built on 386 linux. I suspect today's problem is pretty easy to figure out for a GHC expert, but I'm not. When I try to build utils/genapply, the link fails because the symbols _GHCziList_lvl22_closure and _GHCziList_zdwlen_info are undefined. I'll include the build log below. While we're on the topic, can somebody explain the algorithm used to generate these symbol names? The build log was: gcc -x c GenApply.hc -o GenApply.raw_s -S -O -fno-builtin -fno-defer- pop -fomit-frame-pointer -mdynamic-no-pic - DDONT_WANT_WIN32_DLL_SUPPORT -mdynamic-no-pic - D__GLASGOW_HASKELL__=605 -O -I/Users/rfh/ghc-6.5/mac/ ghc-6.5.20060510/includes -I/Users/rfh/ghc-6.5/mac/ghc-6.5.20060510/ libraries/base/include -I/Users/rfh/ghc-6.5/mac/ghc-6.5.20060510/ libraries/unix/include -I/Users/rfh/ghc-6.5/mac/ghc-6.5.20060510/ libraries/parsec/include -I/Users/rfh/ghc-6.5/mac/ghc-6.5.20060510/ libraries/readline/include -I. `echo | sed 's/^$/- DSTOLEN_X86_REGS=4/'` ../../driver/mangler/ghc-asm GenApply.raw_s GenApply.s as -o GenApply.o GenApply.s gcc -o genapply -fno-builtin -fno-defer-pop -fomit-frame-pointer - mdynamic-no-pic -DDONT_WANT_WIN32_DLL_SUPPORT -mdynamic-no-pic - D__GLASGOW_HASKELL__=605 -O -I/Users/rfh/ghc-6.5/mac/ ghc-6.5.20060510/includes -I/Users/rfh/ghc-6.5/mac/ghc-6.5.20060510/ libraries/base/include -I/Users/rfh/ghc-6.5/mac/ghc-6.5.20060510/ libraries/unix/include -I/Users/rfh/ghc-6.5/mac/ghc-6.5.20060510/ libraries/parsec/include -I/Users/rfh/ghc-6.5/mac/ghc-6.5.20060510/ libraries/readline/include -L/Users/rfh/ghc-6.5/mac/ ghc-6.5.20060510/rts -L/Users/rfh/ghc-6.5/mac/ghc-6.5.20060510/rts/ gmp -L/Users/rfh/ghc-6.5/mac/ghc-6.5.20060510/libraries/base -L/Users/ rfh/ghc-6.5/mac/ghc-6.5.20060510/libraries/base/cbits -L/Users/rfh/ ghc-6.5/mac/ghc-6.5.20060510/libraries/haskell98 -L/Users/rfh/ghc-6.5/ mac/ghc-6.5.20060510/libraries/parsec -L/Users/rfh/ghc-6.5/mac/ ghc-6.5.20060510/libraries/Cabal -L/Users/rfh/ghc-6.5/mac/ ghc-6.5.20060510/libraries/template-haskell -L/Users/rfh/ghc-6.5/mac/ ghc-6.5.20060510/libraries/readline -L/Users/rfh/ghc-6.5/mac/ ghc-6.5.20060510/libraries/unix -L/Users/rfh/ghc-6.5/mac/ ghc-6.5.20060510/libraries/unix/cbits -u "_GHCziBase_Izh_static_info" -u "_GHCziBase_Czh_static_info" -u "_GHCziFloat_Fzh_static_info" -u "_GHCziFloat_Dzh_static_info" -u "_GHCziPtr_Ptr_static_info" -u "_GHCziWord_Wzh_static_info" -u "_GHCziInt_I8zh_static_info" -u "_GHCziInt_I16zh_static_info" -u "_GHCziInt_I32zh_static_info" -u "_GHCziInt_I64zh_static_info" -u "_GHCziWord_W8zh_static_info" -u "_GHCziWord_W16zh_static_info" -u "_GHCziWord_W32zh_static_info" -u "_GHCziWord_W64zh_static_info" -u "_GHCziStable_StablePtr_static_info" -u "_GHCziBase_Izh_con_info" -u "_GHCziBase_Czh_con_info" -u "_GHCziFloat_Fzh_con_info" -u "_GHCziFloat_Dzh_con_info" -u "_GHCziPtr_Ptr_con_info" -u "_GHCziStable_StablePtr_con_info" -u "_GHCziBase_False_closure" -u "_GHCziBase_True_closure" -u "_GHCziPack_unpackCString_closure" -u "_GHCziIOBase_stackOverflow_closure" -u "_GHCziIOBase_heapOverflow_closure" -u "_GHCziIOBase_NonTermination_closure" -u "_GHCziIOBase_BlockedOnDeadMVar_closure" -u "_GHCziIOBase_Deadlock_closure" -u "_GHCziWeak_runFinalizzerBatch_closure" -u "___stginit_Prelude" GenApply.o -lHSreadline -lHStemplate-haskell -lHSunix - lHSunix_cbits -lHSCabal -lHShaskell98 -lHSbase -lHSbase_cbits - lHSparsec -lHSrts -lgmp -lm -lreadline -lncurses -ldl /usr/bin/ld: Undefined symbols: _GHCziList_lvl22_closure _GHCziList_zdwlen_info collect2: ld returned 1 exit status make[1]: *** [genapply] Error 1 Reilly Hayes

4 4