- Haskell-Cafe - Haskell.org

Gobbler Benchmarks
by Adrian Hey 21 Feb '08

21 Feb '08

Hello Folks, There's been some discussions recently about the pros and cons of various coding styles, particularly whether stack greedy or heap greedy is best, and how (if) ghcs stack management in particular should affect all this. In particular, the problem of implementing an eager take function. Here's some real numbers measured with ghc 6.8.2 under windowsxp using AMD Athlon 64 1.8 GHz. The source code can be found here.. http://homepages.nildram.co.uk/~ahey/Test1.zip There are 4 possible implementations that have been tested: -- Uses O(n) stack stackGobbler :: Int -> [x] -> [x] stackGobbler 0 _ = [] stackGobbler _ [] = [] stackGobbler n (x:xs) = let xs' = stackGobbler (n-1) xs in xs' `seq` (x:xs') -- Uses O(n) heap instead, O(1) stack heapGobbler :: Int -> [x] -> [x] heapGobbler = heapGobbler' [] where heapGobbler' rxs 0 _ = reverse rxs heapGobbler' rxs _ [] = reverse rxs heapGobbler' rxs n (x:xs) = heapGobbler' (x:rxs) (n-1) xs -- Neils O(n) heap version, O(1) stack neilGobbler :: Int -> [x] -> [x] neilGobbler n xs = length res `seq` res where res = take n xs -- Continuation passing O(n) heap version, O(1) stack cpGobbler :: Int -> [x] -> [x] cpGobbler = f id where f c 0 _ = c [] f c _ [] = c [] f c n (x:xs) = f (\xs' -> c (x:xs')) (n-1) xs There are 16 tests for each, parameterised by p=0..15. Each test takes 63*(2^p) elements from a test list of the same length, and is repeated 2^(25-p) times. So in total, 63*(2^25) elements are processed in each case (independent of p). Here are the results in "myCpuTimePrecision = 15625000000" units (the figure exported by System.CPUTime is wrong for me). To convert these to actual time per element figures you need to multiply each by 7.4 pS (I think :-). All tests were run with fixed stack and heap sizes of 16 and 256 MiB respectively. p stack heap neil cp ---------------------------- 0 - 1793 2684 4937 2593 1 - 1860 2673 4897 2584 2 - 1910 2673 4825 2578 3 - 1927 2659 4819 2575 4 - 1946 2657 4813 2574 5 - 1950 2656 5048 2578 6 - 1960 2711 5036 2627 7 - 1976 2730 5126 2643 8 - 2072 2900 5197 2813 9 - 2439 3044 5153 2974 10 - 2685 3275 5371 3199 11 - 2760 3384 5466 3321 12 - 2930 3487 5525 3444 13 - 3181 3648 5813 3698 14 - 3698 3973 6417 4031 15 - 4727 4987 7964 5224 So pretty much as I expected. For smallish lists, stackGobbler is easily the fastest, heapGobbler and cpGobbler are pretty similar, and neilGobbler is the slowest (sorry Neil:-). The performance of all is degraded as p increases. I guess this is not too surprising, but stackGobbler seems to degrade faster so that at p=15 there's not much difference between it and heapGobbler/cpGobbler. I'm not sure what it is that causes stackGobbler to be "unfairly" penalised this way, but I'm reminded of this post from John Meacham.. http://haskell.org/pipermail/glasgow-haskell-users/2007-May/012470.html The other big problem with stackgobbler in practice is the risk of stack overflow. For p=15 it would not work at all for ghc default stack limit. Regards -- Adrian Hey

1 0

what is the fastest way to extract variables from a proposition?
by Cetin Sert 21 Feb '08

21 Feb '08

-- proposition data Prp a = Var a | Not (Prp a) | Or (Prp a) (Prp a) | And (Prp a) (Prp a) | Imp (Prp a) (Prp a) | Xor (Prp a) (Prp a) | Eqv (Prp a) (Prp a) | Cns Bool deriving (Show, Eq) -- Here are to variable extraction methods -- variable extraction reference imp. -- Graham Hutton: Programming in Haskell, 107 vars_ :: Prp a → [a] vars_ (Cns _) = [] vars_ (Var x) = [x] vars_ (Not p) = vars_ p vars_ (Or p q) = vars_ p ++ vars_ q vars_ (And p q) = vars_ p ++ vars_ q vars_ (Imp p q) = vars_ p ++ vars_ q vars_ (Xor p q) = vars_ p ++ vars_ q vars_ (Eqv p q) = vars_ p ++ vars_ q -- variable extraction new * this is faster vars :: Prp a → [a] vars p = evs [p] where evs [] = [] evs (Cns _ :ps) = [] evs (Var x :ps) = x:evs ps evs (Not p :ps) = evs (p:ps) evs (Or p q:ps) = evs (p:q:ps) evs (And p q:ps) = evs (p:q:ps) evs (Imp p q:ps) = evs (p:q:ps) evs (Xor p q:ps) = evs (p:q:ps) evs (Eqv p q:ps) = evs (p:q:ps) -- for : Not (Imp (Or (Var 'p') (Var 'q')) (Var p)) -- vars_: ['p','q','p'] -- vars : ['p','q','p'] -- order and the fact that 'p' appears twice being irrelevant: -- is there an even faster way to do this? -- -- Cetin Sert -- www.corsis.de

4 7

Selecting Array type
by Jeff φ 21 Feb '08

21 Feb '08

I'm trying to create a type called SmartArray. It is a type synonym for an array. If the element type can be unboxed, then SmartArray is an unboxed array. Otherwise, it is a boxed array. For instance, (SmartArray Int Double) is the same as (UArray Int Double) (SmartArray Int String) is the same as (Array Int String) However, my implementation of SmartArray requires me to create an instance of a selector class to tell the compiler wheither the type is boxed or unboxed. I'm hoping to avoid creating instances of the selector class for every possible type. I'd be grateful for any suggestions. Please see my code: {-# OPTIONS_GHC -fglasgow-exts -fbreak-on-exception -XOverlappingInstances #-} import Data.Ix import Data.Array.Unboxed import Data.Complex type SmartArray i e = (Ix i, SmartArraySelector a e) => (a i e) -- smartArray is similar to array function from Data.Array. But, it -- will return a UArray if e can be unboxed. Otherwise, it returns an Array. smartArray :: (i, i) -> [(i, e)] -> SmartArray i e smartArray bnd eLst = array bnd eLst class (IArray a e) => SmartArraySelector a e | e -> a where arrayType :: Ix i => a i e -> a i e arrayType = id -- SmartArraySelector selects UArray for all types that can be -- unboxed. An instance has to be created for each unboxed type. I'd -- like to avoid listing all unboxed types here. However, since there -- are only a few unboxed types, it's not too burdensome to list them -- all. (For brevity, I didn't create all possible instances.) instance SmartArraySelector UArray Bool where instance SmartArraySelector UArray Char where instance SmartArraySelector UArray Double where instance SmartArraySelector UArray Float where instance SmartArraySelector UArray Int where -- SmartArraySelector selects Array for all types that can't be -- unboxed. An instance has to be created for EVERY possible unboxed -- type that might be used with SmartArray. Since, the list of -- possible types is unlimited, this is pretty annoying. instance SmartArraySelector Array String where instance SmartArraySelector Array (Complex e) where -- I'd like to replace all the boxed instances above with one instance -- like . . . -- -- instance SmartArraySelector Array e where -- -- However, this generates an error even though, -- -XOverlappingInstances turned on. test e = smartArray (0,10) [ (i,e) | i <- [0..10]]

5 5

Re: [Haskell-cafe] Where does ~> come from?
by Wolfgang Jeltsch 21 Feb '08

21 Feb '08

Am Dienstag, 19. Februar 2008 18:26 schrieben Sie: > […] > However, I was told this: ~> a b is a ~> b, but if I write c a b and > wish the effect of a `c` b. This would not work. ~> as an infix operator > has a special place in GHC. It is not "just a type variable". Sorry, but I don’t understand fully what you mean. :-( But nevertheless, a ~> b is not the same as ~> a b but as (~>) a b. It’s just like with ordinary operators where a + b is the same as (+) a b. ~> is not special in GHC. You could use, for example, ### instead of ~> and get the same results. However, GHC accepts type operators only if you tell it to do so. Give GHC the option -XTypeOperators or insert {-# LANGUAGE TypeOperators #-} at the beginning of your source file. > […] Best wishes, Wolfgang

5 4

Haddock documentation of Data.Array.* is confusing
by Alfonso Acosta 21 Feb '08

21 Feb '08

Hi, Excuse me for the subject, but IMHO is absolutely true. Anyhow, the purpose of this message is not merely to rant about it (which I know doesn't help) but to illustrate the possible impression of a Haskell newcomers. It's been a long long time since I last used arrays in Haskell (lists are normally just fine for me) so I checked the docs to refresh my memory. This is the result of my experience: The first thing I checked was Data.Array which ... just shows function names without signatures! OK, I followed the advice shown in "Data.Array" and tried to understand the more generic interface of Data.IArray. Fine, the documentation is much better, however it mentions Data.Array.Base, whose documentation link is missing :S I was suprised to see that even if all the functions of Data.IArray (i.e. array, listArray ... ) are perfectly sensible and generic (which is nice), they are not part of ot the IArray multiparameter class. So I wondered .. how can someone add its own implementation of inmutable arrays to the IArray interface? It was obvious that "bounds" (the only method of the IArray typeclass) was not going to enough, but I tried anyway with a naive example. {-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-} data Ix i => LArray i e = LArray [e] (i,i) instance IArray LArray e where -- bounds :: (Ix i, IArray LArray e) => LArray i e -> (i,i) bounds (LArray _ b) = b GHC warned me about missing definitions for some"unsafe" methods of ArrayI which .... as expected, belong to the "phantom" Data.Array.Base module. The sources of Data.Array.Base revealed that the purpose of hiding them was to protect the user. Someone who wants add an array implementation to the IArray interface should use Data.Array.Base but why would it hurt to add a note in IArray mentioning it? and Why is Data.Array.Base hidden for Haddock (especially when there are some broken links pointing to it)? Cheers, Fons

2 2

Broken http://darcs.haskell.org/darcsweb/?
by Dominic Steinitz 21 Feb '08

21 Feb '08

I'm getting errors when I click on any of the links. I'm not sure who administers the site. IOError Python 2.4.4: /usr/bin/python Wed Feb 20 11:41:13 2008 A problem occurred in a Python script. Here is the sequence of function calls leading up to the error, in the order they occurred. /srv/darcsweb/darcsweb.cgi 2248 url_request.sort() 2249 cache = Cache(config.cachedir, url_request) 2250 if cache.open(): 2251 # we have a hit, dump and run 2252 cache.dump() cache = <__main__.Cache instance>, cache.open = <bound method Cache.open of <__main__.Cache instance>> /srv/darcsweb/darcsweb.cgi in open(self=<__main__.Cache instance>) 466 pid = str(os.getpid()) 467 fname = self.basedir + '/.' + self.fname + '-' + pid 468 self.file = open(fname, 'w') 469 self.mode = 'w' 470 self = <__main__.Cache instance>, self.file = None, builtin open = <type 'file'>, fname = '/tmp/darcsweb-cache/.3647210cedbbeff551e4ffe8dac1328a00518335-30974' IOError: [Errno 2] No such file or directory: '/tmp/darcsweb-cache/.3647210cedbbeff551e4ffe8dac1328a00518335-30974' args = (2, 'No such file or directory') errno = 2 filename = '/tmp/darcsweb-cache/.3647210cedbbeff551e4ffe8dac1328a00518335-30974' strerror = 'No such file or directory'

2 1

Exporting Haskell Libraries to C Programmers
by Bruce, Joseph R (Joe) 21 Feb '08

21 Feb '08

Hi, I have a Haskell library that I want to make available via FFI to C programmers on my project team. I read this thread (http://thread.gmane.org/gmane.comp.lang.haskell.cafe/21447) which had some interesting ideas, but they seemed unresolved. Or maybe it answers my question but I don't understand it. Is there a way I can package (ghc-)compiled Haskell code into a statically-linked library and not force the C programmers to include headers and libraries that they have no knowledge of and undefine a seemingly endless list of preprocessor symbols (run ghc with the verbose flag and look at the calls to gcc)? Can this process be automated? Thanks, Joe

2 1

Re: a help for install
by Wolfgang Jeltsch 21 Feb '08

21 Feb '08

Am Montag, 18. Februar 2008 19:46 schrieb Carlos Gomez A.: > hi, my name is carlos > > I need information for correct install or > > what are dependencies on ghc ? > > I have a Debian System. Always use your distribution’s packages until they aren’t any or there is good reason not to do so. Try “aptitude install ghc6”. Best wishes, Wolfgang

2 1

Arrows: definition of pure & arr
by Peter Verswyvelen 21 Feb '08

21 Feb '08

After having played with some packages that use arrows, and after having read the very nice "programming with arrows" paper I wanted to build some of my own. Strangely my code did not work, even the simplest function got stuck in an infinite loop or gave a stack overflow. I quickly noticed I made a really stupid mistake, I forget to implement "arr"! However, the compiler did not give a warning on this. So I wandered how it was possible that the Arrow package had a default implementation for something so specific as arr? The code revealed the following: -- | Lift a function to an arrow: you must define either this -- or 'pure'. arr :: (b -> c) -> a b c arr = pure -- | A synonym for 'arr': you must define one or other of them. pure :: (b -> c) -> a b c pure = arr Ah, so the default implementation of arr is pure... and vice versa... This feels like rather incorrect to me, but my feelings are based on imperative background knowledge, so this might be totally correct design in Haskell. Why not force people to implement arr and leave just pure as the synonym? And if pure is really a synonym for arr, what does it do inside the Arrow type class? Does it ever make sense to have a different implementation for arr and pure? Thanks for any help, Peter

7 11

First Call for Papers -- GPCE'08
by Emir Pasalic 20 Feb '08

20 Feb '08

Call for Papers Seventh International Conference on Generative Programming and Component Engineering (GPCE 2008) October 19-23, 2008 Nashville, Tennessee (co-located with OOPSLA 2008) http://www.gpce.org Important Dates: * Submission of abstracts: May 12, 2008 * Submission: May 19, 2008 * Notification: June 30, 2008 * Tutorial and workshop proposals: March 30, 2008 * Tutorial and workshop notification: April 5, 2008 Scope Generative and component approaches are revolutionizing software development similar to how automation and components revolutionized manufacturing. Generative Programming (developing programs that synthesize other programs), Component Engineering (raising the level of modularization and analysis in application design), and Domain-Specific Languages (DSLs) (elevating program specifications to compact domain-specific notations that are easier to write, maintain, and analyze) are key technologies for automating program development. The International Conference on Generative Programming and Component Engineering provides a venue for researchers and practitioners interested in techniques for enhancing the productivity, quality, and time-to-market in software development that stems from deploying components and automating program generation. In addition to exploring cutting-edge techniques for developing generative and component-based software, our goal is to foster further cross-fertilization between the software engineering research community and the programming languages community. Submissions Research papers: 10 pages in SIGPLAN proceedings style (sigplanconf.cls) reporting original research results that contribute to scientific knowledge in the areas listed below (the PC chair can advise on appropriateness). Experience reports: 2 to 4 pages in length in SIGPLAN proceedings style (sigplanconf.cls). We encourage experience reports that provide concrete evidence with regards to the efficacy of generative technologies in industrial applications. Topics GPCE seeks contributions in software engineering and in programming languages related (but not limited) to: * Generative programming o Reuse, meta-programming, partial evaluation, multi-stage and multi-level languages, step-wise refinement, and generic programming o Semantics, type systems, symbolic computation, linking and explicit substitution, in-lining and macros, templates, and program transformation o Runtime code generation, compilation, active libraries, synthesis from specifications, development methods, generation of non-code artifacts, formal methods, and reflection * Generative techniques for o Product-line architectures o Distributed, real-time and embedded systems o Model-driven development and architecture o Resource bounded/safety critical systems. * Component-based software engineering o Reuse, distributed platforms and middleware, distributed systems, evolution, patterns, development methods, deployment and configuration techniques, and formal methods * Integration of generative and component-based approaches * Domain engineering and domain analysis o Domain-specific languages including visual and UML-based DSLs * Separation of concerns o Aspect-oriented and feature-oriented programming, o Intentional programming and multi-dimensional separation of concerns * Industrial applications of the above Experience reports on applications of these techniques to real-world problems are especially encouraged, as are research papers that relate ideas and concepts from several of these topics, or bridge the gap between theory and practice. The program chair is happy to advise on the appropriateness of a particular subject. Submissions must adhere to SIGPLAN's republication policy. Please contact the program chair if you have any questions about how this policy applies to your paper (gpce2008 at gpce.org) Organizers General Chair: Yannis Smaragdakis (University of Oregon) Program Chair: Jeremy Siek (University of Colorado at Boulder) Satellite Chair: Ralf Lammel (Univ. Koblenz-Landau) Publicity Chair: Emir Pasalic (LogicBlox, Inc.) Program Committee David Abrahams (Boost Consulting) Uwe Assmann (Technische Universitat, Dresden) Ira Baxter (Semantic Designs, USA) Martin Bravenboer (Delft Univ. of Tech., The Netherlands) Jacques Carette (McMaster University, Canada) Shigeru Chiba (Tokyo Institute of Technology, Japan) William R. Cook (University of Texas at Austin, USA) Lidia Fuentes (University of Malaga, Spain) Yossi Gil (The Technion, Israel) Aniruddha Gokhale (Vanderbilt University, USA) Mark Grechanik (Accenture Technology Labs, USA) Stanislaw Jarzabek (National University of Singapore) Jaakko Jarvi (Texas A&M Unviersity, USA) Julie Lawall (DIKU, University of Copenhagen, Denmark) Christian Lengauer (University of Passau, Germany) Matthew Marcus (Adobe Systems Inc., USA) Anne-Francoise Le Meur (University of Lille 1, France) Sibylle Schupp (Chalmers University of Technology, Sweden) Peter Sestoft (IT University of Copenhagen, Denmark) Chung-chieh Shan (Rutgers University, USA) Eric Van Wyk (University of Minnesota, USA)

1 0

Re: [Haskell-cafe] Haskell maximum stack depth
by Neil Mitchell 20 Feb '08

20 Feb '08

Hi > ghc uses a pretty conventional stack AFAIK, and it is arbitrarily > limited, but you can change the limit with +RTS options. GHC uses a conventional stack (in that you put stuff at the top, and take it off from the top), but it is not a conventional stack in the way imperative programs work. In an imperative program if you make a function call, a frame gets pushed on the stack. When the function call returns, the frame gets popped off the stack. In Haskell, lazy evaluation makes it massively more confusing. > Also, stack "overflows" are a pretty common cause of program failure > IME, not at all rare. At least, far more common than whatever error > message you get from heap exhaustion (can't even remember the last > time I saw one of those). Yes, I agree. However, in imperative programming stack overflow nearly always means you've exceeded some recursion depth in the program, and should think about refactoring it to use explicit loops. In Haskell, stack overflow is usually a laziness bug. Same error message, completely different causes. In Haskell, the solution to stack overflow is almost never "increase the stack depth", but "fix your laziness leak". To answer the question if Haskell has a "stack depth restriction ... like Java" the answer is no. It has a stack depth restriction, but its absolutely nothing like Java in the way it uses the stack, so you can't compare them. My guess is that Istarex's inner thought might have been along the lines of "in Java if I do too much recursion I get a stack overflow, but Haskell only has recursion, does that mean I get into stack overflows all the time?". I could of course be entirely wrong ;-) Thanks Neil

14 47

build-depends contraints in a .cabal file
by Antoine Latter 19 Feb '08

19 Feb '08

Can I specify an equality constraint in the build-depends field of a .cabal file? This would say that I want one specific version (because all the rest of my packages are compiled against that version and I'm getting type-checking errors trying to install the new package). neither > build-depends: foobar = 3.0.1 or > build-depends: foobar-3.0.1 seem to work. Do I have any choices other than re-compiling everything? Thanks, Antoine

3 2

Arrow combinator names
by Tom Davies 19 Feb '08

19 Feb '08

Are there generally accepted English language names for the arrow combinators? >>> compose? &&& pair? etc...

4 3

Doubting Haskell
by Alan Carter 19 Feb '08

19 Feb '08

Greetings Haskellers, I'm a Haskell newbie, and this post began as a scream for help. Having slept on it I find myself thinking of Simon Peyton-Jones' recent request for good use cases. Perhaps a frustrated - and doubting - newbie can also provide a data point. If my worries are unfounded (and I hope they are), I think it's significant that to me, today, they seem real enough. Please understand that I'm not being negative for the sake of it - rather I'm describing what Haskell looks like from the outside. Let me put it this way. Imagine that two weeks ago my forward-thinking and risk-embracing boss asked me to evaluate Haskell for the upcoming Project X. Further imagine that she ensured I was able to sit in the corner emitting curses for the whole two weeks, and on Monday I have to provide my report. At this point, two weeks in, I would be forced to say that I have no reason to believe that Haskell is useful for real world tasks. ghc is an industrial strength compiler for a toy language. While remarkable claims are made for it, in practice even the experts are often unable to implement the most basic behaviours, and where they are able to implement, they find that their program has become so complex that they are unable to describe or discuss the result. Likely this is a deep problem, not a shallow one. The Haskell community is in denial over this, leading to phenomenal time wasting as one goes round and round in circles playing word games with documentation. This risks a return of the chronic embuggerance that we thought we'd escaped when Vista appeared and the set of people who would have to write Windows device drivers reduced to Hewlett Packard employees, Joanna Rutkowska and criminals. When people enthuse about Haskell, we should run a program called Cat.hs from the haskell.org website, throw fruit at them and laugh. Strong words, but in all honesty I *want* to believe, and if I would make such a report I imagine hundreds if not thousands would say the same thing. I'm hoping I'm wrong about this, and what's actually needed is some work on communication (perhaps from a production programming point of view, which I'd be keen to help with). What got me started with Haskell was the video of an Intel employee holding a Teraflops in his hand. I still remember the very silly September 1991 edition of Scientific American, which asked if a Teraflops would *ever* be built. What a stupid question! Stack up enough VIC20s and eventually you'll get a Teraflops. The question should have been "when". Now it's the size of a CD, and only 80 cores are needed. Unfortunately keeping 80 cores running is tricky. I know this from writing some heavy parallel stuff in the mid-90s. It was all quite clever in it's day. Chuck bloated and unguessable CORBA, do something light with TCP/IP (Beuwolf took that to extremes). Neat linkage like rpcgen gave C, so that I could run fast on an SMP Sequent with 30 cores or on a floorfull of about 70 Sun pizza boxen at night. Unfortunately despite having a nice framework, tracing rays is still hard (the rays and medium were... interesting). Making a problem parallel required a sneaky and dedicated person's sincere skull-sweat. Worse, the solutions so produced had a horrible structural instability about them. Just a small change to the requirement could require a computed value where it wasn't needed before, so that it resulted in big changes to the implementation. The skull-sweating would be needed all over again. (Remember that the big point about objects, which e.g. Booch always emphasized, was that a well chosen set of classes maps well to the domain and so reduces such structural instability.) Even then, it was devilish hard to keep 70 "cores" busy. So watching the Intel guy got my klaxons going. We now need to be able to do parallel with ease. Functional programming just got really important. It's years since I last played with Scheme, but I quickly moved on because I could see the "which Scheme" problem becoming a millstone round everyone's necks outside of research contexts. Ditto Lisp. So Haskell. Grown-up compiler, one standard and (apparently) a decent corpus of example code and tutorials. I might be an imperative programmer, but I do lapse - for example I find it very easy to generate swathes of cross referenced documentation using m4. My head goes kind of weird after a few hours, such that m4 seems sane and it's the rest of the world that's ungainly, so maybe it should be banned like DMT, but I like it. I felt able to enter the functional world. I'll omit the first week of suffering, which I see is a well documented rite of passage. (Although most evaluators will have left the building by the end of week one so it's not helping popularity. Perhaps there could be Squires of the Lambda Calculus who haven't done the vigil, mortification of flesh and so on?) Eventually a 3 page introduction on the O'Reilly website together with a good document called "Haskell for C Programmers" got me to the point where I could access "Yet Another Haskell Tutorial", and I was away... for a bit. After a while I'd written some malformed horrors as answers to exercises, and was telling myself that it's probably just an edge effect - deep within a real Haskell program the ugliness would be invisible, tucked away in Ugly.hs. Then I discovered wxHaskell and got very excited. I really like wxWidgets, and I know it well. If I could play with some Haskell which manipulates wxWidgets I'd progress very quickly! I even have a recent C++ wxWidgets program which was annoying me as I wrote it because of the boilerplate. Great! I can play with type inference and mutter "about bloody time" with a smile on my face. Eventually I got a mix of wxWidgets 2.6.3, wxHaskell from darcs, ghc 6.6 running on my Mac, almost exactly as that permutation was described on the website, and I was off. Within a few hours I had a nice frame, with 10 text controls and legends populating it. It already took less lines than C++, and then I discovered how to bundle all the text controls into a tuple to pass them around, and define some "getters" to access the tuple. My line count shrunk to what it "should" be - that is, something Kolmogorov wouldn't laugh at but is unattainable in C++. I had an onOpen which popped up a dialog and got a filename from the user, with all the properties filled in right. I proved that I could update the values in the text controls from the onOpen. Great. Next, translate the bit that says (pseudocode): if(attempt_file_open) if(attempt_file_read) process That's it. No fancy, complex error messages. Just check the error returns and only proceed if I have something to proceed with. Like grown-ups do. I *will* check my error returns. I have tormented too many newbies to *ever* consider doing anything else. If I cannot check my error returns I will not write the program. This is production programming 101, and I suspect that there's a real issue with priorities between the traditional Haskell community and production programmers. So the time of madness began. I could find examples which did: if(attempt_file_open) attempt_file_read process Which is useless. Other examples did: attempt_file_open if(attempt_file_read) process Which is also useless. So I'm looking through the wxHaskell examples. They're all contrived, using very high level functions to (for example) read a complete image structure from a named file, which as one function had one possible source of errors. I go back to scanning and Googling like crazy. Eventually I notice a bit in "Yet Another Haskell Tutorial" - page 65 - which introduces "bracket", immediately explains that it is useless for my (very common) need, and refers the reader to Section 10 - "Advanced Techniques". The author of this excellent document hasn't yet written Section 10. I wonder why. I pause to examine bracket some more. I really can't tell if the "always" clause gets called if the initialization fails. From the use with file opening it looks like it isn't (or the handle to be closed would be invalid) but that wouldn't help if the initializer had two steps, e.g. called socket(2) and bind(2). This is the kind of thing good production programmers get really het up about. I'm still grovelling through reams of stuff, trying to find out how to open *and* read a file in a grown up way, and I find various programs on haskell.org. There's an implementation of cat(1)! That's the thing! A file concatenator must be able to open *and* read it's file. Eagerly I download it. Curiously there doesn't seem to be any error handling. I compile it and point it at a non-existent file. The program crashes. Horribly. So much for Cat.hs. I feel glad I hadn't been able to cope with the video of Simon Peyton-Jones OSCON talk, because the camera operator kept filming his face while he's gesturing at the specific line of code he's talking about with a pointer! After seeing Cat.hs do essence of FAIL just opening a file, claims that Haskell could serve as a scripting language suitable for the crew of the Black Pearl in yonder corner to use would pain me. Now I'm getting cross and turned off the whole business. I've been here before, grovelling through reams of stuff, trying to find something out while each example is contrived to side-step the problem, half-baked and useless, evasive or referencing non-existent documentation. All I need to make the experience complete is a certain firm's trademarks gratuitously embedded in the text at least once on every line. Then I'd be nauseous by now too. Finally I found an uncommented example with no discussion called Hedi. This seems to be doing exception handling, but what it is doing, how, why, what can raise them, so on and so forth would presumably be covered in the "too complex to describe" bit of "Yet Another Haskell Tutorial". I tried to understand it from first principles, looking at the Type theology for the exceptions and various calls, but while I have the cup of tea I lack the necessary Total Perspective Vortex. I felt no confidence trying to even cut and paste it. So question number one: Please - how do I do this? Somehow I doubt that wrapping the complexity of opening a file *and* reading it in a grown up way and then documenting idioms that use the wrapper would help. If it would, the wrapper and doco would already exist. That implies that the complexity doesn't stack. If I get to the point where I can open a file *and* read it in a grown up way, and then I need to (say) verify a version number from the file: if(attempt_file_open) if(attempt_file_read) if(version_ok) process Would I need to completely restructure my program? I suspect so. But it's worth bringing it up. Question number two: Might wrapping the indescribable complexity of the most basic operations make it possible to publish and discuss some idioms which accomplish them? I'd be quite happy with a voodoo idiom for now. I know someone who (20 years on) still doesn't understand pointers to functions. She still uses qsort(3) by rote, and it works for her. That will do for beginners. My biggest worry is that there's a really bad trade-off going on here. Sure, the structural instability of imperative parallel algorithms can be reduced, but at the cost of adding structural instability to everything else! TANSTAAFL and the lump in the carpet always goes somewhere. I read one chap who complained that in order to add one single line of debug he had to completely restructure his entire program, and then the line count was as big as an imperative language would be. Plus a world more complex I bet. It's this TANSTAAFL that's making me a non-believer. So question number three (rhetorical): What would have happened if Codd and Date had tried to make SQL a general purpose programming language? Sequential file handling would have been impossible for all practical purposes, so no-one would have got the benefits of set theory (oh sorry relational calculus) and our most successful intentional language would have been stillborn. We'd still be using CODASYL. Which leads to question number four: Why not do one job well? Limit parallelism to a single SMP machine where there are no comms to fail and failures which do occur will justify the OS chucking the whole process. Make an interface so that Haskell can be called from C++ or Java, with a simple IDL that can marshall nested structs, list<>s, map<>s and vector<>s in and out. Then we can get on with writing ambitious pure computations with names like sortOutRawCatScanData, tersely and in easily parallelizable ways, like we embed SQL to get certain specialist jobs done. Then when all this was going on, question number five appeared: What the hell are these "lightweight Haskell threads"? Are they some kind of green threads running non-preemptively inside a single OS thread? Are they OS threads that could run concurrently on multi-core hardware? If they are green threads (and it sounds like they are) then this is all an academic exercise which has no production application yet. I'm still hoping that this is solvable. That the instinctive priorities of production programmers are just different to those of researchers, and in fact it *is* possible to open a file *and* read it, checking *both* error returns, without being driven insane. If so, I sincerely suggest an example or two, like the small but well formed programs in K&R, Stroustrup or Gosling saying things like: if((fp = fopen(...)) != NULL) { if(fgets(...) != NULL) { printf(...); } fclose(...) } Best wishes - and still hoping I'm wrong after all Alan Carter -- ... the PA system was moaning unctuously, like a lady hippopotamus reading A. E. Housman ..." -- James Blish, "They Shall Have Stars"

20 30

naming a data structure for weighted random selection without replacement
by Stuart Cook 19 Feb '08

19 Feb '08

A while ago I wrote a little data structure that allows weighted random selection-without-replacement from a collection of values in O(log n) time.[1] I'm now in the process of packaging it up for Hackage, but I'm looking for good names for both the type and its operations. The name I have at the moment is "Pool", which I'm reasonably happy with, but I wanted to see if I could find anything better. Asking on #haskell got me a few responses: * Hat (cute, but conflicts with the program tracer) * Bag (already way too overloaded) * Bucket (not as suggestive as Pool) I have three main operations: * "pull" selects a random element, returning it and the remainder, but fails if the pool is empty * "pullN" selects /n/ distinct elements, returning them and the remainder, but fails if the pool has too few elements * "takeN" selects up to /n/ distinct elements, returning them and the remainder, but returns no more elements than could be found in the pool (analogous to Data.List.take) Any suggestions? Stuart [1] Actually I delegated most of the work to the data-structure-in-a-can that is Data.FingerTree, but that's another story.

6 6

Working with multiple time zones
by Dave Hinton 19 Feb '08

19 Feb '08

(This is a toy program to demonstrate only the part of my real program that I'm having trouble with.) Suppose I'm writing a program to print the current time in various time zones. The time zones are to be given symbolically on the command line in the form "Europe/London" or "America/New_York". The idea is that either the operating system or the runtime library keeps track of what time zones different places are in, and when they are on summer time, so that my code doesn't have to worry about it. Haskell has a TimeZone type in Data.Time.LocalTime, but it only represents constant offsets from UTC — doesn't encode rules for when the clocks change. And there doesn't seem to be any way of looking up the time zone for a locality. Data.Time.LocalTime has the getTimeZone function, which returns the time zone for a given UTC time on the local machine — this takes care of summer time, but by itself only works for the local machine's locality. If I was writing this program in C, I'd get round this by setting the TZ environment variable to the locality I was interested in before doing time conversions. $ cat cnow.c #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> void outTime (time_t utc, char *tzName) { char env[100] = "TZ="; strcat (env, tzName); putenv (env); printf ("%s\t%s", tzName, asctime (localtime (&utc))); } int main (int argc, char **argv) { int i; time_t utc = time (NULL); for (i = 1; i < argc; ++i) outTime (utc, argv[i]); return 0; } $ gcc cnow.c -o cnow $ ./cnow Europe/Paris Europe/Moscow Europe/London Europe/Paris Sat Feb 16 23:57:22 2008 Europe/Moscow Sun Feb 17 01:57:22 2008 Europe/London Sat Feb 16 22:57:22 2008 So far, so good. Here's the equivalent in Haskell: $ cat hsnow.hs import Data.Time import Data.Time.LocalTime import System.Environment import System.Posix.Env outTime utc env = do putEnv ("TZ=" ++ env) tz <- getTimeZone utc putStrLn (env ++ "\t" ++ show (utcToLocalTime tz utc)) main = do utc <- getCurrentTime mapM_ (outTime utc) =<< getArgs $ ghc --make hsnow.hs -o hsnow [1 of 1] Compiling Main ( hsnow.hs, hsnow.o ) Linking hsnow ... $ ./hsnow Europe/Paris Europe/Moscow Europe/London Europe/Paris 2008-02-16 23:59:11.776151 Europe/Moscow 2008-02-16 23:59:11.776151 Europe/London 2008-02-16 23:59:11.776151 $ ./hsnow Europe/Moscow Europe/London Europe/Paris Europe/Moscow 2008-02-17 01:59:28.617711 Europe/London 2008-02-17 01:59:28.617711 Europe/Paris 2008-02-17 01:59:28.617711 Not good. GHC's runtime library seems to be taking the value of TZ the first time it is called as gospel, and ignoring subsequent changes to TZ. So: 1. Is this a bug in GHC's Data.Time.LocalTime.getTimeZone? 2. If GHC's implementation is working as designed, how do I translate the C program above into Haskell? I'm running on Debian stable, with GHC 6.6. Thanks.

8 9

Haskell Thrift bindings
by Dave Tapley 19 Feb '08

19 Feb '08

Hi everyone, This is regarding Thrift, "a software framework for scalable cross-language services development"(1) Present in the release tarball there is some source for Haskell but no sign of a tutorial or any sample code. I'm just picking through but as a long shot does anyone have examples they could send me? I'm also looking to put together a page on haskellwiki once I'm up and running. The project seems like a fine way to sneak Haskell into existing project ;) Cheers, Dave (1) http://developers.facebook.com/thrift/

1 0

More powerful error handling
by Philippa Cowderoy 18 Feb '08

18 Feb '08

For a while I've been meaning to propose something along the lines of this class: class (MonadError m e, MonadError m' e') => MonadErrorRelated m e m' e' | m -> e, m' -> e', m e' -> m' where catch' :: m a -> (e -> m' a) -> m' a rethrow :: m a -> (e -> e') -> m' a with an example instance being: instance (Error e, Error e') => MonadErrorRelated (Either e) e (Either e') e' where catch' (Right v) _ = Right v catch' (Left e) h = h e rethrow c ef = catch' c (throw . ef) (yep, that definition of rethrow would make a sensible default and there's a default catch' in terms of rethrow too) The nicest use would be for converting between a more specific error type and a more general one that handles a wider range of errors - enabling us to keep tighter track of which errors are possible in a given piece of code. Bonus points for using it together with polymorphic variants where rethrow becomes rather trivial. The following two functions or close variants might also be useful: catchMaybe :: (MonadError m ()) => Maybe a -> m a catchMaybe Nothing = throwError () catchMaybe (Just a) = return a catchEither :: (MonadError m e) => Either e a -> m a catchEither (Left err) = throwError err catchEither (Right a) = return a No doubt there are some names that could use tweaking. As far as I'm concerned you can count me in the camp of people that resent the existing MonadError instances all requiring an Error instance too, it makes things messier when you have access to something like this. But I guess that's because fail is begging for the following definition: fail = fail -- fail is made of fail -- flippa(a)flippac.org There is no magic bullet. There are, however, plenty of bullets that magically home in on feet when not used in exactly the right circumstances.

2 1

problem with collection (container) class
by Leandro Demarco Vedelago 18 Feb '08

18 Feb '08

Hi! I'm pretty (not to say very) new to haskell and i've to create a new class named container that includes types that hold other values, more specific, i have "created" this two types: data Abb a b = Branch a b (Abb a b) (Abb a b) | Leaf and data ListAssoc a b = Node a b (ListAssoc a b) | Empty and implemented some common functions (add, search, delete, empty,etc). So when I was asked to create this new class I crashed against a big problem, or at least for me. My first attempt was: class Container c where empty :: c but when I had to implement "add" I tried add :: c -> a -> b -> c although I was almost sure that it wouldn't work, so I realized that I had to give Container not one but three parameters, the container and the types of values that the container saved so I started searching and I found similar cases, but the difference iis that in this cases the class was defined as follows: class Container c e | c->e where empty :: c insert :: c -> e -> c member :: c -> e -> Bool but my particular problem here is that the types I designed hold two values of different type and these holds just one value. Besides I knew nothing about functional dependency used in here and I keep knowing almost nothing about them, but I tried something like this: class Container c a b |c -> a, c -> b where empty :: c add :: c -> a -> c search :: c -> a -> Maybe b del :: c -> a -> c toListPair :: c -> [(a,b)] instance Container Abb a b where empty = Leaf add Leaf x y = Branch x y Leaf Leaf add arb@(Branch ni nd ri rd) x y |x == ni = arb |x > ni = Branch ni nd ri (add rd x y) |otherwise = Branch ni nd (add ri x y) rd search Leaf x = Nothing search (Branch ni nd ri rd) x |x == ni = Just nd |x > ni = search rd x |x < ni = search ri x but when I try to load it in WinHugs I get the following error message: - Instance is more general than a dependency allows *** Instance : Container Abb a b *** For class : Container a b c *** Under dependency : a -> b and as I have stated above my knowledge about dependencies is almost null, not to say null, so I don´t even have an idea where the error is. A suggestion that I've received was to change the type of Abb for data Abb (a,b) = Branch a b (Abb (a,b)) (Abb (a,b)) | Leaf and declare container class with just two parameters like I found in all pages I visited. I have not tried this yet, as I still have hope that what I intend to do is possible. Well if you have any suggestions I'd appreciate you send it to me and sorry for bothering you and my english, but i'm "spanish-speaker".

4 4

Designing DSL with explicit sharing [was: I love purity, but it's killing me]
by oleg＠okmij.org 18 Feb '08

18 Feb '08

Matthew Naylor wrote: > it's not immediately clear (to me at least) how efficient your method > will be in "practice". Any method based on common sub-expression > elimination surely must inspect every node in the flattened graph. In > the worst case, an acyclic graph containing n nodes could have 2^n > nodes when flattened to a tree: > > tricky 0 = constant 0 > tricky d = add g g > where > g = tricky (d-1) It should work quite well in practice, as demonstrated below. Once our DSL is extended with a let form (so the user can declare the intention to share results of computations rather than computations themselves), tricky code becomes trivial. The code remains declarative, safe and pure, and, save for the (cosmetic) lack of the monomorphism restriction, Haskell98. The well-commented code is available at http://okmij.org/ftp/Haskell/DSLSharing.hs First a few comments on the tricky code. It is true that (absent programmer's proclamations and code structuring forms) a complete method of common sub-expression elimination must inspect every sub-expression in the program. That inspection must include at least one comparison of a node with some other nodes. As I understand the original problem had less to do with the number of comparison but more to do with the cost of a single comparison. In an impure language, we can use constant-time physical equality. It is usually provided natively as pointer comparison, and can be trivially emulated via mutation. The original poster used pure Haskell and the following representation for the program graph: data Expression = Add Expression Expression | Sub Expression Expression | Variable String | Constant Int deriving Eq Here, the derived equality operation, albeit pure, no longer takes constant time. Comparing nodes near the root of a deep tree really takes a while. As the previous message on DSL with sharing showed, one can do common sub-expression elimination and the conversion of the program tree to a DAG using a constant-time node equality operation, without sacrificing purity. The tricky function is a metaprogram that builds a large DSL program: (tricky 12) yields a single DSL expression with 8191 nodes. Such humongous expressions with thousands of components are unlikely to be written by human programmers (although can be easily generated). Many compilers will choke if we submit a program with one large expression. (Incidentally, the previously posted code converts the tree (tricky 12) to a 12-node DAG in 0.25 secs on 1GHz Pentium). The reason we can compile much larger projects is because we structure them, into compilation units, functions, let-blocks. The structure gives the common sub-expression eliminator and other optimizer phases much needed hints and so significantly limits the search space. For example, hardly any compiler searches for common sub-expressions across compilation units. More importantly for us here, forms like let-expressions let the programmer declare that the results of certain computations be shared. Although the tricky code also contains a let-expression (masqueraded as 'where'), the sharing there occurs at the meta-level and benefits the generator rather than the generated program. We share code generators rather than the generated code. The importance of placing 'let' in the right phase has been extensively discussed in http://www.cs.rice.edu/~taha/publications/conference/pepm06.pdf also in the context of a DSL (for dynamic programming). In our case, we need to give our DSL programmer a way to state their intention on sharing results of DSL computations. The programmer declares certain expressions common, and thus greatly helps the compiler as well as human readers of the code. As Chung-chieh Shan has pointed out, we need to introduce a "let" construct in the _embedded_ language. Since our DSL already has (concrete) variables with string names, we can extend our language thusly: let_ "v1" (add (constant 1) (variable "x)) (add (variable v1") (variable "v1")) We chose a different way: higher-order abstract syntax. We use variables of the metalanguage (that is, Haskell) as let-bound variables. Our language is now defined as > class Exp repr where > constant :: Int -> repr Int > variable :: String -> repr Int > add :: repr Int -> repr Int -> repr Int > sub :: repr Int -> repr Int -> repr Int > let_ :: repr a -> (repr a -> repr b) -> repr b -- like flip ($) Here are simple programs in our language > a = add (constant 10) (variable "i1") > b = sub (variable "i2") (constant 2) > c = add a b > d = add c c > e = add d d -- "e" now as 16 leaf nodes. > e' = let_ d (\x -> add x x) The programs (e) and (e') evaluate to the same integer given the same environment for "i1" and "i2". The two programs differ in how sharing is declared. The program (e) uses the identifier (d) twice; even if GHC shares the corresponding expressions rather than copies them (a Haskell system is not obliged to share anything: sharing is not observable in Haskell98), what GHC shares are metalanguage computations. Although the metalanguage (Haskell) is pure, the object language does not have to be. Indeed, the common-subexpression elimination, when considered as an evaluation of an object expression, is an impure evaluation. The same object expression may give, in different contexts, different results (that is, compile to different assembly code). In the case of (e'), we explicitly stated that "d" is a common sub-expression. It must be executed once, with the results shared. The difference is easy to see if we print e and e': *DSLSharing> test_showe "10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2" *DSLSharing> test_showe' "let v0 = 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 in v0 + v0" Higher-order syntax for let_ (see e') seems better than that based on concrete variable names. As test-showe' demonstrates, we can easily convert from higher-order abstract to the concrete syntax. The converse is much more cumbersome. We easily extend the previously written common sub-expression eliminator by adding the clause for let_ > instance Exp A where > ... > let_ e f = A(do > x <- unA e > unA $ f (A (return x))) And that is it. We can write the tricky function with the explicit sharing: > tricky' 0 = constant 0 > tricky' d = let_ (tricky' (d-1)) (\g -> add g g) > > test_tricky' n = runState (unA (tricky' n)) exmap0 *DSLSharing> test_tricky' 12 (AAdd 12, ExpMaps {hashcnt = 13, ctmap = fromList [(0,0)], vrmap = fromList [], admap = fromList [(1,(AConst 0,AConst 0)),(2,(AAdd 1,AAdd 1)), (3,(AAdd 2,AAdd 2)),(4,(AAdd 3,AAdd 3)),(5,(AAdd 4,AAdd 4)), (6,(AAdd 5,AAdd 5)),(7,(AAdd 6,AAdd 6)),(8,(AAdd 7,AAdd 7)), (9,(AAdd 8,AAdd 8)),(10,(AAdd 9,AAdd 9)),(11,(AAdd 10,AAdd 10)), (12,(AAdd 11,AAdd 11))], sumap = fromList []}) (0.01 secs, 0 bytes) Indeed it takes negligible time. In fact, test_tricky' 12 takes (0.01 secs, 561860 bytes) test_tricky' 100 takes (0.03 secs, 1444888 bytes) If the DAG corresponding to (test_tricky' 100) were converted to a tree, it would have had 2^101 -1 nodes (which is more than 10^31).

5 4

Re: [Haskell-cafe] Designing a Parser
by PR Stanley 18 Feb '08

18 Feb '08

Actually, I haven't sent this question to the list before. So you're in no danger of repeating yourself. Thanks for your kind reply anyway Paul At 07:03 17/02/2008, you wrote: >On Feb 17, 2008 6:20 AM, PR Stanley <prstanley(a)ntlworld.com> wrote: > > I can't think of an elegant pattern for the last function. I've > > already tried set comprehension. However, something tells me that the > > answer may lie in a complex recursive pattern. I'm not afraid of > > complex solutions but I naturally see them as an easy way out. It's > > those clear simple patterns that separate men from mice. :-) I'd be > > grateful for any advice on this and indeed my approach as a whole. If > > you think I'm on the wrong path from the start feel free to let me > > know. I'm not asking for the answer. I'd like to work that out by > > myself although some guidance would be most appreciated. > >Yes, I definitely think you're on the wrong path from the start. In >high school when I was learning C++ I wrote an arithmetic expression >parser in something like this fashion. I scanned the input for the >first opening bracket, then I walked forward to the matching closing >bracket and extracted the subexpression and evaluated it. > >The approach turned out to be both complicated and inefficient. I >think the biggest problem was that it didn't scale well with >implementation complexity; eg. to add support for prefix functions >like sin() was almost impossible. Think about how you would go about >doing such things using your approach. > >I think I've seen you ask questions relating to this on the list >before, and at the risk of repeating others, I suggest the ReadS in >the Haskell Prelude. You get the benefit of it being a clean, >top-down solution as well as the benefit of having a lot of primitive >Haskell types already implemented for you (such as Integers). > >I'll describe the approach again, describing the combinators, and then >afterward showing how you might use them to accomplish this problem. >I'll leave the details up to you, since you can learn a lot by >implementing combinator libraries like this. > >First, you build a bunch of functions which are "parsers". A "parser" >is just a function of type String -> [(a,String)] for some type 'a'; >that is, it takes a string and returns a list of "parses", where a >parse is the value parsed paired with the remainder of the string. So >if you have a function: > > parseInt :: String -> [(Int,String)] > >Then you can expect this result: > > parseInt "123 hello world" = [(123, " hello world")] > >Or maybe even: > > parseInt "123 hello world" = [(123, " hello world"), (12, "3 hello >world"), (1, "23 hello world")] > >But that latter behavior is not recommended in this case (i.e. it is >advisable force int parsing to be greedy). > >Then to combine parsers you can use some combination operations: > > sequenceParsers :: (String -> [(a,String)]) -> (a -> String -> >[(b, String)]) -> String -> [(b,String)] > >That one may be easier to see if you use the built-in type synonym >ReadS a = String -> [(a, String)]: > > sequenceParsers :: ReadS a -> (a -> ReadS b) -> ReadsB > >The second argument here is a function, because we have already parsed >the first argument and know its value, so the second argument ought to >be able to use it. We can also write: > > alternateParsers :: ReadS a -> ReadS a -> ReadS a > >Which gives all valid parses that the first one recognizes >concatenated with all valid parsers that the second one recognizes. > >Implementation of these combinators is left to you. Since the types >of these functions are quite general, you can use a type-directed >approach (i.e. if your implementation uses all available data and it >typechecks, it's probably correct). > >Now that you have these, how do you use them to actually parse >something? Let's parse simple logical expressions. First we need a >data structure to parse into: > > data Exp > = Variable String > | AndExp Exp Exp > | OrExp Exp Exp > >Let's do it with a top down coding strategy: write a function to >parse an expression using whatever helper functions we need but >haven't written yet :-) > > parseExp :: ReadS Exp > parseExp = parseAnyOf [ parseVariable, parseAndExp, parseOrExp ] > >Where we haven't written parseAnyOf yet. Write that inductively on the list: > > parseAnyOf :: [ReadS a] -> ReadS a > parseAnyOf [] = \input -> [] > parseAnyOf (p:ps) = alternateParsers p (parseAnyOf ps) > >And jump in to the next thing we haven't written, parseVariable: > > parseVariable :: ReadS Exp > parseVariable = mapParser Variable parseString > >mapParser doesn't actually parse anything, it just parses whatever its >argument does and applies a function to the result: > > mapParser :: (a -> b) -> ReadS a -> ReadS b > mapParser :: (a -> b) -> (String -> [(a,String)]) -> String -> > [(b,String)] > >I rewrote the type signature to help guide your implementation. > >That should get you started, and show you how the approach usually >goes. You seem to already get the idea of writing many small >functions and composing them together. This is the same idea, except >the functions are abstracting the problem more. > >Luke

2 1

GHC + interactive input/output
by Jonathan Cast 17 Feb '08

17 Feb '08

$ cat > foo.c #include <stdio.h> int main() { char s[1024]; printf("gsi> "); gets(s); printf("%s\n", s); return 0; } $ make foo cc gsi.c -o gsi $ ./foo warning: this program uses gets(), which is unsafe. gsi> hello hello $ cat > foo.hs main = do putStr "gsi> " s <- getLine putStrLn s $ ghc foo.hs -o foo $ ./foo hello gsi> hello (This is on MacOS X). It strikes me that GHC is being extraordinarily unhelpful here. Is there anyone on the planet who ever actually wants this behavior? jcc

13 25

ANN: winerror-0.1
by Felix Martini 17 Feb '08

17 Feb '08

This is a small package for error handling when making foreign calls to the Windows API. The functions are similar to those in Foreign.C.Error, e.g. throwWinErrorIf corresponds to throwErrnoIf. Dynamic io errors are thrown with GHC so the catchWinError function can catch specific Windows error codes and handle them. Regards, Felix

1 0

Designing a Parser
by PR Stanley 17 Feb '08

17 Feb '08

Hi friends I'm in the process of designing a series of functions which you might collectively call a parser. The idea is to evaluate an input string for a proof software. So a typical input string would be something like "(P & Q) -> q". There are a number of things to consider here, for example, does the string belong to the domain which is a subset of the 7-bit ASCII table, starting from 32 and ending at 126. Then you need to remove all space characters to make things a bit simpler. Next we find out if the logical sentnece is bracketted. I start this by looking for a bracket in the string. If true then I isolate the brackets into a new set in order to spot any odd ones. Here is what I've done so far: domain :: [Char] domain = [x | x <- ascii7, x >= ' ' && x <= '~'] where ascii7 = ['\0'..'\127'] -- a legal input character is a member of domain. isInDomain :: Char -> Bool isInDomain x = any (==x) domain -- a legal input string is a subset of domain. isSubset :: [Char] -> Bool isSubset input = all isInDomain input -- delete spaces for easier parsing. noSpace :: [Char] -> [Char] noSpace input = [x | x <- input, x /= space] where space = ' ' -- set of brackets brackets = ['(', ')', '[', ']', '{', '}'] -- Are there any brackets in input? hasBrackets :: [Char] -> Bool hasBrackets input = or [True | x <- input, any (==x) brackets] -- filter all brackets into a subset. getBrackets :: [Char] -> [Char] getBrackets input = [x | x <- input, any (==x) brackets] -- What are matching brackets? areMatched :: Char -> Char -> Bool areMatched '(' ')' = True areMatched '[' ']' = True areMatched '{' '}' = True areMatched _ _ = False -- Can all the brackets in input be paired up? allMatched :: [Char] -> Bool I can't think of an elegant pattern for the last function. I've already tried set comprehension. However, something tells me that the answer may lie in a complex recursive pattern. I'm not afraid of complex solutions but I naturally see them as an easy way out. It's those clear simple patterns that separate men from mice. :-) I'd be grateful for any advice on this and indeed my approach as a whole. If you think I'm on the wrong path from the start feel free to let me know. I'm not asking for the answer. I'd like to work that out by myself although some guidance would be most appreciated. Thanks, Paul

2 1

GHC strange behavior
by Ruslan Evdokimov 17 Feb '08

17 Feb '08

Hi, all! I have strange GHC behavior. Consider the code: import Control.Parallel main = print (o `par` (fromInteger e) / (fromInteger o)) where [e,o] = map sum $ map (`filter` numbers) [even, odd] numbers = [1..10000000] When it compiled without threaded it has 19068 ms to run, 396 Mb total memory in use and %GC time 88.2%, the same with -threaded and +RTS -N1, but with +RTS -N2 it takes only 3806 ms to run, 3 Mb total memory in use and %GC time 8.1%. Why it so? It's a bug or I missed something? I test it on dual-core Athlon X2 4200+ 2Gb running 64bit Gentoo system. gcc 4.2.2 and ghc 6.8.2. -- Ruslan

4 8

Haskell project support and analysis on ohloh
by Don Stewart 17 Feb '08

17 Feb '08

Recently ohloh.net added support for analysing haskell code. You can see a range of Haskell projects analysed on ohloh here: http://www.ohloh.net/projects/search?q=haskell Including: http://www.ohloh.net/projects/11789?p=nhc98 http://www.ohloh.net/projects/6869?p=xmonad http://www.ohloh.net/projects/4078?p=HUGS http://www.ohloh.net/projects/6949?p=yi http://www.ohloh.net/projects/10496?p=bytestring http://www.ohloh.net/projects/11766?p=parsec http://www.ohloh.net/projects/11779?p=mtl http://www.ohloh.net/projects/11729?p=binary http://www.ohloh.net/projects/11769?p=X11 http://www.ohloh.net/projects/11790?p=array Which gives rise to some fun 'reports' (and also helps non-Haskell people notice that there are lots of Haskell projects, and developers with experience): xmonad: " Over the past twelve months, 34 developers contributed new code to xmonad. This is one of the largest open-source teams in the world, and is in the top 2% of all project teams on Ohloh. " nhc98: "nhc has a mature, well established code base. The first lines of source code were added to nhc98 in 1999. This is a relatively long time for an open source project to stay active, and can be a very good sign. A long source control history like this one shows that the project has enough merit to hold contributors's interest for a long time. It might indicate a mature and relatively bug-free code base, and can be a sign of an organized, dedicated development team. " Now, they don't support analysing darcs repos, but the do support git, and with darcs-to-git and darcs2git I've been able to (slowly) get a bunch of repos into git form. You can find the git conversions here, if you're interested: http://www.cse.unsw.edu.au/~dons/git/ (git clone http://www.cse.unsw.edu.au/~dons/git/parsec for example). GHC, base and lambdabot are still in the process of conversion. If you want to do your own conversions, I suggest trying darcs2git first, which is very fast. If that doesn't suceed, try darcs-to-git, which is *much* slower (damn ruby), but seems to be more robust. You can then register the resulting git repo for analysis. The global language statistics, and individual Haskell statistics will update in the next few hours, I suspect. http://www.ohloh.net/languages/38 Though at the time of writing they appear out of date. Happy hacking. -- Don

1 0

Help with error
by Jeff φ 16 Feb '08

16 Feb '08

Hello, I get an error message on the code below with GHC. I can't figure out how to get rid of the error. I'd appreciate suggestions on how to fix this. (BTW, the code may look overly combersome because I stripped out anything unnecessary to demonstrate the error.) {-# OPTIONS_GHC -fglasgow-exts -fbreak-on-exception -fallow-undecidable-instances #-} import qualified Prelude import Prelude import Data.Array.IArray class Sequence seq where slength :: (seq e) -> Int snull :: (seq e) -> Bool shead :: (seq e) -> e stail :: (seq e) -> (seq e) instance Sequence [] where slength = length snull = null shead = head stail = tail class From_seq t where from_seq :: (Sequence seq) => (seq e) -> (t e) instance From_seq [] where from_seq seq | snull seq = [] | otherwise = (shead seq) : (from_seq (stail seq)) from_seq' seq | snull seq = (listArray (0,-1) []) | otherwise = listArray (0,fromIntegral (slength seq) -1) (from_seq seq) {- When I uncomment this out, I get the error messages: Error.hs:41:19: Could not deduce (IArray a e) from the context (From_seq (a i), Ix i, Num i, IArray a e1, Sequence seq) arising from a use of `from_seq'' at Error.hs:41:19-31 instance (Ix i, Num i, IArray a e) => From_seq (a i) where from_seq seq = from_seq' seq -} When I load the module above, I can evaluate the folloing in GHCI *Main> from_seq' [0..5] :: Array Int Double array (0,5) [(0,0.0),(1,1.0),(2,2.0),(3,3.0),(4,4.0),(5,5.0)] But, I'd like to do this with the From_seq class. If anyone has suggestions, I'd be grateful. Thanks, Jeff

2 2

*** JOB OFFER *** related to realtime 3D graphics, animation and reactive content
by Peter Verswyvelen 16 Feb '08

16 Feb '08

<http://www.anygma.com/> Anygma is a startup company focusing on generating easy-to-use tools for creating audio-visual 2D/3D content, in the area of entertainment, media, corporate communication and the internet. <http://www.anygma.com/> Anygma has recently raised new capital in order to fund the development of a new platform targeted towards artists and designers for generating procedural and reactive geometry, animations and games. We are looking for talented and passionate computer scientists and software engineers to help us design and implement a prototype of this platform. If you are interested in applying Haskell, OpenGL, and some C/C++, to create such a platform, feel free to apply for the job by sending an email to <mailto://peter%3CAT%3Enazooka%3CDOT%3Ecom> peter AT nazooka DOT com. More information about the job offer can be found <http://www.anygma.com/JobOfferA.html> here. Thank you, Peter Verswyvelen, Software Architect, www.anygma.com <http://www.anygma.com/> PS: This job offer was already placed in the Haskell Café a while ago, but apparently many Haskellers did not notice it, so heres take#2

2 1

Re: [Haskell] Lemmas about type functions
by Ryan Ingram 16 Feb '08

16 Feb '08

[moved to haskell-cafe] Hmm, there's a problem here. Since type functions are open, it's not actually true that (forall ts. Cat ts () = ts), because someone could add, for example type instance Cat [a] () = [(a,a)] which makes the lemma no longer true. What you are doing in cat_nil is not proving that Cat ts () = ts, but rather that the form of ts is a particular form which makes that theorem hold, in particular, for all types ts of the form ts = (t1, (t2, ..., (tN, ()) ... )) Cat ts () = ts So for your lemma to hold, you need a new judgement "Valid ts": class Valid ts where cat_nil :: Equiv (Cat ts ()) ts -- other lemmas here instance Valid () where cat_nil = Equiv instance Valid x => Valid (a, x) where cat_nil = case (cat_nil :: Equiv (Cat x ()) x) of Equiv -> Equiv coerce :: forall f ts. Valid ts => f (Cat ts ()) -> f ts coerce x = case (cat_nil :: Equiv (Cat ts ()) ts) of Equiv -> x Also, I'm not sure if GHC can currently optimize away cat_nil; it's clear by construction that cat_nil is total, but if the compiler can't detect that it needs to run and make sure it returns Equiv and not _|_. Otherwise you get an unsound result: (given the type instance above) instance Valid [a] where cat_nil = cat_nil Oleg has pointed out this problem with GADTs as type witnesses here: http://okmij.org/ftp/Haskell/GADT-problem.hs -- ryan On 2/15/08, Ryan Ingram <ryani.spam(a)gmail.com> wrote: > I am pretty sure that this doesn't exist, but it's quite interesting. > I've submitted a feature request here: > > http://hackage.haskell.org/trac/ghc/ticket/2101 > > On 2/15/08, Louis-Julien Guillemette <guillelj(a)iro.umontreal.ca> wrote: > > Hi all, > > > > I've been using GHC's type families somewhat extensively in my > > type-preserving compiler (BTW, they work great), and quite often I > > come across the need to prove lemmas about those functions. As far as > > I understand there's currently no way to handle such lemmas purely at > > the type level, and I have to encode them as term-level functions. > > > > I wonder if I'm missing something, or otherwise if there are plans to > > provide some way to do this kind of type-level reasoning. > > > > Here's a simple example. > > > > I encode (de Bruijn) type contexts as lists of types of this form: > > > > (t0, (t1, (... , ()...))) > > > > I sometimes concatenate type contexts, and need a lemma stating that > > appending an empty context leaves it unchanged (ts ++ [] == ts). > > > > type family Cat ts0 ts > > type instance Cat () ts' = ts' > > type instance Cat (s, ts) ts' = (s, Cat ts ts') > > > > That is, I need to coerce: > > > > Exp (Cat ts ()) > > > > into: > > > > Exp ts > > > > The way I presently do it is through a term-level function that > > produces a witness that the two types are equivalent, like this: > > > > data Equiv s t where > > Equiv :: (s ~ t) => Equiv s t > > > > cat_nil :: EnvRep ts -> Equiv (Cat ts ()) ts > > cat_nil R0 = Equiv > > cat_nil (Rs _ ts_r) = case cat_nil ts_r of Equiv -> Equiv > > > > coerce :: EnvRep ts -> Exp (Cat ts ()) -> Exp ts > > coerce ts_r e = case cat_nil ts_r of Equiv -> e > > > > > > Louis > > > > _______________________________________________ > > Haskell mailing list > > Haskell(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell > > >

1 0

set terminology
by PR Stanley 16 Feb '08

16 Feb '08

Hi domain, source --- are the two different things? I'm sure I read somewhere that the source \subseteq domain in mappings. The same was said about range and target -- target \subseteq range. Any ideas? Thanks, Paul

2 2

ANN: two new packages: carray, fft
by Jed Brown 16 Feb '08

16 Feb '08

Hopefully these are mature enough to be generally useful. I would appreciate any comments regarding the interface. The FFTW API is not particularly nice for building a pure interface on. Some of the transforms could be made slightly faster at the expense of a much nastier interface, but unless someone needs the extra few percent, or is pushing the memory limits on their machine, I'm not inclined to expose the underlying nastiness. * carray A C-compatible array library. Provides both an immutable and mutable (in the IO monad) interface. Includes utilities for multi-dimensional arrays, slicing and norms. Memory is 16-byte aligned by default to enable use of SIMD instructions. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/carray * fft Bindings to the FFTW library. Provides high performance discrete fourier transforms in arbitrary dimensions. Include transforms of complex data, real data, and real to real transforms. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/fft Jed

3 5

Re: [Haskell-cafe] fast integer base-2 log function?
by Thorkil Naur 16 Feb '08

16 Feb '08

Hello, If the standard libraries provide such a function, I haven't found it. I must admit that I haven't studied your code in detail. I usually do as follows for integer logarithms, shamelessly stolen from the Haskell report: > -- Integer log base (c.f. Haskell report 14.4): > > imLog :: Integer->Integer->Integer > imLog b x > = if x < b then > 0 > else > let > l = 2 * imLog (b*b) x > doDiv x l = if x < b then l else doDiv (x`div`b) (l+1) > in > doDiv (x`div`(b^l)) l Best regards Thorkil On Monday 11 February 2008 07:15, Uwe Hollerbach wrote: > Hello, haskellers, > > Is there a fast integer base-2 log function anywhere in the standard > libraries? I wandered through the index, but didn't find anything that > looked right. I need something that's more robust than logBase, it > needs to handle numbers with a few to many thousands of digits. I > found a thread from a couple of years ago that suggested there was no > such routine, and that simply doing "length (show n)" might be the > best. That seems kind of... less than elegant. I've come up with a > routine, shown below, that seems reasonably fast (a few seconds of CPU > time for a million-bit number, likely adequate for my purposes), but > it seems that something with privileged access to the innards of an > Integer ought to be even much faster -- it's just a simple walk along > a list (array?) after all. Any pointers? Thanks! > > Uwe > > > powi :: Integer -> Integer -> Integer > > powi b e | e == 0 = 1 > > | e < 0 = error "negative exponent in powi" > > | even e = powi (b*b) (e `quot` 2) > > | otherwise = b * (powi b (e - 1)) > > > ilog2 :: Integer -> Integer > > ilog2 n | n < 0 = ilog2 (- n) > > | n < 2 = 1 > > | otherwise = up n (1 :: Integer) > > where up n a = if n < (powi 2 a) > > then bin (quot a 2) a > > else up n (2*a) > > bin lo hi = if (hi - lo) <= 1 > > then hi > > else let av = quot (lo + hi) 2 > > in if n < (powi 2 av) > > then bin lo av > > else bin av hi > > (This was all properly aligned when I cut'n'pasted; proportional fonts > might be messing it up here.) > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

4 5

fast integer base-2 log function?
by Uwe Hollerbach 15 Feb '08

15 Feb '08

Hello, haskellers, Is there a fast integer base-2 log function anywhere in the standard libraries? I wandered through the index, but didn't find anything that looked right. I need something that's more robust than logBase, it needs to handle numbers with a few to many thousands of digits. I found a thread from a couple of years ago that suggested there was no such routine, and that simply doing "length (show n)" might be the best. That seems kind of... less than elegant. I've come up with a routine, shown below, that seems reasonably fast (a few seconds of CPU time for a million-bit number, likely adequate for my purposes), but it seems that something with privileged access to the innards of an Integer ought to be even much faster -- it's just a simple walk along a list (array?) after all. Any pointers? Thanks! Uwe > powi :: Integer -> Integer -> Integer > powi b e | e == 0 = 1 > | e < 0 = error "negative exponent in powi" > | even e = powi (b*b) (e `quot` 2) > | otherwise = b * (powi b (e - 1)) > ilog2 :: Integer -> Integer > ilog2 n | n < 0 = ilog2 (- n) > | n < 2 = 1 > | otherwise = up n (1 :: Integer) > where up n a = if n < (powi 2 a) > then bin (quot a 2) a > else up n (2*a) > bin lo hi = if (hi - lo) <= 1 > then hi > else let av = quot (lo + hi) 2 > in if n < (powi 2 av) > then bin lo av > else bin av hi (This was all properly aligned when I cut'n'pasted; proportional fonts might be messing it up here.)

3 2

Proper exception handling
by Thomas DuBuisson 15 Feb '08

15 Feb '08

Cafe, Fact 1: ghc{,i} does not crash when executing this code. Fact 2: I do not want this to crash. Question: Is there some theoretical window between the 'catchDyn' exception handling and the recursive call to 'catchThatDamnError' that could result in an unhandled exception? (of type 'DynError', of coarse) I suppose I am looking for an answer to this question from a language standpoint as well as a compiler pov. As an aside: I see at least one way to be certain of the safty by wrapping the call to forkIO in 'catchDyn', reforking if an exception is caught, and passing the new ThreadId to throwConstantly via shared mutable state - I'd like to avoid all this if my current example is safe. Thomas > import Control.Exception (catchDyn, throwDynTo) > import Control.Concurrent (forkIO, threadDelay) > import Control.Monad (forever) > import Data.Dynamic > > main = do > tid <- forkIO catchThatDamnError > forever $ throwConstantly tid > > catchThatDamnError = catchDyn start (\DynError -> catchThatDamnError) > > start = do > threadDelay 5000 > start > > throwConstantly tid = do > throwDynTo tid DynError > > data DynError = DynError deriving (Eq, Ord, Show, Typeable)

4 3

Re: [Haskell-cafe] Mutable arrays
by Jeff φ 15 Feb '08

15 Feb '08

On Feb 5, 2008 4:58 PM, Chaddaï Fouché <chaddai.fouche(a)gmail.com> wrote: > 2008/2/5, Jeff φ <jeff1.61803(a)gmail.com>: > > This is interesting. I've been programming in Concurrent Clean for a > while. > > Instead of monads, Clean supports unique types for mutable arrays and > IO. > > In Clean, I can write code that iterates through a mutable array by > > converting it to a lazy list. This is convenient because I can use all > the > > nice list processing functions that are available. > > > > You could absolutely write something like that in Haskell, but as some > have pointed out, this is probably _not a Good Idea_, even though it > works in your particular case, the array could be modified between the > time you get the lazy list and the time you actually read it... And > there's no way to insure it's not happening in Haskell, and I strongly > doubt there is in Concurrent Clean, could you confirm ? > Concurrent Clean can handle this in a safe way. Here's a code snippet for normalize_2D_ary from ArrayTest.icl: uToList_2D :: *(a u:(b c)) -> (.[c],*(a u:(b c))) | Array a (b c) & Array b c map_in_place_2d_arr :: (a -> a) *(b *(c a)) -> *(b *(c a)) | Array b (c a) & Array c a normalize_2D_ary :: *(a *(b c)) -> *(a *(b c)) | Array a (b c) & Array b c & / c & Ord c normalize_2D_ary ary = let (lst,ary2) = uToList_2D ary max_elem = foldl1 max lst in map_in_place_2d_arr (\ x -> x / max_elem) ary2 uToList_2D takes a unique array, ary, and returns a tuple containing a list of the array elements and a "new" array, ary2. uToList_2D does not modify ary, but Clean's type system forces any function that accesses a unique array to thread the array through and return a "new" array. Under the hood the "new" array actually uses the same memory storage as the original array. So, it is effecient. Threading the array serializes access insuring the array won't be modified until the list is complete. The type system will generate an error if I wrote code that breaks referential transparency. Array and IO Monads can be implemented in Clean on top of the uniqueness type system. The do-notation could be added to the language. However, the comments I've read so far lead me to believe the code I've shown cannot be implemented in Haskell using a lazy list without resorting to unsafe functions. I'm beginning to suspect the uniqueness type system of Clean is more general and flexible than Haskell's monads.

11 25

Re: [Haskell] Mailing List Archive: Search Broken?
by Janis Voigtlaender 15 Feb '08

15 Feb '08

Don Stewart wrote: > voigt: > >>Hi, >> >>it seems that something is wrong with the search on >> >> http://www.mail-archive.com/haskell@haskell.org/ >> >>Only messages from Nov and Dec 2007 are found, no matter what search >>phrases and date ranges are given. >> >>Worked yesterday and delivered search results over the whole history of >>the archive. >> >>Same for haskell-cafe. >> >>Anyone knows what is going on? > > > I always use gmane, via: > > http://news.gmane.org/search.php?match=haskell The problem with this is that when searching through gmane, and selecting a single message with a hit, one gets only to see that message without its context thread. At least I could not find out a way to switch from the found message to the thread in which it occurred. The search facility on www.mail-archive.com is much nicer in that respect, but as mentioned, as of yesterday seems to have forgotten about all messages prior to November 2007, and from 2008. Too bad... Ciao, Janis. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

3 5

Re: [Haskell-cafe] ANN: ctemplate, SSL server support in HsOpenSSL, network-minihttp, binary parsing, network-dns
by Donn Cave 15 Feb '08

15 Feb '08

On Feb 14, 2008, at 4:44 PM, Adam Langley wrote: > HsOpenSSL now has rudimentary support for writing SSL servers[5] > (clients coming soon). In terms of blocking IO, this /should/ work the > way you would hope (i.e. like a Haskell function w.r.t. forkIO). Coincidentally, night before last I downloaded the openssl source and started trying to think about an SSL library. The thing is, I have always wished for an SSL library that doesn't do I/O, but just transforms data and leaves the I/O to you. I guess that's going to be a good deal more complicated, and in many cases not worth it at all - so there would need to be an SSLIO layer above it - but clinging to some vague reactive-object ideals I imagine that this `pure' SSL core could fit into some kinds of dispatching frameworks where the usual thing would be awkward. Anyway, I'll write again in a few years if I get around to doing anything about it. Donn Cave, donn(a)avvanta.com

1 0

a general question on Arrows
by Steve Lihn 15 Feb '08

15 Feb '08

In John Hughes' paper [1], Programming with Arrows, p. 20, "The truly interesting arrow types are those which do not correspond to a monad, because it is here that arrows give us real extra generality. Since we know that stream functions cannot be represented as a monad, then they are one of these "interesting" arrow types. So are the arrows used for functional reactive programming, for building GUIs, and the arrows for discrete event simulation we present in Section 5. And since these arrows cannot be represented by a monad, we know that they cannot support a sensible definition of app either." He described a few things that "cannot" be represented as a monad, they are: 1. Stream 2. FRP 3. GUI (request/response?) 4. Event Driven System (like circuits, robots?) My first question is: Are they "absolutely" outside of the realm of function + monad, therefore, arrows are indispensable? Or it is simply because the haskell program would be very cumbersome without arrows in these areas? (I mean without utilizing FFI to rescue.) The second question is: Other than the 4 areas above, are there more? Just want to get a sense of how useful arrows are. Not really a theoretical question. Thanks, Steve [1] http://www.cs.chalmers.se/~rjmh/afp-arrows.pdf

2 3

Best way to find an "undefined" error?
by Scott West 15 Feb '08

15 Feb '08

Hello all, Does anyone favourite technique to track down an "undefined" call? I'm 99% sure that my code is not the offender (I've grepped for undefined occurrences and turned them all into "error" calls). Supposing that this is happening in some other package or library that I'm using, what is the best way to find out where it is? I have profiling enabled on all libraries that I use, so I'm ok there I think. Any magic combination of +RTS .. -RTS? Scott

3 6

ANN: Leksah 0.1 - Haskell IDE written in Haskell
by Jürgen Nicklisch-Franken 15 Feb '08

15 Feb '08

I'm pleased to announce the first release of Leksah, an IDE for Haskell written in Haskell. Leksah is intended as a practical tool to support the Haskell development process. This is an unfinished pre-release with bugs and open ends. However, I decided to make a first announcement, hoping that Leksah may already be interesting and useful. Leksah uses GTK+ as GUI Toolkit with the gtk2hs binding. It is platform independent and should run on any platform where GTK+, gtk2hs and GHC can be installed. I have tested it on Windows and Linux. It only supports GHC. Features: * jumping to code every and anywhere * integration of cabal build * source candy * keymaps * configurable window * ... Some rudimentary documentation can be found in the doc/ subdirectory. Author and availability: Leksah is written by me and published under a GPL-2 license. Leksah can be optained via Hackage: http://hackage.haskell.org/ Darcs development repository: http://code.haskell.org/leksah Juergen

8 9

ANN: ctemplate, SSL server support in HsOpenSSL, network-minihttp, binary parsing, network-dns
by Adam Langley 15 Feb '08

15 Feb '08

Binary parsing: binary-strict now has support for combinator parsing[1] with <|> and friends. This works both for the strict Get and the IncrementalGet. (The latter was more complex than I expected) binary-strict also gained a very fast byte set module[2] (used for scanning ranges of valid bytes) and a surprisingly useful hexDump[3] function (because I kept having to write it in lots of places) [1] http://hackage.haskell.org/packages/archive/binary-strict/0.3.0/doc/html/Da… [2] http://hackage.haskell.org/packages/archive/binary-strict/0.3.0/doc/html/Da… [3] http://hackage.haskell.org/packages/archive/binary-strict/0.3.0/doc/html/Da… DNS: network-dns contains a DNS client library[4] in pure Haskell. The ADNS library (for which a wrapper already exists) is GPL, not BSD. This code is also halfway to being a DNS server should anyone so wish. This is very similar to the DNS client library in libevent (because I wrote them both). HTTP: ctemplate is a wrapping of the template library which Google uses for most of their sites. There are several template systems already in Hackage, but I like ctemplate because escaping is so easy and well supported. Generally the power of a template system doesn't interest me (in fact, it can be a bad thing), but stopping XSS attacks is a big deal. HsOpenSSL now has rudimentary support for writing SSL servers[5] (clients coming soon). In terms of blocking IO, this /should/ work the way you would hope (i.e. like a Haskell function w.r.t. forkIO). network-minihttp is a small HTTP server. Currently it serves files from the disk (with caching and range support), but it's most of the way to being a HTTP client also. Don't do anything too serious with it yet, however. It needs a few limits to stop DoS attackers from, for example, sending an infinite header and using up all the memory :) [4] http://hackage.haskell.org/packages/archive/network-dns/0.1.1/doc/html/Netw… -- Adam Langley agl(a)imperialviolet.org http://www.imperialviolet.org 650-283-9641

1 0

Re: [Haskell-cafe] Re: A question about "monad laws"
by Thorkil Naur 15 Feb '08

15 Feb '08

Hello, On a tangent, probably: On Thursday 14 February 2008 10:24, Roman Leshchinskiy wrote: > ... > Hmm. Personally, I've never seen an algorithm where comparing for exact > equality was algorithmically necessary. Sometimes (rarely) it is > acceptable but necessary? Do you know of one? Finding the "machine epsilon", perhaps, that is, the smallest (floating point, surely) number for which 1.0+machine_eps==1.0 would be a candidate? > ... Best regards Thorkil

2 1

Haskell wiki is searched by google.
by Daniil Elovkov 14 Feb '08

14 Feb '08

Hello I remember there was a problem with haskell wiki pages not being indexed and searched. Now it seems to work perfectly. Actually typing 'monomorphism restriction' in google I see the appropriate wiki page as the first result. I must have missed the moment when it was fixed. Just sharing my observations. Thanks.

4 6

threads + IORefs = Segmentation fault?
by David Roundy 14 Feb '08

14 Feb '08

Hi all, I'm working on some new progress-reporting code for darcs, and am getting segmentation faults! :( The code uses threads + an IORef global variable to do this (with lots of unsafePerformIO). So my question for the gurus who know more about this than I do: is this safe? I thought it would be, because only one thread ever modifies the IORef, and the others only read it. I don't really care if they read a correct value, as long as they don't segfault. The code (to summarize) looks like: {-# NOINLINE _progressData #-} _progressData :: IORef (Map String ProgressData) _progressData = unsafePerformIO $ newIORef empty updateProgressData :: String -> (ProgressData -> ProgressData) -> IO () updateProgressData k f = when (progressMode) $ modifyIORef _progressData (adjust f k) setProgressData :: String -> ProgressData -> IO () setProgressData k p = when (progressMode) $ modifyIORef _progressData (insert k p) getProgressData :: String -> IO (Maybe ProgressData) getProgressData k = if progressMode then lookup k `fmap` readIORef _progressData else return Nothing The key function is beginTedious :: String -> IO () beginTedious k = do tid <- forkIO $ handleProgress k debugMessage $ "Beginning " ++ k setProgressData k $ ProgressData { sofar = 0, latest = Nothing, total = Nothing, handler = Just tid } which is called before an action that may be so tedious for our users that they need their day brightened by messages such as "Applying patch 137/1436". The handleProgress function alternates between threadDelay and reading the progress data to see whether any progress has been made and printing messages. Meanwhile the main thread calls functions that update _progressData. Anyhow, the point is that I'm getting segfaults, even after recompiling everything from scratch! Is this in fact that unsafe? Do I really need to switch to MVars, even though no locking is required? -- David Roundy Department of Physics Oregon State University

6 9

Designing DSL with explicit sharing [was: I love purity, but it's killing me]
by oleg＠okmij.org 14 Feb '08

14 Feb '08

Tom Hawkins wrote: ] My DSLs invariably define a datatype to capture expressions; something ] like this: ] ] data Expression ] = Add Expression Expression ] | Sub Expression Expression ] | Variable String ] | Constant Int ] deriving Eq ] The problem comes when I want to generate efficient code from an ] Expression (ie. to C or some other target language). The method I use ] invovles converting the tree of subexpressions into an acyclic graphic ] to eliminate common subexpressions. The nodes are then topologically ] ordered and assigned an instruction, or statement for each node. For ] example: ] ] let a = Add (Constant 10) (Variable "i1") ] b = Sub (Variable "i2") (Constant 2) ] c = Add a b ] The process of converting an expression tree to a graph uses either Eq ] or Ord (either derived or a custom instance) to search and build a set ] of unique nodes to be ordered for execution. In this case "a", then ] "b", then "c". The problem is expressions often have shared, ] equivalent subnodes, which dramatically grows the size of the tree. ] For example: ] ] let d = Add c c ] e = Add d d -- "e" now as 16 leaf nodes. ] ] As these trees grow in size, the equality comparison in graph ] construction quickly becomes the bottleneck for DSL compilation. We show the design of the same sort of DSL that explicitly maintains sharing information and where node comparisons are quick, because we are comparing hashes rather than trees themselves. Our approach is assuredly safe, pure, and Haskell98 (save for disabling of the monomorphism restriction, which is done solely to avoid writing signatures). No GHC-specific behavior is relied upon. > {-# OPTIONS_GHC -fno-monomorphism-restriction #-} > > module DSL where > > import Data.IntMap as IM > import Control.Monad.State The approach is based on the final tagless representation. Here is our DSL: > class Exp repr where > constant :: Int -> repr Int > variable :: String -> repr Int > add :: repr Int -> repr Int -> repr Int > sub :: repr Int -> repr Int -> repr Int Tom Hawkins' test expressions now look as follows > a = add (constant 10) (variable "i1") > b = sub (variable "i2") (constant 2) > c = add a b > d = add c c > e = add d d which is the same as before modulo the case of the identifiers: everything is in lower case. We can show the expressions as before: showing is one way of evaluating things > newtype S t = S{unS :: String} > > instance Exp S where > constant x = S $ show x > variable x = S x > add e1 e2 = S( unS e1 ++ " + " ++ unS e2) > sub e1 e2 = S( unS e1 ++ " - " ++ unS e2) > > test_showe = unS e *DSL> test_showe "10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2" We can write an evaluator for the expressions > type REnv = [(String,Int)] > newtype R t = R{unR :: REnv -> t} -- A reader Monad, actually > > instance Exp R where > constant x = R $ const x > variable x = R ( \env -> maybe (error $ "no var: " ++ x) id $ > Prelude.lookup x env) > add e1 e2 = R(\env -> unR e1 env + unR e2 env) > sub e1 e2 = R(\env -> unR e1 env - unR e2 env) > test_vale = unR e [("i1",5),("i2",10)] -- 92 We stress: we are using exactly the same expression e as before. We are only evaluating it differently. The gist of the final tagless approach is to write an expression once and evaluate it many times. Now, we chose a different representation: to make sharing explicit We chose not to rely on GHC; we don't care if in (add c c), the two c are shared or copied. It is not observable in pure Haskell, and we don't care. We build our acyclic graph nevertheless. > type ExpHash = Int We stress: ACode is NOT a recursive data structure, so the comparison of ACode values takes constant time! > data ACode = AConst ExpHash | > AVar ExpHash | > AAdd ExpHash | > ASub ExpHash > deriving (Eq,Show) > data ExpMaps = ExpMaps{ hashcnt :: ExpHash, -- to generate new Hash > ctmap :: IntMap Int, > vrmap :: IntMap String, > admap :: IntMap (ACode,ACode), > sumap :: IntMap (ACode,ACode)} > deriving Show > exmap0 = ExpMaps 0 IM.empty IM.empty IM.empty IM.empty > > > newtype A t = A{unA :: State ExpMaps ACode} Granted, the following could be done far more efficiently: we need bimaps. > loookupv :: Eq v => v -> IntMap v -> Maybe Int > loookupv v = IM.foldWithKey > (\k e z -> maybe (if e == v then Just k else Nothing) (const z) z) > Nothing > > record con prj upd x = do > s <- get > maybe (do let s' = upd (s{hashcnt = succ (hashcnt s)}) > (IM.insert (hashcnt s) x (prj s)) > put s' > return (con $ hashcnt s)) > (return . con) $ loookupv x (prj s) > instance Exp A where > constant x = A(record AConst ctmap (\s e -> s{ctmap = e}) x) > variable x = A(record AVar vrmap (\s e -> s{vrmap = e}) x) > add e1 e2 = A(do > h1 <- unA e1 > h2 <- unA e2 > record AAdd admap (\s e -> s{admap = e}) (h1,h2)) > sub e1 e2 = A(do > h1 <- unA e1 > h2 <- unA e2 > record ASub sumap (\s e -> s{sumap = e}) (h1,h2)) Again, we are using the very same expression e we wrote at the very beginning: > test_sme = runState (unA e) exmap0 *DSL> test_sme (AAdd 8, ExpMaps {hashcnt = 9, ctmap = fromList [(0,10),(4,2)], vrmap = fromList [(1,"i1"),(3,"i2")], admap = fromList [(2,(AConst 0,AVar 1)),(6,(AAdd 2,ASub 5)), (7,(AAdd 6,AAdd 6)),(8,(AAdd 7,AAdd 7))], sumap = fromList [(5,(AVar 3,AConst 4))]}) We retain all the information about expression 'e'. In addition, all sharing is fully explicit. As we can see, the evaluation process finds common subexpressions automatically.

4 5

Re: [Haskell-cafe] ANN: nano-hmac 0.2.0
by Don Stewart 14 Feb '08

14 Feb '08

Ok, I'll leave it up there as a separate package then. :) -- Don hitesh.jasani: > Don, > > It's tempting, but I would really hate to lose nano-md5 as it is > today. I thought your concept was a great idea to inspire people to > start small to get a feel for developing Haskell libraries. The > current nano-md5 serves as a really good example. > > In the Ruby community there are many small libraries that do one, > simple focused task. There are times when this is a virtue over > libraries that try to be all encompassing. It's weird but I would > have thought the Haskell community would have more embraced small > libraries also since they may be more composable. > > - Hitesh > > > On Feb 11, 2008 4:29 PM, Don Stewart <dons(a)galois.com> wrote: > > hitesh.jasani: > > > nano-hmac provides bindings to OpenSSL's HMAC interface. With this release the > > > set of hashing functions supported is: MD5, SHA, SHA1, SHA224, SHA256, SHA384, > > > SHA512. > > > > > > If you're unfamiliar with HMAC's then you may want to check out the second link > > > below where I explain a little bit about them in a blog entry. > > > > > > The hackage pages mentioned that they're not running haddock 2.0, so I don't > > > know if the docs will generate. If not, you can see the docs online at the > > > third link below. > > > > > > * http://hackage.haskell.org/cgi-bin/hackage-scripts/package/nano-hmac-0.2.0 > > > * http://www.jasani.org/2008/02/nano-hmac-020-released.html > > > * http://docs.jasani.org/nano-hmac/0.2.0/ > > > > > > Any and all comments/suggestions/criticisms/fortune-cookie-proverbs are welcome. > > > > > > > Shall we merge nano-md5 into this lib, and deprecate nano-md5 itself? > > Seems like a good time to consolidate, and produce a single openssl > > binding. > > > > -- Don > >

3 2

Re: [Haskell-cafe] existential types
by Jake McArthur 14 Feb '08

14 Feb '08

From: Jake McArthur <jake.mcarthur(a)gmail.com> Date: February 13, 2008 7:04:49 PM CST To: Felipe Lessa <felipe.lessa(a)gmail.com> Subject: Re: [Haskell-cafe] existential types On Feb 13, 2008, at 11:15 AM, Felipe Lessa wrote: > On Feb 13, 2008 2:41 PM, Jake McArthur <jake.mcarthur(a)gmail.com> > wrote: >> Now we can have NumericLists like [1 :: Int, 5.7 :: Double, 4%5 :: >> Rational]. > > No, we can't =). Using > > data NumericList = forall a . Num a => N [a] > [etc.etc.etc.] Oops again. Maybe I just shouldn't say anything to anybody on the Internet within an hour of waking up in the morning! ;) - Jake

1 0

getSymbolicLinkStatus completely broken on some 6.8.2 systems
by Jeremy Shaw 14 Feb '08

14 Feb '08

Hello, I get funny results when I call getSymbolicLinkStatus in ghc 6.8.2 on Ubuntu 7.10. This happens on several systems and has been confirmed by other people. Though, some people on almost the exact same system claimed to not see it at all. Here is an interactive example with ghci, note how the result changes from run to run. (Although not shown below, the values do sometimes repeat, so it is not completely random): Prelude> System.Posix.Files.getSymbolicLinkStatus "/etc/motd" >>= print . System.Posix.Files.fileID 13165085651657739420 Prelude> System.Posix.Files.getSymbolicLinkStatus "/etc/motd" >>= print . System.Posix.Files.fileID 13165312309966851228 Prelude> System.Posix.Files.getSymbolicLinkStatus "/etc/motd" >>= print . System.Posix.Files.fileID 623410571888290073 Prelude> System.Posix.Files.getSymbolicLinkStatus "/etc/motd" >>= print . System.Posix.Files.fileID 12892261005034 If I *compile* the following (with or without optimization): module Main where import System.Posix.Files main = do getSymbolicLinkStatus "/etc/motd" >>= print . fileID getSymbolicLinkStatus "/etc/motd" >>= print . fileID getSymbolicLinkStatus "/etc/motd" >>= print . fileID getSymbolicLinkStatus "/etc/motd" >>= print . fileID Then I get all 0: /tmp # ./test 0 0 0 0 I have tested the same code under GHC 6.6 and 6.4 and it works fine. Additionally, getFileStatus, seems to work fine everytime. (Unfortunately, I really need getSymbolicLinkStatus). If anyone has a work-around or fix that I can use in the next 15 hours, that would be extremely useful ;) Thanks in advance! j.

2 6

existential types
by Simeon Mattes 14 Feb '08

14 Feb '08

I have found that ghc has adopted the existential data constructors. Because it was first time I have heard this term I have found some articles about it. The less complex for me was the following explanation data Worker x y = Worker {buffer :: b, input :: x, output :: y} This is wrong in Haskell98 because we can 't just hide buffer :: b. We should write instead data Worker b x y = Worker {buffer :: b, input :: x, output :: y} Let suppose that b has an indefinite type. Then with existential types we could write data Worker x y = forall b. Buffer b => Worker {buffer :: b, input :: x, output :: y} The example above is similar to the example that Paul Hudak, John Hughes, Simon Peyton Jones and Philip Wadler mention in an article "a history of Haskell". Though I can't figure out how exactly could utilize such a type. To be honest haskell is my first functional language and I 'm not so familiar with. So, an example would be very helpful

8 9

ANN: unix-pty-light 0.1
by Stuart Cook 13 Feb '08

13 Feb '08

A little while ago, I needed bindings for creating and accessing a pseudo-terminal device. Since I couldn't find any in the unix package, I wrote my own. Later, I found out that unix-2.2.0.0 does indeed contain pseudo-terminal bindings, but unfortunately it seems to be incompatible with my version of GHC (6.6). Therefore, I have created a package that provides pseudo-terminal support, and should work with both 6.6 and 6.8 (though I have only tested 6.6). As always, comments and feedback are most welcome. Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/unix-pty-light-0… Darcs: http://code.haskell.org/~scook0/unix-pty-light/ Haddock: http://code.haskell.org/~scook0/haddock/unix-pty-light/ Stuart Cook

1 0