- Haskell - Haskell.org

Re: lexer puzzle
by b.i.mills＠massey.ac.nz 25 Sep '03

25 Sep '03

Hi, > Haskell to me seems to be a great language with a syntax problem, > and a bad case of too many ways to do the same thing; thus every > programmer does things their own way and it's difficult to grasp > the language by looking at examples. int fact(int x){int t=1; while(x) t*=x--;} int fact(int x){int t=1; for(int i=1;i<=x;i++) t=t*i;} int fact(int x){if(x=0) return 1; else return x * fact(x-1);} int fact(int x){return aux(x,1);} int aux(int x, int t){ return x ? t : aux(x-1,t*x);} int fact(int x){int t=1; while(x && (t*=x--)); return t;} #define TRUE 1 #define FALSE 0 int fact(int x) { if((x==0)==TRUE) return 1; else { t = fact(x-1); return(t*x); } } x = x + 1; x += 1; x++; #include <stdio.h> main(t,_,a) char *a; { return!0<t?t<3?main(-79,-13,a+main(-87,1-_,main(-86,0,a+1)+a)): 1,t<_?main(t+1,_,a):3,main(-94,-27+t,a)&&t==2?_<13? main(2,_+1,"%s %d %d\n"):9:16:t<0?t<-72?main(_,t, "@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l+,/n{n+,/+#n+,/#\ ;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l \ q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# \ ){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' \ iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \ ;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# \ }'+}##(!!/") :t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1) :0<t?main(2,2,"%s"):*a=='/'||main(0,main(-61,*a, "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"),a+1); } I'm not being facetious here, but deadly serious. Your average language that is worth anything allows programmers to program in more than one way. If the language truely constrained everyone to produce a given program looking exactly the same way, then it is probably a nightmare to program in. Speaking as someone who comes from a C/C++/Java/Scheme/Assembler/Algebra background, I don't find Haskell syntax to be any more annoying than any other typical syntax. And I did not find any particular clash with `.' It's like the the game of Go, the rules (syntax) you learn in one sitting, but the strategy can take a life time. Any programmer should be able to pick up a new syntax in a week. (not that you want to do that every week, because you want to get down to playing the game). Regards, Bruce. Institute for Information and Mathematical Sciences Massey University at Albany, email: B.I.Mills(a)massey.ac.nz web: http://www.massey.ac.nz/~bimills

1 0

lexer puzzle
by Iavor Diatchki 25 Sep '03

25 Sep '03

hi everyone, what do people think should be the tokens produced by a haskell lexer when applied to the following input: A... bye iavor & thomas h. -- ================================================== | Iavor S. Diatchki, Ph.D. student | | Department of Computer Science and Engineering | | School of OGI at OHSU | | http://www.cse.ogi.edu/~diatchki | ==================================================

8 9

"Real world" example needed for ...
by Steffen Mazanek 25 Sep '03

25 Sep '03

Hello, I am looking for a real world example of a type constructor, that expects another type constructor as an argument in the context of subtyping, e.g., one could define --not Haskell98 data T a b c = F (a b c) a::T (->) Pt Pt a = F id b::T (->) CPt CPt b = F id l = [a,b] Thereby CPt is assumed to be a subtype of Pt. From my expectations l should be typable [T (->) CPt Pt], because of contravariance of (->). Using c::T (Either) Pt Pt and d::T (Either) CPt CPt one would gain [c,d]::T (Either) Pt Pt. I need this "real world" example for the sake of motivation, that variance can be expressed by Haskell kinds, e.g., in a kind system the kind of T could be (a->b->*)->a->b->*. Thereby the "kind variables" a and b can be instantiated by "special kinds" + and -, that represent co- and contravariance, respectively. So one would have T (->)::- -> + -> * and T (Either)::+ -> + -> * and so on... Any ideas are very appreciated. Ciao, Steffen

1 0

Library Infrastructure Proposal & Home Page
by Isaac Jones 24 Sep '03

24 Sep '03

Followups to libraries(a)haskell.org please. Greetings, After many rounds of email and discussion, some wiki work, and discussion at the HIM, I've finally put together a proposal for the Library Infrastructure Project. I've inserted the introduction below. The draft proposal itself is available in a variety of formats. I've also started a web page for the project under the haskell.org site: http://www.haskell.org/libraryInfrastructure/ Please let me know if there's anything that needs to be added, if anything is confusing, etc. Comments and questions are welcome by email or on the libraries(a)haskell.org mailing list. peace, isaac ps. I expect to be moving a lot of stuff off of the wiki page since it is duplicated here. ------------------------------------------------------------ Library Infrastructure Project Proposal The Library Infrastructure Project is an effort to provide a framework for developers to more effectively contribute their software to the Haskell community. The Haskell Implementations[1] come included with a good set of standard libraries, but this set is constantly growing and is maintained centrally. This model does not scale up well, and as Haskell grows in acceptance, the quality and quantity of available libraries is becoming a major issue. There are a wide variety of Haskell Implementations (both compilers and interpreters), each of which target a variety of hardware architectures and operating systems. There are also a number of different groups and individuals providing libraries, and these libraries depend upon each other and they depend upon external systems such as Java or GTK. It can be very difficult for an end user to manage these dependencies and build all the necessary software at the correct version numbers on their platform: there is currently no generic build system to abstract away differences between Haskell Implementations and operating systems [2]. The Library Infrastructure Project seeks to provide some relief to this situation by building tools to assist developers, end users, and operating system distributers. This is a draft proposal. If you have comments, please email Isaac Jones. The latest version of this document should be available in a variety of formats from the Library Infrastructure Project home page. _________________________________________________________ Table of Contents 1. High-Level Overview 2. Issues Facing Developers 2.1. Issues Facing Packagers 2.2. Why We Should Solve This 3. A Solution for Haskell in Haskell 3.1. The Module Design 3.2. But Why Should We Use Haskell? 3.3. Setup.lhs Command-Line Interface 3.4. An Example Setup.lhs Script 4. Distribution Module 4.1. Distribution.Build 4.2. Distribution.Install 4.3. Distribution.Package 4.3.1. PackageConfig Data Structure 4.4. haskell-config Command-line interface 4.5. haskell-pkg? 4.6. Distribution.Config 5. Use Cases 6. Means of Distribution and Layered Tools 7. Development Plan A. Related Systems A.1. Debian A.2. Python Distutils A.3. CPAN and Boost A.4. FreeBSD's Ports System A.5. The XEmacs Packaging System A.6. Make-Based Systems A.7. hmake 1. High-Level Overview On a high level, we say that we want the system to help the user to install packages (whether they be libraries or applications) and their dependencies. To accomplish this, we propose a system similar to Python's Distutils (Section A.2) where each Haskell tool is distributed with a script (Section 3.4) which has a standard command-line interface. This script will provide a familiar user interface (Section 3.3) for compiling, installing, and removing packages and their dependencies. For instance, to install the HUnit package, the user might download the source code from the web site, change into the HUnit directory, and type ./Setup.lhs install default, which would build and install the HUnit package for the default compiler. Similarly, he might type ./Setup.lhs install nhc to install the package for NHC. Other tasks might be necessary to make the package known to the system, such as registering it with the Haskell Implementation of interest (Section 4.3). Such tasks would also be performed by this Setup program. FULL TEXT AT: http://www.haskell.org/libraryInfrastructure/proposal/index.html

1 0

Re: pretty newby
by Luc Taesch 24 Sep '03

24 Sep '03

Thanks. i understand that a2ps is rather for printing. What I had in mind what to pp my own programs, to clean the source layout, rather. The process i used in other context is to hack , without really taking care of the layout ( say getting distracted by) , and once i got a resonalble level of stability, i cleaned the program, using a pp; ideally in haskell, this would add the typing for me, also. ( still havent made my religion if that's cool to have the typing on top of the definition, or not, but at least for doc generation purpose, that's good.) feedback on that ? so the two gain i was expecting were : - cleaning the layout, after i removed all the debugging code - generating the type but i understood from Per from that the parser would not take care of the comments. ( not take care, or remove , btw ?). alos, Im surprised that this bland issue has not already been solved (PP lib paper looks dated 96). no offence intended, but aas im newbie, i wonder what am i missing ? what is different in the process of creation so that this need did not arised already? i should admint i'm puzzled, given the facilities at hand... > Alle 16:05, marted� 23 settembre 2003, Luc Taesch ha scritto: > > are there any facility to pretty print an haskell program ? > > If what you need is an external program and not a library, have a look > at GNU a2ps. > > Vincenzo > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell

8 7

From enumerators to cursors: turning the left fold inside out
by oleg＠pobox.com 24 Sep '03

24 Sep '03

There are two basic approaches of accessing a collection, be it a file, a database, or a generating function. One approach relies on enumerators (aka folds); the other is based on lazy lists (aka cursors, streams). Given a stream, we can always construct the corresponding enumerator. It's perhaps less appreciated that given a left fold enumerator, we can always construct the corresponding stream [1]: we can mechanically invert an enumerator inside out. It has been argued [2] that the enumerator approach is superior, especially from the point of view of managing scarce resources such as database connections. When we design the interface to a collection, it seems a good idea to choose enumerator as a primitive. We can always obtain a stream if we really need it. The mechanical inversion procedure presented in [2] had a catch: it relies on shift/reset (or call/cc plus a mutable cell, which is the same thing). How can we do such an inversion in Haskell? Well, we can introduce a right fold enumerator, which is more amenable to such transformation. Or we can use a continuation monad and emulate shift/reset. The present article demonstrates a third approach: a half-baked, non-recursive left-fold. We argue that such a left fold is the best interface for a collection. Indeed, given the half-baked left-fold we can: - instantiate it into the ordinary left fold - instantiate in into a stream If we turn two enumerators into streams, we can *safely* interleave these streams. The rest of the article demonstrates the inversion procedure. We use a file as a sample "collection", a collection of characters. Haskell provides a stream interface to that collection: hGetChar. We implement a left fold enumerator. We then show how to turn that enumerator back to a stream: how to implement a function mygetchar only in terms of the left fold enumerator. The approach is general and uses no monadic heavy lifting. The following code is Haskell98. No unsafe operations are used. > import IO The desired left-fold enumerator over a file: > hfold_left:: FileName -> Title > -> Iteratee seed > -> seed -- the initial seed > -> IO seed > type FileName = String > type Title = String -- just an identifying string for debug printing > type Iteratee seed = seed -> Char -> Either seed seed The function (seed -> Char -> Either seed seed) is an iteratee: it takes the current seed and the current character and returns a new seed. To be more precise, if it returns Right seed', the iteration continues with seed' as the new seed. If the iteratee returns Left seed'', the enumerator immediately stops further iterations, frees all the resources, and returns seed'' as the final result. So our left fold enumerator supports premature termination of iterations, a quite useful feature. As me mentioned above, we actually need a half-baked, non-recursive enumerator hfold_left' > make_hfold_left' filename title = do > h <- openFile filename ReadMode > let hfold_left' self iteratee seed = do > mc <- try $ hGetChar h > case mc of > Left exc -> hClose h >> return seed > Right c -> do > putStrLn $ " reading from " ++ title ++ ". Got " ++ (show c) > case iteratee seed c of > Left seed -> hClose h >> return seed > Right seed -> self iteratee seed > return hfold_left' We can easily obtain the desired hfold_left as an instantiation of hfold_left': > hfold_left filename title iteratee seed = do > hfold_left' <- make_hfold_left' filename title > let g = hfold_left' g > hfold_left' g iteratee seed We should note that the Handle is an internal resource and is never leaked. The statement putStrLn $ " reading from " ++ title ... is for debugging. We want to be sure that we don't read from a stream too much. This will be important for interleaving. Let us create a test file > tf = "/tmp/a" > make_test_file fname = do > h <- openFile fname WriteMode > mapM_ ((hPutStr h) . show) [0..9] > putStrLn $ "Wrote " ++ fname > hClose h and test our left fold enumerator > test_read fname n = do > (count,acc) <- hfold_left fname "handle" reader (0,[]) > putStrLn $ "Have read: " ++ (show acc) > where reader (count,acc) c = > let count' = count + 1 > acc' = c:acc > in (if count' >= n then Left else Right) (count',acc') The first test checks the premature termination. We read only five characters, and then terminate the iteration and dispose of its resources, including the (invisible) handle. *Main> test_read tf 5 reading from handle. Got '0' reading from handle. Got '1' reading from handle. Got '2' reading from handle. Got '3' reading from handle. Got '4' Have read: "43210" The following tests the exhaustive iteration. *Main> test_read tf 20 reading from handle. Got '0' reading from handle. Got '1' reading from handle. Got '2' reading from handle. Got '3' reading from handle. Got '4' reading from handle. Got '5' reading from handle. Got '6' reading from handle. Got '7' reading from handle. Got '8' reading from handle. Got '9' Have read: "9876543210" Let us suppose that make_hfold_left' is the only way to access files. Can we recover ordinary i/o streams from it? The answer is yes. We can get the familiar open, getchar and eof functions from the half-baked enumerator. Furthermore, the derivation of these functions is *independent* of the precise nature of the enumerator. We will never need (nor be given) access to the handle. > data MyStream = MyNil (Maybe Char) | MyCons Char (IO MyStream) > > myopen:: FileName -> Title -> IO MyStream > > myopen filename title = do > hfold_left' <- make_hfold_left' filename title > let k fn (MyNil Nothing) = return $ MyNil Nothing > k fn (MyNil (Just c)) > = return $ MyCons c (hfold_left' k fn (MyNil Nothing)) > hfold_left' k (\_ c -> Right $ MyNil $ Just c) (MyNil Nothing) > mygetchar:: MyStream -> IO (Char,MyStream) > mygetchar (MyCons c k) = k >>= (return . ((,) c)) > > myiseof:: MyStream -> Bool > myiseof (MyNil Nothing) = True > myiseof _ = False We can now test reading from two streams with interleaving: > test_interleave fname = do > stream1 <- myopen fname "stream1" > stream2 <- myopen fname "stream2" > > putStrLn "\nReading 2 chars from one stream" > (c1,stream1) <- mygetchar stream1 > (c2,stream1) <- mygetchar stream1 > putStrLn $ "Read: " ++ (show [c1,c2]) > > putStrLn "\nReading 3 chars from the second stream" > (c1,stream2) <- mygetchar stream2 > (c2,stream2) <- mygetchar stream2 > (c3,stream2) <- mygetchar stream2 > putStrLn $ "Read: " ++ (show [c1,c2,c3]) > > putStrLn "\nReading again 2 chars from the first stream" > (c1,stream1) <- mygetchar stream1 > (c2,stream1) <- mygetchar stream1 > putStrLn $ "Read: " ++ (show [c1,c2]) *Main> test_interleave tf reading from stream1. Got '0' reading from stream2. Got '0' Reading 2 chars from one stream reading from stream1. Got '1' reading from stream1. Got '2' Read: "01" Reading 3 chars from the second stream reading from stream2. Got '1' reading from stream2. Got '2' reading from stream2. Got '3' Read: "012" Reading again 2 chars from the first stream reading from stream1. Got '3' reading from stream1. Got '4' Read: "23" Note that we read ahead by exactly one character. If we want to detect EOF, that is inevitable (we need to attempt reading if we want to detect EOF). We should point out the relationship between hfold_left, hfold_left' and myopen: hfold_left is the fixpoint of hfold_left'. OTH, myopen captures the continuation of hfold_left' in an IO action. This relationship once again illustrates that call/cc and Y are indeed two sides of the same coin [3]. [1] General ways to traverse collections http://pobox.com/~oleg/ftp/Scheme/enumerators-callcc.html [2] An argument against cursors http://srfi.schemers.org/srfi-44/mail-archive/maillist.html [3] Self-application as the fixpoint of call/cc http://google.com/groups?selm=7eb8ac3e.0309182239.5a64b3b1%40posting.google…

2 1

pretty newby
by Luc Taesch 23 Sep '03

23 Sep '03

are there any facility to pretty print an haskell program ? im aware of HPJ combinators library, but i was looking for a command line utility, rather.. am i missing an entry in HPJ ? thanks Luc

4 3

Canonic labeling of graphs
by JP Bernardy 23 Sep '03

23 Sep '03

Hello all, As an exercise, I've implemented an algorithm for canonic relabeling of graphs. (Two graphs are isomorphic iff they have the same canonic labelling) The method used is stolen from Brendan McKay, "Practical graph isomorphism". http://cs.anu.edu.au/~bdm/nauty/PGI/ In the hope that it is useful to anyone, I attach the code (for GHC 6). Any remark is welcome. Cheers! --JP. __________________________________ Do you Yahoo!? Yahoo! SiteBuilder - Free, easy-to-use web site design software http://sitebuilder.yahoo.com

1 0

Re: Polymorphic Recursion / Rank-2 Confusion
by oleg＠pobox.com 23 Sep '03

23 Sep '03

Dominic Steinitz wrote: > My motivation in using this type was to see if, for example, I could > restrict addition of a vector to another vector to vectors of the same > length. This would be helpful in the crypto library where I end up having to > either define new length Words all the time or using lists and losing the > capability of ensuring I am manipulating lists of the same length. Perhaps you might find the following http://pobox.com/~oleg/ftp/Haskell/number-parameterized-types.html relevant to your task. The page demonstrates bitvectors of a statically-checked width. An attempt to AND or OR two bitvectors of different widths results in a type error. The width can be specified in _decimal_ rather than in binary, which makes types smaller and far easier to read. Type error messages also become more comprehensible. To implement just the width-checking, we need only Haskell 98. Incidentally, the approach can be easily extended to arbitrary bases, e.g., base64. Therefore, we can define numerals over a field Z^{*}_p whose modulus p is statically known and statically checked. It would be a type error to add or multiply two numerals with different moduli. With base64-bigits, we need only 86 bigits for a 512-bit modulus. Eighty-six terms make a type expression a bit long, but still manageable; whereas binary types such as Zero and One would make the approach unfeasible.

1 0

Polymorphic Recursion / Rank-2 Confusion
by Dominic Steinitz 22 Sep '03

22 Sep '03

Can anyone tell me why the following doesn't work (and what I have to do to fix it)? I thought by specifying the type of coalw as rank-2 would allow it to be used both at a and (a,b). Dominic. Reading file "Test.hs":tten Type checking ERROR "Test.hs":18 - Inferred type is not general enough *** Expression : \(w1,w2) -> coalw w1 ++ coalw w2 *** Expected type : a -> [b] *** Inferred type : (a,b) -> [c] data Vector_ v w = Zero v | Even (Vector_ v (w,w)) | Odd (Vector_ (v,w) (w,w)) deriving Show vzero = Zero () vone = Odd (Zero ((),'a')) vtwo = Even (Odd (Zero ((),('a','b')))) vthree = Odd (Odd (Zero (((),'a'),('b','c')))) vfour = Even (Even (Odd (Zero ((),(('a','b'),('c','d')))))) coal_ :: (forall a b. a -> [b]) -> (forall c d. c -> [d]) -> Vector_ v w -> [w] coal_ coalv coalw (Zero v) = coalv v coal_ coalv coalw (Even v) = coal_ coalv (\(w1,w2) -> (coalw w1) ++ (coalw w2)) v coal_ coalv coalw (Odd v) = coal_ (\(v,w) -> (coalv v) ++ (coalw w)) (\(w1,w2) -> (coalw w1) ++ (coalw w2)) v

4 8