March 2009 - Haskell-Cafe

about Haskell code written to be "too smart"
by Manlio Perillo 04 Apr '09

04 Apr '09

Hi. In these days I'm discussing with some friends, that mainly use Python as programming language, but know well other languages like Scheme, Prolog, C, and so. These friends are very interested in Haskell, but it seems that the main reason why they don't start to seriously learning it, is that when they start reading some code, they feel the "Perl syndrome". That is, code written to be "too smart", and that end up being totally illegible by Haskell novice. I too have this feeling, from time to time. Since someone is starting to write the Haskell coding style, I really suggest him to take this "problem" into strong consideration. Manlio

40 124

g++ std:map vs GHC IntMap
by Manlio Perillo 04 Apr '09

04 Apr '09

Hi. I have tried to compare performance of the g++ std::map versus the GHC IntMap. The test consists in adding 10000000 elements to an empty map. Haskell code is here: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2899 C++ code is here: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2900 The execution time and CPU usage is almost the same. However the C++ version requires 305 MB, the GHC version 617 MB. gcc 4.3.2 ghc 6.8.2 on Debian Linux Lenny, i386. Isn't really possible to optimize memory usage in cases like this? I also tried with Data.HashTable: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2902 but memory usage is 703 MB, and execution time is about 4.5 times slower! Thanks Manlio Perillo

6 11

Looking for practical examples of Zippers
by Gü?nther Schmidt 02 Apr '09

02 Apr '09

Hi, my quest for data structures continues. Lately I came across "Zippers". Can anybody point be to some useful examples? Günther

12 15

Character I/O
by Andrew Coppin 02 Apr '09

02 Apr '09

I ran the following program: >module Main where > >main = do > putStrLn "Key" > c <- getChar > print c > main Unfortunately, it doesn't do what I was hoping. Specifically, it only returns any data when I hit [return]. It also seems to be giving me a command history somehow. Special keys (e.g., arrow keys, backspace, escape) don't get through to the application. I'm trying to write a program that uses individual keys as commands. What's the correct way to get this to work?

5 7

ANNOUNCE: vacuum: extract graph representations of ghc heap values.
by Matt Morrow 01 Apr '09

01 Apr '09

I am pleased to announce the release of vacuum, a Haskell<http://haskell.org/>library for extracting graph representations of values from the GHC <http://haskell.org/ghc/> heap, which may then be further processed and/or translated to Graphviz <http://graphviz.org/> dot format to be visualized. The package website is at http://moonpatio.com/vacuum/, which contains a gallery section (which i intend to add to over time). The most recent version is 0.0.6, which is available on Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/vacuum/. Feedback, comments, and/or gallery submissions will be gratefully received via this email address (contrary to the email address currently on the vacuum Hackage page (i fail at setting up email :)). Matt

2 2

Parsing with Proof
by muad 01 Apr '09

01 Apr '09

Hi everyone on haskell-cafe, I am wondering about how to give a correctness prove of a simple parsing algorithm. I tried to think of a simple example but even in this case I don't know how. I have an abstract syntax: > data Parens = Empty | Wrap Parens | Append Parens Parens assumption (A), in Append x y, x and y are never Empty assumption (B), Strings only contain '(' and ')' characters and a printing function > print :: Parens -> String > print Empty = "" > print (Wrap m) = "(" ++ print m ++ ")" > print (Append x y) = print x ++ print y So the idea is that I would like to write parse :: String -> Maybe Parens, such that if it gives Nothing then the String was malformed, if it gives Just x then the string should be equal to print x. I think I can write such a function in a few different ways, but I don't know how to prove this code works, could anybody show me how? Thank you for any replies. -- View this message in context: http://www.nabble.com/Parsing-with-Proof-tp22814576p22814576.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 3

Re: Definition of "tail recursive" wrt Folds
by Ben Franksen 01 Apr '09

01 Apr '09

Mark Spezzano wrote: > Just looking at the definitions for foldr and foldl I see that foldl is > (apparently) tail recursive while foldr is not. > > Why? > > Is it because foldl defers calling itself until last whereas foldr > evaluates itself as it runs? > > What, strictly speaking, is the definition of ”tail recursive” as opposed > to just “recursive”? An application of some function f inside another function g is in 'tail position' (or a 'tail call') if the result of applying f is the result of g. Operationally speaking, calling f is the very last thing g does. Tail calls can be optimized by a compiler (or interpreter) so that the call does not use additional stack; that is, the call can be replaced by a jump. A function is called ”tail recursive” (as opposed to just “recursive”) if the recursive call to itself is in tail position. If the compiler performs tail call optimization, tail recursive functions can work with constant stack space, similar to a (imperative) loop. Looking at a definition of foldl, e.g. foldl f z0 xs0 = lgo z0 xs0 where lgo z [] = z lgo z (x:xs) = lgo (f z x) xs you see that lgo calls itself in tail position, thus is tail recursive. In contrast, foldr can be defined as foldr k z xs = go xs where go [] = z go (y:ys) = y `k` go ys where you see that the result of go is not the recursive call to go. Instead, the result is y `k` go ys . Thus, foldr is not tail recursive. So, if you are saying that "foldl defers calling itself until last whereas foldr evaluates itself as it runs" then you got the right idea, I think. The point is that foldr still needs to do something (namely to apply (y `k`)) to the result of applying itself. It needs to remember to do so, and thus the stack grows linearly with the size of the list. Cheers Ben

2 2

ANN: cmonad 0.1.1
by Lennart Augustsson 01 Apr '09

01 Apr '09

I've uploaded my CMonad package to Hackage. It allows you to write Haskell code in a C style. Unfortunately, GHC lacks certain optimizations to make efficient code when using CMonad, so instead of C speed you get low speed. Example: Computing some Fibonacci numbers: fib = do { a <- arrayU[40]; i <- auto 0; a[0] =: 1; a[1] =: 1; for (i =: 2, (i :: EIO Int) < 40, i += 1) $ do { a[i] =: a[i-1] + a[i-2]; }; retrn (a[39]); } Example: Copying stdin to stdout: cat = do { c <- auto 0; while ((c =: getchar()) >= 0) $ do { putchar(c); }; return (); } -- Lennart

16 22

[SoC] XML Schema Implementation
by Vlad Dogaru 01 Apr '09

01 Apr '09

Hello everyone, I am writing to judge interest in a Summer of Code proposition: an XML Schema[1] implementation, described as a possbile application here[2]. As both a tool and an inspiration, I intend to use HaXML[3]. More specifically, I would be interested in the degree the Haskell community uses XML Schema, and if you were tempted to use it if we had an implementation. To further expand the question, how useful do you consider each of these components: * a validator * a pretty-printer * a translator from XML Schema to Haskell, similar to DtdToHaskell[4] For the latter item, some runtime checking will definitely be required: restrictions such as value ranges for integers or minimum and maximum occurences of an element cannot, to my knowledge, be enforced through type definitions. Finally, I kindly ask anyone with relevant experience to point out other possible pitfalls. Vlad Dogaru [1] http://www.w3schools.com/Schema/ [2] http://hackage.haskell.org/trac/summer-of-code/ticket/1120 [3] http://www.cs.york.ac.uk/fp/HaXml/ [4] http://www.cs.york.ac.uk/fp/HaXml/Xml2Haskell.html

6 6

[ANN] salvia-0.1, salvia-extras-0.1
by Sebastiaan Visser 01 Apr '09

01 Apr '09

Hi all, I am pleased to announce a new version of Salvia, the lightweight Haskell Web Server Framework with modular support for serving static files, directories indices, default error responses, connection counting and logging, HEAD and PUT requests, keep-alives, custom banner printing, default handler environments for parsing request and printing responses, dispatching based on request methods, URI, paths and filename extension, URI rewriting and redirection, virtual hosting, cookie, session and user management and more... Changes since previous version: - Some more advanced, non-fundamental handlers have been moved to their own package salvia-extras. This helps pruning the dependencies a bit. - The package now has some default handler environments that simplify setting up a server application. - The server now has support for keep-alive, significantly increasing the performance. - The library functions are now almost fully documented instead of no- documentation-at-all in the previous versions. - Salvia now also works on windows (I heard). - Lots of code cleanups throughout the code. - Lots of minor bug fixes. To install: use cabal. Thanks to the people that helped me with suggestions and bug-reports! -- Sebastiaan.

2 2