September 2008 - Haskell-Cafe

the way to fail
by Jason Dusek 24 Sep '08

24 Sep '08

Whenever `fail` comes up, there are usually remarks to the effect that it doesn't really belong in the definition of `Monad`. Where does `fail` belong? Could it go in `Arrow`? -- _jsn

2 1

Haskell Weekly News: Issue 86 - September 20, 2008
by Brent Yorgey 24 Sep '08

24 Sep '08

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20080920 Issue 86 - September 20, 2008 --------------------------------------------------------------------------- Welcome to issue 86 of HWN, a newsletter covering developments in the [1]Haskell community. Lots of NEW stuff this week! A new generics library, new versions of Pandoc and darcs, a new website for xmonad, a new GADT/type family inference engine for GHC, a Haskell binding for Qt, and some new, astonishingly elegant ideas from Oleg. Also, here's hoping that everyone has a lot of fun at ICFP! Announcements GHC version control. Simon Peyton-Jones [2]sent out a revised proposal for GHC version control. darcs 2.0.3pre1. Eric Kow [3]announced the first pre-release of [4]darcs 2.0.3, featuring a few major bug fixes and a handful of interesting features. EMGM. Sean Leather [5]announced a release of [6]Extensible and Modular Generics for the Masses (EMGM), a library for generic programming in Haskell using type classes. Pandoc 1.0.0.1. John MacFarlane [7]announced the release of [8]pandoc 1.0.0.1, the swiss army knife of text markup formats. Iteratee-based IO. oleg [9]described a [10]safe, declarative approach to input processing which will be the subject of a talk at DEFUN08 on September 27. MetaHDBC paper. Mads Lindstroem [11]announced a [12]draft version of a paper about the [13]MetaHDBC library, which uses Template Haskell to do type-safe database access. Comments are welcomed, especially about the overall quality of the paper, whether it can be called scientific, and anything Mads could do to improve the paper. qtHaskell 1.1.2. David Harley [14]announced a second preview release of [15]qtHaskell, a set of Haskell bindings for Trolltech's Qt. Discussion Library design question. Andre Nathan [16]asked for advice on designing a simple graph library. The resulting discussion included an analysis of using the State monad versus a more functional approach. A round of golf. Creighton Hogg [17]learns about laziness by [18]making grown men cry. XML (HXML) parsing :: GHC 6.8.3 space leak from 2000. Lev Walkin [19]discovers a nice example of an obscure class of space leaks while writing some XML-processing code, prompting an in-depth analysis by Simon Marlow. Proofs and commercial code. Daryoush Mehrtash [20]asked about automated proof tools and techniques, and their uses in the real world. Blog noise [21]Haskell news from the [22]blogosphere. * Creighton Hogg: [23]Haskell Cafe or: How I learned to stop worrying & love laziness. * Douglas M. Auclair (geophf): [24]Animal as RDR, part II. Doug continues his posts on RDR expert systems. * Ivan Lazar Miljenovic: [25]Getting Real World Haskell Down Under. * Douglas M. Auclair (geophf): [26]Animal: an RDR implementation study. Doug describes "ripple-down rules" expert systems, and illustrates the types needed to encode one in Haskell. * Mark Jason Dominus: [27]data Mu f = In (f (Mu f)). Mark writes about fixpoints of type constructors. * John Goerzen (CosmicRay): [28]Switched from KDE to xmonad. John has taken the plunge to xmonad and seems to like it so far! * Eric Kow (kowey): [29]darcs weekly news #4. Pre-release of darcs 2.0.3; darcs hacking sprint next month; code.haskell.org upgrades to darcs 2; and other news. * Mads Lindstroem: [30]MetaHDBC paper (draft). Mads's first paper ever, on using Template Haskell for type-safe database access. Comments welcome! * Braden Shepherdson: [31]xmonad-light 0.8 Released. * Manuel M T Chakravarty: [32]GHC HEAD just got a new inference engine for GADTs and type families.. * Magnus Therning: [33]Haskell and Time. Magnus describes the solution to a problem with Data.Time. * Dan Piponi (sigfpe): [34]Two Papers and a Presentation. * Xmonad: [35]New xmonad website launched. xmonad has a shiny new website! Quotes of the Week * Botje: GHC 11 will have shootout entries as primitives. * wjt: oh, i see what you're doing. ...no, i don't. *splode* * Benjamin Pierce: [on existential types] I have a term, and it has a type. So there. * bos: come on, real programmers use "(((,) <$>) .) . (<*>)" * quicksilver: #haskell : Sometimes we answer your question, sometimes we lay hideous traps which will devour your soul. It's a risk you take. * harrison: [on computing 1000000!] it is the same as factorial 999999 * 1000000, big deal About the Haskell Weekly News New editions are posted to [36]the Haskell mailing list as well as to [37]the Haskell Sequence and [38]Planet Haskell. [39]RSS is also available, and headlines appear on [40]haskell.org. To help create new editions of this newsletter, please see the information on [41]how to contribute. Send stories to byorgey at cis dot upenn dot edu. The darcs repository is available at darcs get [42]http://code.haskell.org/~byorgey/code/hwn/ . References 1. http://haskell.org/ 2. http://www.haskell.org//pipermail/libraries/2008-September/010661.html 3. http://www.haskell.org//pipermail/haskell-cafe/2008-September/047664.html 4. http://www.darcs.net/darcs-2.0.3pre1.tar.gz 5. http://www.haskell.org//pipermail/haskell-cafe/2008-September/047751.html 6. http://www.cs.uu.nl/wiki/GenericProgramming/EMGM 7. http://www.haskell.org//pipermail/haskell-cafe/2008-September/047437.html 8. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/pandoc 9. http://article.gmane.org/gmane.comp.lang.haskell.cafe/44828 10. http://okmij.org/ftp/Haskell/Iteratee/ 11. http://article.gmane.org/gmane.comp.lang.haskell.cafe/44713 12. http://lindstroem.files.wordpress.com/2008/09/metahdbc.pdf 13. http://www.haskell.org/haskellwiki/MetaHDBC 14. http://article.gmane.org/gmane.comp.lang.haskell.general/16425 15. http://qthaskell.berlios.de/ 16. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/44733 17. http://abstractabsurd.blogspot.com/2008/09/haskell-cafe-or-how-i-learned-to… 18. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/44724 19. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/44708 20. http://www.haskell.org//pipermail/haskell-cafe/2008-September/047440.html 21. http://planet.haskell.org/ 22. http://haskell.org/haskellwiki/Blog_articles 23. http://abstractabsurd.blogspot.com/2008/09/haskell-cafe-or-how-i-learned-to… 24. http://logicaltypes.blogspot.com/2008/09/animal-as-rdr-part-ii.html 25. http://ivanmiljenovic.wordpress.com/2008/09/19/getting-real-world-haskell-d… 26. http://logicaltypes.blogspot.com/2008/09/animal-rdr-implementation-study.ht… 27. http://blog.plover.com/prog/springschool95-2.html 28. http://changelog.complete.org/posts/756-Switched-from-KDE-to-xmonad.html 29. http://koweycode.blogspot.com/2008/09/darcs-weekly-news-4.html 30. http://lindstroem.wordpress.com/2008/09/18/metahdbc-paper-draft/ 31. http://braincrater.wordpress.com/2008/09/17/xmonad-light-08-released/ 32. http://justtesting.org/post/50500880 33. http://therning.org/magnus/archives/389 34. http://sigfpe.blogspot.com/2008/09/two-papers-and-presentation.html 35. http://xmonad.wordpress.com/2008/09/14/new-xmonad-website-launched/ 36. http://www.haskell.org/mailman/listinfo/haskell 37. http://sequence.complete.org/ 38. http://planet.haskell.org/ 39. http://sequence.complete.org/node/feed 40. http://haskell.org/ 41. http://haskell.org/haskellwiki/HWN 42. http://code.haskell.org/~byorgey/code/hwn/

3 3

A question about parsec implementation
by Xinyu Jiang 24 Sep '08

24 Sep '08

Hi everybody, I am trying to port (a part of) the parsec library to scheme. I have read the paper and the haskell source of parsec, but I still have a problem. May be the problem is from my lack of parser knowledge, but I have to bother you. Scheme does not support lazy evaluation by default, so I simulated laziness when implementing finite lookahead. The result was not what I expected: it slowed down the parser and ate more memory, not speeding it up and reducing its space leak. If finite lookahead is a real gain, it would beat the cost of simulating lazy evaluation, which is not much. After analysis my code, I drew a conclusion (which may be wrong) that if the grammar you write is LL(1), that is, you don't use the "try" combinator, the time complexity of the predictive parser and the backtracking parser will be the same when they both suceed. Because in an LL(1) grammar, any consumed errors will make the whole parser return errors. Since the behaviors of the predictive parser and the backtracking parser are the same on LL(1) grammars, the backtracking parser will only eat more memory than the predictive parser when it fails. Is my conclusion right? Does parsec perform better than backtracking parsers on a pure LL(1) grammar when it suceeds? I am very grateful for your answer, thanks.

1 0

what is the magic hash?
by Jason Dusek 24 Sep '08

24 Sep '08

It is not much covered in the docs. It has something to do with magic triggered by a postfix octothorpe? -- _jsn |...docs.| http://haskell.org/ghc/docs/latest/html/users_guide/flag-reference.html

3 3

ANN: A Functional Implementation of the Garsia-Wachs Algorithm
by Nicolas Pouillard 23 Sep '08

23 Sep '08

Hi All, Here is an Haskell implementation of an algorithm that builds a binary tree with minimum weighted path length from weighted leaf nodes given in symmetric order. This can be used to build optimum search tables, to balance a 'ropes' data structure in an optimal way. This module a direct translation from OCaml of a functional pearl by Jean-Christophe Filliâtre yesterday on ML Workshop 2008. There was an interesting point to porting it to Haskell, indeed there is a crucial use of first-class references used only locally. A good reason to show the power of the ST monad and it's runST function! Here is the hackage URL: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/garsia-wachs And the darcs 2 URL: http://darcs.feydakins.org/garsia-wachs -- Nicolas Pouillard aka Ertai

3 3

Re: ANNOUNCE: protocol-buffers-0.2.9 for Haskell is ready
by Chris Kuklewicz 23 Sep '08

23 Sep '08

I am cross-posting this message to several lists. I had learned the trick before the documentation was updated. It seems I have used a very unreliable trick. And the "use castToSTUArray" suggested alternative is a really poor one since I am not using arrays at all. Who can suggest a way to cast from Float to Word32 and Double to Word64 using ghc? The actual task is that I need to write out the Float as a little endian sequence of four bytes and also be able to read it back in. The writing and reading are done in Put and Get monads to ByteString (from the "binary" package). The alloca/poke/peek work around I have looks like castWord32ToFloat :: Word32 -> Float castWord32ToFloat x = unsafePerformIO $ alloca $ \p -> poke p x >> peek (castPtr p) castFloatToWord32 :: Float -> Word32 castFloatToWord32 x = unsafePerformIO $ alloca $ \p -> poke p x >> peek (castPtr p) The unsafeCoerce trick that is no longer working looks like: castWord64ToDouble :: Word64 -> Double castWord64ToDouble (W64# w) = D# (unsafeCoerce# w) castDoubleToWord64 :: Double -> Word64 castDoubleToWord64 (D# d) = W64# (unsafeCoerce# d) Any ideas? Or is the alloca trick the only way to do this? Chris Ian Lynagh wrote: > Hi Chris, > > On Sun, Sep 21, 2008 at 05:37:33PM +0100, Chris Kuklewicz wrote: >> Also, I tried two tricks: >> (D# x) <-> (W64# x) which works fine >> (F# x) <-> (W32# x) which produced garbage, so I had to replace it with >> alloca/poke/peek. > > This isn't supported, and I suspect is the cause of the -fasm problems. > > Please see > http://hackage.haskell.org/trac/ghc/ticket/2209 > for more details and suggested alternative. > > > Thanks > Ian >

4 3

hGetContents and lazyness
by Max Vasin 23 Sep '08

23 Sep '08

Hello, haskellers! Suppose we have function (it filters package filenames from apt Packages file): > getPackageList :: FilePath -> IO [FilePath] > getPackageList packageFile = withFile packageFile ReadMode $ > \h -> do c <- hGetContents h > return $ map (drop 10) $ filter (startsWith "Filename:") $ lines c -- (1) > where startsWith [] _ = True > startsWith _ [] = False > startsWith (x:xs) (y:ys) | x == y = startsWith xs ys > | otherwise = False When, I apply it to a Packages file I (surely) get an empty list. This is an expected result due to lazyness of hGetContents. I tried changing line (1) to > return $ map (drop 10) $ filter (startsWith "Filename:") $! lines c or > return $ map (drop 10) $! filter (startsWith "Filename:") $! lines c with no success. Chaning it to > return $! map (drop 10) $ filter (startsWith "Filename:") $ lines c makes getPackageList function return several (but not all) filenames. What I'm missing? And how can I fix my code? -- WBR, Max Vasin.

2 3

"piping" to system call
by Janis Voigtlaender 23 Sep '08

23 Sep '08

Hi, assume I have a program taking input from stdin. How do I call it from Haskell while feeding to it a string as input. That is, I want a function like system' :: String -> String -> IO ExitCode such that system' cmd inp would be equivalent to first writing inp to a file, say "temp", and then calling system (cmd ++ " < temp") Of course, without actually creating that temporary file and having to clean it up afterwards. Does such a system' exist? Thanks, Janis. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

5 7

Re[10]: [Haskell-cafe] Climbing up the shootout...
by Bulat Ziganshin 23 Sep '08

23 Sep '08

Hello Donnie, Tuesday, September 23, 2008, 7:16:04 PM, you wrote: > I don't understand why you are willing to criticize GHC, but > unwilling to help improve GHC. Personally, I think it is a waste of > everyone's time for you to just complain about GHC without offering > suggestions on how to improve GHC -- What is the point? i don't criticize nor complain. haskell is much more higher-level language than C and that's the reason why it's slower. i just cold down heroes that lie to novices saying that Haskell is as fast or even faster than C. if i will say that Ford is slower than F1 cars, is it complaints or critics? :) when i worked on high-speed Haskell libs, i helped GHC team a bit by showing concrete cases. now i just don't work in this area so i have a little to offer ps: xposted to cafe -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0

XML (HXML) parsing :: GHC 6.8.3 space leak from 2000
by Lev Walkin 23 Sep '08

23 Sep '08

Recently I had to process some multi-megabyte XML files. Tried a few Haskell XML parsers (HaXML, HXT, HXML) but all of them were exhibiting very pronounced space leaks, and all but HXML were too strict for my input. Judging by the code and stated objectives, Joe English's HXML (0.2, circa 2003) looked more promising for hacking around so I tried to figure out the space leak problem. It wasn't too long to find out the source of a problem, the buildTree function in TreeBuild.hs. In fact, the very annotation to that function reads as follows: -- %%% There is apparently a space leak here, but I can't find it. -- %%% Update 28 Feb 2000: There is a leak, but it's fixed -- %%% by a well-known GC implementation technique. Hugs 98 happens -- %%% not to implement this technique, but STG Hugs (and most other -- %%% Haskell systems) do implement it. -- %%% Thanks to Simon Peyton-Jones, Malcolm Wallace, Colin Runcinman -- %%% Mark Jones, and others for investigating this. And there's some more in the accompanying documentation: + Under Hugs 98 only, suffers a serious space fault. I wondered why would a contemporary GHC 6.8.3 exhibit such a leak? After all, the technique was known in 2000 (and afir by Wadler in '87) and one would assume Joe English's reference to "most other Haskell systems" ought to mean GHC. But here we are, in 2008 I still can't get HXML to not to leak like a hose while lazily parsing my file. In fact, I can't get my 45-megabyte file parsed on my 1GB RAM system without swapping. So I went ahead and extracted the code and stripped all XML related junk to reproduce the problem with a minimal test case. Attached please find a single tree.hs module which is just sufficient to demonstrate a memory leak. Here's a culprit function: data TreeEvent = Start String -- Branch off a new subtree | Stop -- Stop branching and return 1 level | Leaf String -- A simple leaf without children deriving Show -- Lazily build a tree out of a sequence of tree-building events build :: [TreeEvent] -> ([UnconsumedEvent], [Tree String]) build (Start str : es) = let (es', subnodes) = build es (spill, siblings) = build es' in (spill, (Tree str subnodes : siblings)) build (Leaf str : es) = let (spill, siblings) = build es in (spill, Tree str [] : siblings) build (Stop : es) = (es, []) build [] = ([], []) In fact, the attached module implements almost verbatim the code from an old Joe's request (circa 2000): http://www.cse.unsw.edu.au/~dons/haskell-1990-2000/msg06086.html but my version is a bit more self-sufficient for the new folks who'd like to quickly test it on their system. Am I really ignorant of some important GHC optimization options (tried -O2/-O3), or is this indeed a serious problem to tackle? -- Lev Walkin vlm(a)lionet.info module Main where -- A simple tree to hold hierarchial XML-like data structure data Tree a = Tree a [Tree a] deriving Show -- A member of the event sequence which attempts to build a tree. -- For example, the following sequence -- [Start "top", Leaf "leaf", Start "sub", Stop, Stop] -- should correspond to the following tree: -- Tree "top" [Tree "leaf" [], Tree "sub" []] data TreeEvent = Start String -- Branch off a new subtree | Stop -- Stop branching and return 1 level | Leaf String -- A simple leaf without children deriving Show -- Lazy printing of an infinite tree building process main = print . snd . build $ Start "top" : cycle [Leaf "sub"] -- Convert a stream of tree building events -- into a list of unconsumed events and a constructed tree body. type UnconsumedEvent = TreeEvent -- Alias for program documentation build :: [TreeEvent] -> ([UnconsumedEvent], [Tree String]) build (Start str : es) = let (es', subnodes) = build es (spill, siblings) = build es' in (spill, (Tree str subnodes : siblings)) build (Leaf str : es) = let (spill, siblings) = build es in (spill, Tree str [] : siblings) build (Stop : es) = (es, []) build [] = ([], []) -- Stricter version of build, never terminates on infinite input, -- but exhibits no space leaks whatsoever. build' f (Start str : es) = let (es', subnodes) = build' id es in build' ((Tree str subnodes) :) es' build' f (Leaf str : es) = build' ((Tree str []) :) es build' f (Stop : es) = (es, f []) build' f [] = ([], f [])

4 7