February 2005 - Haskell-Cafe

transformation of point-free expressions
by Daniel Fischer 16 Feb '05

16 Feb '05

G'day ye all, is there an *elegant* way to transform ( (.) (flip (.) (flip ($)))) . flip (.) . flip (.) to the more compact form flip (.) . flip ? And more general, is there an algorithm to simplify such expressions (other than take a piece of paper, apply it to the appropriate number of arguments and see what you get)? Thanks in advance, Daniel

1 0

Problems building GreenCard
by Dmitri Pissarenko 15 Feb '05

15 Feb '05

Hello! I'm trying to build GreenCard 3.01 (latest release according to http://www.haskell.org/greencard/) under Windows with cygwin and GHC 6.2.1. I'm getting these errors: <errors> $ make prefix=/cygdrive/c/Programme/GreenCard/ install install-pkg make[1]: Entering directory `/cygdrive/c/dapWork/temp/downloads/greencard- 3.01/g reencard-3.01/src' rm -f .depend touch .depend ghc -M -optdep-f -optdep.depend -optdep-xFiniteMap -optdep-xPretty -recomp -O - f glasgow-exts Casm.lhs DIS.lhs Decl.lhs ErrMonad.lhs FillIn.lhs FillInMonad.l hs GCToken.lhs GreenCard.lhs Lex.lhs LexM.lhs ListUtils.lhs MarshallMonad.lhs Na me.lhs NameSupply.lhs Package.lhs PrettyUtils.lhs Proc.lhs Process.lhs Target.lh s Type.lhs Parse.hs make[1]: Leaving directory `/cygdrive/c/dapWork/temp/downloads/greencard- 3.01/gr eencard-3.01/src' make[1]: Entering directory `/cygdrive/c/dapWork/temp/downloads/greencard- 3.01/g reencard-3.01/src' ghc -recomp -O -fglasgow-exts -c Target.lhs -o Target.o ghc -recomp -O -fglasgow-exts -c PrettyUtils.lhs -o PrettyUtils.o ghc -recomp -O -fglasgow-exts -c Casm.lhs -o Casm.o Casm.lhs:544: Warning: Pattern match(es) are overlapped In a case alternative: _ -> ... Casm.lhs:577: Warning: Pattern match(es) are overlapped In a case alternative: _ -> ... Casm.lhs:616: Warning: Pattern match(es) are overlapped In a case alternative: _ -> ... Casm.lhs:631: Warning: Pattern match(es) are overlapped In a case alternative: _ -> ... ghc -recomp -O -fglasgow-exts -c ListUtils.lhs -o ListUtils.o ghc -recomp -O -fglasgow-exts -c ErrMonad.lhs -o ErrMonad.o ghc -recomp -O -fglasgow-exts -c Name.lhs -o Name.o ghc -recomp -O -fglasgow-exts -c DIS.lhs -o DIS.o ghc -recomp -O -fglasgow-exts -c Type.lhs -o Type.o ghc -recomp -O -fglasgow-exts -c Decl.lhs -o Decl.o ghc -recomp -O -fglasgow-exts -c FillInMonad.lhs -o FillInMonad.o ghc -recomp -O -fglasgow-exts -c NameSupply.lhs -o NameSupply.o ghc -recomp -O -fglasgow-exts -c FillIn.lhs -o FillIn.o ghc -recomp -O -fglasgow-exts -c GCToken.lhs -o GCToken.o ghc -recomp -O -fglasgow-exts -c MarshallMonad.lhs -o MarshallMonad.o ghc -recomp -O -fglasgow-exts -c Proc.lhs -o Proc.o ghc -recomp -O -fglasgow-exts -c LexM.lhs -o LexM.o ghc -recomp -O -fglasgow-exts -c Lex.lhs -o Lex.o ghc -recomp -O -fglasgow-exts -Onot -c Parse.hs -o Parse.o Parse.hs:1733: Warning: Pattern match(es) are overlapped In a case alternative: _ -> ... ghc -recomp -O -fglasgow-exts -c Process.lhs -o Process.o ghc -recomp -O -fglasgow-exts -c Package.lhs -o Package.o ghc -recomp -O -fglasgow-exts -cpp -DBEGIN_GHC_ONLY='-}' -DEND_GHC_ONLY='{- ' - DBEGIN_NOT_FOR_GHC='{-' -DEND_NOT_FOR_GHC='-}' -DPURE_WIN32=0 -c GreenCard.lhs -o GreenCard.o ghc -c ErrorHook.c -o ErrorHook.o ghc -recomp -O -fglasgow-exts -o greencard-bin Casm.o DIS.o Decl.o ErrMonad. o FillIn.o FillInMonad.o GCToken.o GreenCard.o Lex.o LexM.o ListUtils.o Marshall Monad.o Name.o NameSupply.o Package.o PrettyUtils.o Proc.o Process.o Target.o Ty pe.o Parse.o ErrorHook.o sed < greencard.ghc.in > greencard "s|@libdir@|/cygdrive/c/Programme/GreenCard// lib/greencard-3.01|g" chmod a+x greencard install -D greencard-bin /cygdrive/c/Programme/GreenCard//lib/greencard- 3.01/gre encard-bin install -D greencard /cygdrive/c/Programme/GreenCard//bin/greencard make[1]: Leaving directory `/cygdrive/c/dapWork/temp/downloads/greencard- 3.01/gr eencard-3.01/src' make[1]: Entering directory `/cygdrive/c/dapWork/temp/downloads/greencard- 3.01/g reencard-3.01/lib' ../src/greencard-bin --libdir=. Foreign/GreenCard.gc ghc -package-name greencard -cpp -fglasgow-exts -fno-prune-tydecls -c Foreign/ GreenCard.hs -o Foreign/GreenCard.o -hisuf hi ghc.exe: unrecognised flags: -fno-prune-tydecls Usage: For basic information, try the `--help' option. make[1]: *** [Foreign/GreenCard.o] Error 1 rm Foreign/GreenCard.hs make[1]: Leaving directory `/cygdrive/c/dapWork/temp/downloads/greencard- 3.01/gr eencard-3.01/lib' make[1]: Entering directory `/cygdrive/c/dapWork/temp/downloads/greencard- 3.01/g reencard-3.01/src' make[1]: Nothing to be done for `install'. make[1]: Leaving directory `/cygdrive/c/dapWork/temp/downloads/greencard- 3.01/gr eencard-3.01/src' make[1]: Entering directory `/cygdrive/c/dapWork/temp/downloads/greencard- 3.01/g reencard-3.01/lib' ../src/greencard-bin --libdir=. Foreign/GreenCard.gc ghc -package-name greencard -cpp -fglasgow-exts -fno-prune-tydecls -prof -c For eign/GreenCard.hs -o Foreign/GreenCard.p_o -hisuf p_hi ghc.exe: unrecognised flags: -fno-prune-tydecls Usage: For basic information, try the `--help' option. make[1]: *** [Foreign/GreenCard.p_o] Error 1 rm Foreign/GreenCard.hs make[1]: Leaving directory `/cygdrive/c/dapWork/temp/downloads/greencard- 3.01/gr eencard-3.01/lib' make: *** [install] Error 2 </errors> How can I fix them? TIA Dmitri Pissarenko -- Dmitri Pissarenko Software Engineer http://dapissarenko.com

1 1

RE: [Haskell-cafe] Point-free style
by Tim Docker 15 Feb '05

15 Feb '05

Ketil Malde wrote: > (.) . (.) .(.) > > I entered it into GHCi, and got > > :: forall a a b c a. > (b -> c) -> (a -> a -> a -> b) -> a -> a -> a -> c I spent a minute or so attempting to intuit the type signature of this, before cheating and entering it into ghci also. Is there a straightforward technique by which type signatures can be "hand calculated", or does one end up needing to run the whole inference algorithm in one's head? Tim

12 17

RE: [Haskell-cafe] Parsing in Haskell
by Simon Marlow 15 Feb '05

15 Feb '05

On 15 February 2005 10:36, Johan Glimming wrote: > I want to implement a little algebraic specification language in > Haskell, and I have a working C implementation available which uses > yacc/flex. > > What is the best way of replacing yacc/bison and (f)lex when migrating > the project into Haskell? There are yacc & lex equivalents for Haskell, in the form of Happy (http://www.haskell.org/happy) and Alex (http://www.haskell.org/alex) respectively. Cheers, Simon

1 0

Parsing in Haskell
by Johan Glimming 15 Feb '05

15 Feb '05

Hi I want to implement a little algebraic specification language in Haskell, and I have a working C implementation available which uses yacc/flex. What is the best way of replacing yacc/bison and (f)lex when migrating the project into Haskell? Best Wishes, Johan

4 3

RE: [Haskell-cafe] Top 20 ``things'' to know in Haskell
by Bayley, Alistair 15 Feb '05

15 Feb '05

Were you thinking of something like "[n] Things a Java Programmer Should Know About Ruby" ? http://jimweirich.tadalist.com/lists/public/14055 Perhaps you'd like to start a page on the wiki. A link from here, maybe? http://haskell.org/hawiki/FrequentlyAskedQuestions The libraries I think I used the most when starting were: Data.List Data.Char Data.Maybe Data.Either System.IO (reading and writing files) System.Environment (for getArgs) Data.Set Data.FiniteMap (soon to be replaced) Of course, a lot of this is already in the Prelude, so you'll be using it indirectly. > -----Original Message----- > From: Jacques Carette [mailto:carette@mcmaster.ca] > Sent: 07 February 2005 15:31 > To: haskell-cafe(a)haskell.org > Subject: [Haskell-cafe] Top 20 ``things'' to know in Haskell > > The recent post of Graham Klyne (below) reminds me that I > have meant to ask: > is there a ``top 20'' things a serious programmer should know > when writing > code in Haskell? Of course there is a lot of programming > language theory > that would be great to know, but I mean really down-to-earth > things like the > 2 items below (module Maybe, the 'maybe' function). > > The Haskell libraries are quite large, and it is unrealistic > to try to get > familiar with all of them right away. But getting a > ``small'' list would be > very useful - I think of this as step 2 after one learns to > get comfortable > with a language. I had done this (for Maple) for training > new hires at > Maplesoft, and I definitely noticed that they became more idiomatic > programmers faster this way. > > Jacques > > PS: of course, this could already exist on haskell.org and/or > the Wiki, but > not in an 'obvious' enough place as I missed it... > > -----Original Message----- > From: haskell-cafe-bounces(a)haskell.org > [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of Graham Klyne > Sent: February 7, 2005 10:09 AM > To: Yuri D'Elia; haskell-cafe(a)haskell.org > Subject: [Haskell-cafe] Re: [Haskell] [newbye] 'Just a' > > You might also be interested in the library function 'maybe': > http://www.haskell.org/onlinereport/standard-prelude.html#$vmaybe > > or maybe (sic) Maybe.fromMaybe in: > http://www.haskell.org/onlinereport/maybe.html > > #g ----------------------------------------- ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

15 27

RDF and stuff (was: Point-free style ...)
by Graham Klyne 15 Feb '05

15 Feb '05

At 23:00 10/02/05 -0500, David Menendez wrote: >Here's another one: > > addTriple (s,p,o) = addArc s p o . addNode s . addNode p . addNode o It looks like you're playing around with RDF here. A quick check of your web site shows a Semantic Web angle to some of your workings. I also see you show up in some of the ESW work. You may be interested that I have a full RDF/XML parser in Haskell (based on a modified version of HaXML) (and also a reasonably competent Notation3 parser). It passes all of Dave Beckett's RDF parser test cases, which include all the W3C RDF core WG test cases, (except one to do with I18N handling). I haven't yet found time to wrap it all up neatly, but the code is available here: RDF/XML parser and test code: http://www.ninebynine.org/Software/HaskellRDF/RDF/Harp/ Supporting code for RDF node handling: http://www.ninebynine.org/Software/HaskellRDF/RDF/Label/ Modified HaXML parser: http://www.ninebynine.org/Software/HaskellUtils/HaXml-1.12/ URI parser (above should also work with library version in next GHC): http://www.ninebynine.org/Software/HaskellUtils/Network/ Possibly uses some other support modules from: http://www.ninebynine.org/Software/HaskellUtils/ I had been meaning to wrap all this into my Swish package (http://www.ninebynine.org/RDFNotes/Swish/Intro.html) but real work intervened. I do intend to return to this when I can find an excuse to make it part of the new day job. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

Automatic pointless translation
by oleg＠pobox.com 15 Feb '05

15 Feb '05

This message is a literate Haskell98 code for translating proper linear combinators into a point-free style. That is, we will be converting (closed, albeit that is not strictly a requirement) terms of the form ``\x1 ... xn -> term'' where each variable xi has at most one occurrence in term. The technique can be easily generalized to non-linear terms. Other possible generalizations is automatical derivation of the point-less code from the _signature_ of a function. The body of the function isn't actually needed, for applicative and tuple fully-polymorphic functions. > module PF where Our terms have the following simple structure > data Term = Var String > | CId -- identity > | CC -- composition > | CK -- const > | CF -- flip > | A Term Term > deriving (Eq, Show) and a bit of standard term-rewriting grind > occurs v v' | v == v' = True > occurs v (A t1 t2) = occurs v t1 || occurs v t2 > occurs _ _ = False > > ground (Var _) = False > ground (A t1 t2) = ground t1 && ground t2 > ground _ = True We introduce term normalization. A normalized term has the following structure data NT = Ground | A NT Var | A NT Ground that is, the term tree is linear with respect to variables. After normalization, our (closed) source term \x1 ... xn -> term becomes \x1 ... xn -> term' y1 ... ym where each y1 is either a variable or a ground term, and term' is ground. Furthermore, if we drop ground terms from the list y1 ... ym, it becomes a permutation of a subset of x1 ... xn. The normalization is easily performed by tree rotations > norm t | ground t = t > norm (A t1 v@(Var _)) = A (norm t1) v > norm (A t1 t2) | ground t2 = A (norm t1) t2 > norm (A t1 (A t2 t3)) = norm (A (A (A CC t1) t2) t3) > norm v@(Var _) = A CId v > norm c = c As you can see, guards are prominent. A few tests > test1 = norm (A (Var "f") (A (A (Var "g") (Var "a")) (Var "b"))) > -- \f g h x y -> f (g x) (h y) > test2 = norm (A (A (Var "f") (A (Var "g") (Var "x"))) > (A (Var "h") (Var "y"))) > > test32 = norm (A CF (A (A (A (A CId CC) CC) (Var "f")) (Var "g"))) > test34 = norm (A (A CC (A CC CF)) (A (A CId CC) CC)) > test35 = norm (A (A CC (A (Var "g") CF)) (A (A CId CC) CC)) The next step is elimination of variables using eta-reductions, const introductions, and flips to bring the variables into the right position. The function `elim' takes a list of free variables to eliminate, in reverse order, and the term. The function returns the point-free term. > elim [] t = t > -- eta reduction, linearity assumption > elim (h:r) (A t v) | h == v = elim r t > -- if \a b -> t a b then > -- \a b x -> const (t a b) x > elim (h:r) t | not (occurs h t) = elim r (norm (A CK t)) > elim v@(h:r) t = elim v (norm (doflip h t)) > where > doflip v (A (A t v1) v2) | v == v1 = (A (A (A CF t) v2) v1) > doflip v (A t v2) = A (doflip v t) v2 > doflip v t = error $ (show v) ++ "\n" ++ (show t) And that is it. We just need to print the terms nicely: > print_nice (Var v) = show v > print_nice (A (A CC x) y) = "(" ++ (print_nice x) ++ " . " > ++ (print_nice y) ++ ")" > print_nice (A CC x) = "(" ++ (print_nice x) ++ " .)" > print_nice (A x y) = "(" ++ print_nice x ++ ") (" ++ > print_nice y ++ ")" > print_nice CC = "(.)" > print_nice CK = "const" > print_nice CId = "id" > print_nice CF = "flip" > > report' vars term = elim (reverse $ (map Var) vars) (norm term) > report vars = print_nice . report' vars We are ready for some tests: The first two tests are trivial: \f x y -> f x y > test11 = report ["f","x","y"] (A (A (Var "f") (Var "x")) (Var "y")) *PF> test11 "id" And \f x y -> f y x > test12 = report ["f","x","y"] (A (A (Var "f") (Var "y")) (Var "x")) *PF> test12 "(flip . id)" the next one is simple too: \f x y -> f x > test13 = report ["f","x","y"] (A (Var "f") (Var "x")) *PF> test13 "((const .) . id)" Now we can try \f g a b -> f (g a b) > test14 = report ["f","g","a","b"] > (A (Var "f") (A (A (Var "g") (Var "a")) (Var "b"))) *PF> test14 "((.) . (.))" and \f g h x y -> f (g x) (h y) > test15 = report ["f","g","h","x","y"] > (A (A (Var "f") (A (Var "g") (Var "x"))) (A (Var "h") (Var "y"))) *PF> test15 "((flip .) . ((.) . ((.) .)))" The reported derivation was ((flip . ((.) .)) .) . (.) These terms are equivalent. One may look at their types, which are identical. One may also apply these terms to suitable arguments, e.g., ((flip .) . ((.) . ((.) .))) (,) ((,) 1) ((,) 2) 3 4 This sub-thread started from \f g a b -> f (g a b): two-to-one composition, aka triple-(.). Can we generalize? Certainly: \f g a b c -> f (g a b c) > test16 = report ["f","g","a","b","c"] > (A (Var "f") > (A (A (A (Var "g") (Var "a")) (Var "b")) (Var "c"))) *PF> test16 "(((.) . (.)) . (.))" \f g a b c d -> f (g a b c d) > test17 = report ["f","g","a","b","c","d"] > (A (Var "f") > (A (A (A (A (Var "g") (Var "a")) (Var "b")) (Var "c")) > (Var "d"))) *PF> test17 "((((.) . (.)) . (.)) . (.))" *PF> ((((.) . (.)) . (.)) . (.)) ((,) 1) (,,,) 10 11 12 13 (1,(10,11,12,13)) \f g h a b c d -> f (g a b) (h c d) > test18 = report ["f","g","h","a","b","c","d"] > (A (A (Var "f") > (A (A (Var "g") (Var "a")) (Var "b"))) > (A (A (Var "h") (Var "c")) (Var "d"))) *PF> test18 "((flip .) . (((flip .) .) . (((.) . (.)) . (((.) . (.)) .))))" It really begins to look like Unlambda...

1 0

Parse error in a package file
by Dmitri Pissarenko 14 Feb '05

14 Feb '05

Hello! I'm building the haskell-jvm-bridge (http://sourceforge.net/projects/jvm- bridge/). The final step of the building procedure is to install the package of haskell- jvm-bridge. When I enter ghc-pkg -a -f javavm.ghc-pkg I'm getting the error javavm.ghc-pkg: parse error in package config file The original file looks as shown below. <original-file> Package { name = "javavm", import_dirs = ["c:/Programme/haskell-jvm-bridge-0.3- RC1/imports/"], source_dirs = [], library_dirs = [ "c:/Programme/haskell-jvm-bridge-0.3-RC1/lib/"-L ], hs_libraries = [], extra_libraries = ["stdc++","JVMBridge","JVMInvocation","HaskellJVMBridge"-L,"jvm_imp"], include_dirs = [], c_includes = [], package_deps = ["lang","concurrent","haskell98"], extra_ghc_opts = ["-fglasgow-exts","-fallow-undecidable-instances"], extra_cc_opts = [], extra_frameworks = [-L ], extra_ld_opts = [ "-Wl,-rpath,c:/Programme/haskell-jvm-bridge-0.3-RC1/lib/"-L ] } </original-file> I noted that some package files have the form [ Package, Package, ... ], and changed the original file: <original-file> [Package { name = "javavm", import_dirs = ["c:/Programme/haskell-jvm-bridge-0.3- RC1/imports/"], source_dirs = [], library_dirs = [ "c:/Programme/haskell-jvm-bridge-0.3-RC1/lib/"-L ], hs_libraries = [], extra_libraries = ["stdc++","JVMBridge","JVMInvocation","HaskellJVMBridge"-L,"jvm_imp"], include_dirs = [], c_includes = [], package_deps = ["lang","concurrent","haskell98"], extra_ghc_opts = ["-fglasgow-exts","-fallow-undecidable-instances"], extra_cc_opts = [], extra_frameworks = [-L ], extra_ld_opts = [ "-Wl,-rpath,c:/Programme/haskell-jvm-bridge-0.3-RC1/lib/"-L ] }] </original-file> This didn't help me, I got the same error message. Please tell me what's wrong with this package file. Thanks in advance Dmitri Pissarenko -- Dmitri Pissarenko Software Engineer http://dapissarenko.com

2 2

Fwd: [Haskell-cafe] Point-free style
by shiqi cao 13 Feb '05

13 Feb '05

---------- Forwarded message ---------- From: shiqi cao <shiqicaoml(a)gmail.com> Date: Sun, 13 Feb 2005 21:25:56 -0500 Subject: Re: [Haskell-cafe] Point-free style To: Tim Docker <timd(a)macquarie.com.au> On Mon, 14 Feb 2005 11:24:12 +1100, Tim Docker <timd(a)macquarie.com.au> wrote: > Ketil Malde wrote: > > > (.) . (.) .(.) > > > > I entered it into GHCi, and got > > > > :: forall a a b c a. > > (b -> c) -> (a -> a -> a -> b) -> a -> a -> a -> c > > I spent a minute or so attempting to intuit the type signature of this, > before cheating and entering it into ghci also. > > Is there a straightforward technique by which type signatures can be > "hand calculated", or does one end up needing to run the whole inference > algorithm in one's head? Hi Ketil, I think the type signatures can be derived by hand. First let us take a look the type of (.) (.) :: forall c a b. (b -> c) -> (a -> b) -> a -> c one thing need to be taken into account is (.) is left associative, but composition of two functions , like f(g(x)), brings the inner function into our mind first intuitively. Since we know the type of (.) calculating the (.).(.) is algebra manipulation, but be careful. The left hand (.) and right hand (.) are not identical in terms of type. Let us call the left one (.)_1, right one (.)_2 and the middle one (.)_3. Let us type (.)_2 first since the type of (.)_1 is based on (.)_2 (.)_2 :: (b -> c) -> (a->b) -> (a -> c) ----X---- ---------Y---------- Let X = (b -> c) and Y = (a->b) -> (a -> c) (.)_2 :: X -> Y Then (.)_3 must be (Y -> Z) -> (X -> Y) -> (X -> Z) Then (.)_2 must be (Y -> Z) Since (.)_3 is derived (.).(.) has type (X->Z), we need to find out what Z is. (.)_2 :: (Y -> Z) => (.)_2 :: ((a->b) -> (a -> c)) -> Z [1] (.) :: forall C A B. (B -> C) -> (A -> B) -> (A -> C) => (.)_2 :: ((a->b) -> (a -> c)) -> (d -> (a -> b)) -> (d -> (a -> c)) [2] There d is an arbitrary type. [1] and [2] => Z = (d -> (a -> b)) -> (d -> (a -> c)) => (.).(.) :: (X -> Z) = (b -> c) -> (d -> (a -> b)) -> (d -> (a -> c)) GHCi result is (.).(.) :: forall a b c a1. (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c Shiqi Cao

1 0