July 2007 - Haskell-Cafe

Minim interpreter
by Jon Harrop 23 Jul '07

23 Jul '07

Anyone care to code up a Haskell implementation of this trivial interpreter for comparison: http://groups.google.co.uk/group/comp.lang.lisp/browse_frm/thread/7b1ab36f5… -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

5 9

Re: Genuine Eratosthenes sieve [Was: Optimization fun]
by Jens Blanck 23 Jul '07

23 Jul '07

> > The point about "Eratosthenes's sieve" is that it does not specify > algorithmically how to find the next number to be crossed. It does not > even define how to store (crossed) numbers, it stores them "on paper". But , I believe that Eratosthenes's sieve does specify how to store numbers and how to find the next to cross out. This is how I remember it: 0 List the numbers from 2 onwards. 1 Take first uncrossed number, say p. 2 Cross every pth number from there on (crossed or not). 3 Repeat from 1. That "crossed or not" appears above makes repeated filters very tricky. It is trivial with a mutable array, but that is not the preferred way so one needs to somehow merge the crossing out lists. I haven't looked at it really, but being sorted lists I would have thought that this merger would be easy without resorting to things like priority queues, could someone point this out to me? The above mayeasily be optimised to only listing odd numbers (still cross out every pth number in the list), and much less importantly by starting from whereever p*p is. Jens

12 22

Frustrating experience of a wannabe contributor
by Andreas Marth 23 Jul '07

23 Jul '07

Today I had 2 hours time and thought I might contribute to the haskell community. The topic I thought I might be able to give some hints is about creating DLLs. So I went to www.haskell.org which redirected me to the wiki www.haskell.org/haskellwiki/Haskell. So I entered "DLL" into the search to find what is already there and thus began the unpleasant experience. There was nothing in the search result. So I tried to find a place where it might have posted or at least fit into. That was the next step into nowhere. There is an entry "Contributing to this site" which leads to http://www.haskell.org/haskellwiki/HaskellWiki:Contributing, but thats gives zero directions where to put what or how to contribute efficiently. There are two other categories under "Learning Haskell": "Wiki articles" and "Blog articles". After going to "Blog articles" it was clear that it was not the right place either. So I went to "Wiki articles" (http://www.haskell.org/haskellwiki/Category:Haskell) which had such interesting subcategories as "Orphaned projects" and "News". (Remember this is under "Learning Haskell".) At this point I dicided that I might eventually post here under "Tutorials", but first try to find out was is already there. With there I meant the knowledge in the mailing lists. So I went to http://www.haskell.org/haskellwiki/Mailing_lists and there to the archives http://www.haskell.org/pipermail/haskell/ and http://www.haskell.org/pipermail/haskell-cafe/. Unfortunately you cant search this. So I went back and after reading through the mailing list page again went to http://www.mail-archive.com/haskell@haskell.org/index.html. That is the place where you can search the archive. Unfortunately you get the results in a totally mixed up order. When you click on the "Date" link you get it sorted, but it is not your search that is sorted it is the whole archive that is sorted. If you search again you get the same mixed up result as before. So it is not possible t get your search results sorted. (I had a quick check at "refine search" link (http://www.mail-archive.com/faq.html#search) but that gives me only the syntax for different filters but no sorting.) That was the time where I decided it might be best to write this experience down to maybe give some impulses to change. I did a last search on the haskell wiki for "create" as I thought the would be something that would be used in the DLL context and sure enough that generates 133 results and 2 of them are about DLLs (http://www.haskell.org/haskellwiki/GHC/FAQ and http://www.haskell.org/haskellwiki/GHC/Using_the_FFI) So it is not that there isn't anything about DLLs on the wiki it just doesn't find it. (By the way http://www.haskell.org/haskellwiki/GHC/FAQ links to http://www.haskell.org/ghc/docs/latest/html/users_guide/win32-dlls.html#win3 2-dlls-foreign wich has a typo for generations but is not editable.) If that is the experience someone gets early on in his haskell adventure he might very well get frustrated. So what to do? 1.) make the wiki search function return all documents containig the search term 2.) create a USEFUL search function for the mailing archives 3.) consider creating a new wiki topic "Problems and solutions working with haskell" I am especially woried about the unusable information in the mailing list archives. We have a great community here and lots of wonderful information was exchanged here but it is not accesible right now! Sorry for the long post I hope it is useful in one way or another. PS: I am in this community for a few years already so this hassle didn't drive me away from haskell, but I must say that similar experiences drove me away from a few haskell projects I had interests in (wxHaskell comes to mind). And it might also be a good idea to have a category "Fata morgana of solved problems" or so. What would qualify? COM interaction, HDirect and from the mailing list today: haskell_mod. An early move of a project into that category might a) stipulate a change of maintainer ship early enough before to much knowledge is lost and b) gives a clear warning that things might be more difficult than all the research papers imply (see COM integration).

9 15

Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)
by Dave Bayer 23 Jul '07

23 Jul '07

As an exercise, trying to understand the beautiful paper Stream Fusion From Lists to Streams to Nothing at All Duncan Coutts, Roman Leshchinskiy and Don Stewart http://www.cse.unsw.edu.au/~dons/papers/CLS07.html http://www.cse.unsw.edu.au/~dons/streams.html I recoded my prime sieve using a pared down version of their Stream datatype; this is the simplest version I could write that achieves a significant speedup. My reaction to their paper was, if streams are better internally than lists, why not code directly in streams? Lists enjoy a serious notational advantage in Haskell, but one could imagine a language where the list notation was reserved for stream semantics. My sieve was spending half its time in "merge", so I made only the changes necessary to convert "merge" to use streams. My streams are infinite, and "merge" can be written to not use Skip, so Step goes away. Even though "nextx" and "nexty" only have one case now, using case statements is significantly faster than using let or where clauses. I'm imagining that I read about this somewhere, but if I did, it didn't sink in until I was tuning this code. I don't know if this is related to fusion optimization, or a general effect. The timings are > [Integer] -O2 1*10^6 2*10^6 3*10^6 4*10^6 5*10^6 > --------------------------------------------------------- > ONeillPrimes | 3.338 | 7.320 | 11.911 | 18.225 | 21.785 > StreamPrimes | 3.867 | 8.405 | 13.656 | 21.542 | 37.640 > BayerPrimes | 3.960 | 8.940 | 18.528 | 33.221 | 38.568 Here is the code: > {-# OPTIONS_GHC -fglasgow-exts #-} > > module StreamPrimes (primes) where > > -- stream code > > data Stream a = forall s. Stream (s -> (a,s)) s > data AStream a = A a (AStream a) | B (Stream a) > > stream :: [a] -> Stream a > stream xs = Stream next xs > where > next [] = undefined > next (x:xt) = (x,xt) > > astream :: [a] -> AStream a > astream [] = undefined > astream (x:xt) = A x $ B $ stream xt > > merge :: Ord a => Stream a -> Stream a -> Stream a > merge (Stream nextx vs) (Stream nexty ws) = > Stream next (vt,ws,Left v) > where > (v,vt) = nextx vs > next (xs,ys,Left x) = > case nexty ys of > (y,yt) -> > if x < y > then (x,(xs,yt,Right y)) > else (y,(xs,yt,Left x)) > next (xs,ys,Right y) = > case nextx xs of > (x,xt) -> > if x < y > then (x,(xt,ys,Right y)) > else (y,(xt,ys,Left x)) > > mergeA :: Ord a => AStream a -> AStream a -> AStream a > mergeA (A x xt) ys = A x (mergeA xt ys) > mergeA (B xs) ys = mergeB xs ys > > mergeB :: Ord a => Stream a -> AStream a -> AStream a > mergeB s@(Stream next xs) ys@(A y yt) = > case next xs of > (x,xt) -> > if x < y > then A x (mergeB (Stream next xt) ys) > else A y (mergeB s yt) > mergeB xs (B ys) = B $ merge xs ys > > -- Code for venturi :: Ord a => [[a]] -> [a] > > root :: Ord a => AStream a -> [AStream a] -> [a] > root (A x xt) yss = x : (root xt yss) > root (B xs) (ys:yst) = root (mergeB xs ys) yst > root _ _ = undefined > > pair :: Ord a => [AStream a] -> [AStream a] > pair (x:y:xt) = mergeA x y : (pair xt) > pair _ = undefined > > group :: Ord a => [AStream a] -> [AStream a] > group (x:xt) = x : (group $ pair xt) > group _ = undefined > > venturi :: Ord a => [[a]] -> [a] > venturi (x:xt) = root (astream x) $ group $ map astream xt > venturi _ = undefined > > -- Code for primes :: Integral a => [a] > > diff :: Ord a => [a] -> [a] -> [a] > diff xs@(x:xt) ys@(y:yt) = case compare x y of > LT -> x : (diff xt ys) > EQ -> (diff xt yt) > GT -> (diff xs yt) > diff _ _ = undefined > > trim :: Integral a => a -> [a] -> [a] > trim p = let f m x = mod x m /= 0 in filter (f p) > > seed :: Integral a => [a] > seed = [2,3,5,7,11,13,17] > > wheel :: Integral a => [a] > wheel = drop 1 [ m*j + k | j <- [0..], k <- ws ] > where m = foldr1 (*) seed > ws = foldr trim [1..m] seed > > multiples :: Integral a => [a] -> [[a]] > multiples ws = map fst $ tail $ iterate g ([], ws) > where g (_,ps@(p:pt)) = ([ m*p | m <- ps ], trim p pt) > g _ = undefined > > primes :: Integral a => [a] > primes = seed ++ (diff wheel $ venturi $ multiples wheel)

1 0

Equational Reasoning goes wrong
by Neil Mitchell 23 Jul '07

23 Jul '07

Hi Haskell is known for its power at equational reasoning - being able to treat a program like a set of theorems. For example: break g = span (not . g) Which means we can replace: f = span (not . g) with: f = break g by doing the opposite of inlining, and we still have a valid program. However, if we use the rule that "anywhere we encounter span (not . g) we can replace it with break g" then we can redefine break as: break g = break g Clearly this went wrong! Is the folding back rule true in general, only in specific cases, or only modulo termination? Thanks Neil

11 10

Practise fingerspelling with Haskell! (Code cleanup request)
by Dougal Stanton 23 Jul '07

23 Jul '07

The following is a slap-dash program for generating a list of pairs of words which differ by, at most, one letter. It's quite verbose at the moment, because (a) that was the way I wrote it, a snippet at a time, and (b) I lack the wit to make it shorter. Can anyone recommend ways to make this program more efficient/neat/elegant? It runs in decent time on my machine, but it's not exceedingly pretty and I'm sure it can be made shorter too. (The full thing can be found at <http://193.219.108.225/code/fingerspell/> if you want to pull in a working version to play with. The purpose of the program is for a game to practise fingerspelling when learning sign language. More on that here: <http://brokenhut.livejournal.com/265471.html>.) Cheers, D. ---- edited highlights below ---- -- Number of letters difference between two words. difference :: Pair -> Int difference = length . filter (==False) . uncurry (zipWith (==)) -- Keep only pairs that differ by at most -- one letter difference. keepOneDiff :: PairSet -> PairSet keepOneDiff = map snd . filter (\x -> (fst x) < 2) . map (difference &&& id) -- Pairs of words of equal length, sorted to reduce -- duplicates of (a,b), (b,a) type. They shouldn't -- be completely eradicated because part of the game -- is to spot when they;re the same word. listPairs :: WordSet -> PairSet listPairs ws = [ (w, w') | w <- ws, w' <- ws, length w == length w', w <= w' ] -- Take N pairs of words which are the same -- length and differ by at most one letter. wordpairs :: Int -> WordSet -> PairSet wordpairs n = take n . keepOneDiff . listPairs fingerspell wl p = do wordfile <- words `liftM` readFile "/usr/share/dict/words" mapM_ pretty $ wordpairs p $ filter (requirements) wordfile -- Make sure all the words are of the required length and are -- just made up of letters, not punctuation. where requirements w = length w == wl && all (isAlpha) w pretty (x,y) = putStrLn $ x ++ ", " ++ y

5 10

Haskell Weekly News: July 23, 2007
by dons＠cse.unsw.edu.au 23 Jul '07

23 Jul '07

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20070723 Issue 63 - July 23, 2007 --------------------------------------------------------------------------- Welcome to issue 63 of HWN, a weekly newsletter covering developments in the [1]Haskell community. This week, the HWN rises zombie-like from its repository, as your friendly HWN editor tries to get his PhD finished. This bumper issue is filled out with 100 new Haskell blog articles and dozens of new libraries! 1. http://haskell.org/ Announcements Learn Haskell in 10 minutes. Chris Smith [2]prepared a new tutorial on the basics of Haskell 2. http://haskell.org/haskellwiki/Learn_Haskell_in_10_minutes Haskell Program Coverage 0.4. Andy Gill [3]announced release 0.4 of Hpc, a tool for Haskell developers. Hpc is a tool-kit to record and display Haskell Program Coverage. Hpc includes tools that instrument Haskell programs to record program coverage, run instrumented programs, and display the coverage information obtained. 3. http://article.gmane.org/gmane.comp.lang.haskell.general/15381 Uniplate 1.0. Neil Mitchell [4]announced Uniplate (formerly known as Play), a library for boilerplate removal requiring only Haskell 98 (for normal use) and optionally multi-parameter type classes (for more advanced features). 4. http://article.gmane.org/gmane.comp.lang.haskell.general/15366 Atom: Hardware description in Haskell. Tom Hawkins [5]announced Atom, a high-level hardware description language embedded in Haskell that compiles conditional term rewriting systems into conventional HDL. 5. http://article.gmane.org/gmane.comp.lang.haskell.general/15341 Catch. Neil Mitchell [6]announced a pattern-match checker for Haskell, named Catch. Do you sometimes encounter the dreaded 'pattern match failure: head' message? Do you have incomplete patterns which sometimes fail? Do you have incomplete patterns which you know don't fail, but still get compiler warnings about them? Would you like to statically ensure the absence of all calls to error? This is what Catch helps ... catch! 6. http://article.gmane.org/gmane.comp.lang.haskell.general/15334 Haskell Communities and Activities Report. Andres Loeh [7]announced that the Haskell Communities and Activities Report is now available, covering the increasingly diverse groups, projects and individuals working on, with, or inspired by Haskell. 7. http://article.gmane.org/gmane.comp.lang.haskell.general/15302 The Reduceron. Matthew Naylor [8]announced the Reduceron, a processor for executing Haskell programs on FPGA with the aim of exploring how custom architectural features can improve the speed in which Haskell functions are evaluated. Being described entirely in Haskell (using Lava), the Reduceron also serves as an interesting application of functional languages to the design of complex control circuits such as processors. 8. http://article.gmane.org/gmane.comp.lang.haskell.general/15301 Data.Derive. Neil Mitchell [9]announced Data.Derive, a library and a tool for deriving instances for Haskell programs. It is designed to work with custom derivations, SYB and Template Haskell mechanisms. The tool requires GHC, but the generated code is portable to all compilers. We see this tool as a competitor to DrIFT. 9. http://article.gmane.org/gmane.comp.lang.haskell.general/15292 Piffle, a packet filter language. Jaap Weel [10]announced Piffle, a compiler for a packet filter language in Haskell: a good example of how Haskell can be used in an application domain (low level computer networking) where people tend to use C for everything, including writing compilers. 10. http://article.gmane.org/gmane.comp.lang.haskell.general/15290 Towards a Programming Language Nirvana. Simon Peyton-Jones [11]appears on video, talking about the Haskell path to programming language Nirvana 11. http://channel9.msdn.com/showpost.aspx?postid=326762 Yi 0.2. Jean-Philippe Bernardy [12]announced the 0.2.0 release of the Yi editor. Yi is a text editor written and extensible in Haskell. The goal of Yi is to provide a flexible, powerful and correct editor core dynamically scriptable in Haskell. Yi si also a Haskell interpreter, very much like emacs is a Lisp interpreter, this makes really easy to dynamically hack, experiment and modify Yi. All tools and goodies written in haskell are also readily available from the editor. This is implemented by binding to the GHC API. 12. http://article.gmane.org/gmane.comp.lang.haskell.general/15260 Foreign.AppleScript. Wouter Swierstra [13]announced a library for compiling and executing AppleScript from Haskell. AppleScript is a scripting language available on all modern Apple computers. It can be used to script most applications on running on MacOS X. 13. http://article.gmane.org/gmane.comp.lang.haskell.general/15246 Asterisk Gateway Interface. Jeremy Shaw [14]uploaded a simple AGI interface to [15]hackage. For more about Asterix, see [16]here. 14. http://article.gmane.org/gmane.comp.lang.haskell.general/15245 15. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/AGI 16. http://www.voip-info.org/wiki-Asterisk+AGI Harpy. Dirk Kleeblatt [17]announced Harpy, a library for run-time code generation of x86 machine code. It provides not only a low level interface to code generation operations, but also a convenient domain specific language for machine code fragments, a collection of code generation combinators and a disassembler. [18]Lennart Augustsson has written a series of articles demonstrating its use for fast EDSLs. 17. http://article.gmane.org/gmane.comp.lang.haskell.general/15237 18. http://haskell.org/haskellwiki/Blog_articles/EDSLs Yaml Reference. Gaal Yahas [19]announced a Haskell (Cabal) package containing the YAML spec productions wrapped in Haskell magic to convert them to an executable parser. The parser is streaming. It isn't intended to serve as a basis for a YAML tool chain; instead it is meant to serve as a reference implementation of the spec. 19. http://ben-kiki.org/oren/YamlReference/ Haskell' This section covers the [20]Haskell' standardisation process. * [21]Dependent types * [22]Monomorphism restriction * [23]Operator backquoting * [24]Type signatures in export lists * [25]Pragma syntax * [26]inits is too strict * [27]Module system initialisation * [28]Polymorphic strict fields 20. http://hackage.haskell.org/trac/haskell-prime 21. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2282 22. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2262 23. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2247 24. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2240 25. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2238 26. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2232 27. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2212 28. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2192 Libraries This week's proposals and extensions to the [29]standard libraries. * [30]Add exeExtension to System.Info * [31]The drive functions in the filepath package * [32]Optimising words * [33]Add dropPrefix 29. http://haskell.org/haskellwiki/Library_submissions 30. http://thread.gmane.org/gmane.comp.lang.haskell.libraries/7155 31. http://thread.gmane.org/gmane.comp.lang.haskell.libraries/7129 32. http://thread.gmane.org/gmane.comp.lang.haskell.libraries/7094 33. http://thread.gmane.org/gmane.comp.lang.haskell.libraries/7032 Hackage This week's new libraries in [34]the Hackage library database. 34. http://hackage.haskell.org/ * HsOpenSSL-0.1. Masatake Daimon [35]HsOpenSSL 0.1, OpenSSL binding for Haskell 35. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HsOpenSSL-0.1 * Emping-0.3. Hans Van Thiel [36]Emping derives heuristic rules from nominal data 36. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Emping-0.3 * parsely-0.1. Samuel Bronson [37]parsely, Typeclasses for parsing monads, and some instances 37. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/parsely-0.1 * sessions-2007.7.15. Matthew Sackman [38]sessions, Session Types for Haskell 38. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/sessions-2007.7.… * CC-delcont-0.1. Dan Doel [39]CC-delcont1, An implementation of multi-prompt delimited continuations 39. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/CC-delcont-0.1 * gd-3000.3.0. Bjorn Bringert [40]gd, A binding to the GD graphics library 40. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/gd-3000.3.0 * StrategyLib-4.0.0.0. Samuel Bronson [41]StrategyLib, Strafunski's StrategyLib 41. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/StrategyLib-4.0.… * ports-0.4.3.2. Don Stewart [42]ports, concurrent and distributed Haskell programming in the IO monad without relying on mutable variables. 42. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ports-0.4.3.2 * Finance-Quote-Yahoo-0.1. Brad Clawsie [43]Yahoo-0.1, Obtain quote data from finance.yahoo.com 43. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Finance-Quote-Ya… * logict-0.2. Dan Doel [44]LogicT, A continuation-based, backtracking, logic programming monad. 44. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/logict-0.2.1 * utf8-string-0.1. Eric Mertens [45]utf8-string, Support for reading and writing UTF8 Strings 45. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/utf8-string-0.1 * type-int-0.4. Edward Kmett [46]type-int, Type level 2s- and 16s- complement Integers (positive and negative), Booleans, Ord and Eq 46. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/type-int-0.4 * cgi-3001.1.5. BjornBringert [47]cgi-3001, a Haskell library for writing CGI programs 47. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/cgi-3001.1.5 * xmobar-0.6. AndreaRossato [48]xmobar, Xmobar is a minimal status bar for the XMonad Window Manager 48. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/xmobar-0.6 * monad-param-0.0.2. EdwardKmett [49]monad-param, parameterized monads 49. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/monad-param-0.0.2 * dfsbuild-1.0.1. JohnGoerzen [50]dfsbuild, dfsbuild is the program used to create the Debian From Scratch CD image. 50. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dfsbuild-1.0.1 Conference roundup AngloHaskell is [51]coming up in Cambridge, August 10-11 Haskell Hackathon 07 II. Hac07 is [52]coming up in Freiburg, Oct 5-7 51. http://haskell.org/haskellwiki/AngloHaskell 52. http://article.gmane.org/gmane.comp.lang.haskell.general/15416 Blog noise [53]Haskell news from the [54]blogosphere. There really has been 100 new articles since the last issue! 53. http://planet.haskell.org/ 54. http://haskell.org/haskellwiki/Blog_articles * [55]ONLamp: An Introduction to Haskell * [56]ONLamp: An Introduction to Haskell: Part 2: Pure Functions * [57]Knuth-Morris-Pratt in Haskell * [58]Towards Better Error Handling * [59]Dynamic epsilons in Haskell with a bit of type hackery * [60]Null pointers vs None vs Maybe * [61]Lambda calculus in alligator form * [62]Learning Haskell databases * [63]liskell.org * [64]Norvig's spell checker and idiomatic Haskell * [65]Trying out functional programming * [66]Trying out functional programming: part 2 * [67]Roll Your Own Window Manager: Tracking Focus with a Zipper * [68]You Lazy Thunk! * [69]What's a monad? * [70]Erlang: how syntax can discourage good programming practices * [71]Regular expressions in Haskell * [72]Producing diagrams * [73]Notes on Chapter 2 of SOE * [74]Xmonad and KDE on kubuntu feisty * [75]Does XMonad crash? On proving pattern coverage with Catch 55. http://www.onlamp.com/pub/a/onlamp/2007/05/21/an-introduction-to-haskell---… 56. http://www.onlamp.com/pub/a/onlamp/2007/07/12/introduction-to-haskell-pure-… 57. http://twan.home.fmf.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell.details 58. http://nominolo.blogspot.com/2007/05/towards-better-error-handling.html 59. http://augustss.blogspot.com/2007/05/i-was-asked-if-my-fixed-number-module.… 60. http://lukeplant.me.uk/blog.php?id=1107301659 61. http://worrydream.com/AlligatorEggs/ 62. http://davblog48.blogspot.com/2007/05/trying-to-learn-haskell-database.html 63. http://liskell.org/ 64. http://www.serpentine.com/blog/2007/05/14/norvigs-spell-checker-and-idiomat… 65. http://concise-software.blogspot.com/2007/05/trying-out-functional-programm… 66. http://concise-software.blogspot.com/2007/05/trying-out-functional-programm… 67. http://cgi.cse.unsw.edu.au/~dons/blog/2007/05/17#xmonad_part1b_zipper 68. http://blog.tmorris.net/you-lazy-thunk/ 69. http://unenterprise.blogspot.com/2007/05/whats-monad.html 70. http://www.acooke.org/cute/ErlangsSyn0.html 71. http://michaelspeer.blogspot.com/2007/05/initial-code-at-regular-expression… 72. http://pozorvlak.livejournal.com/55568.html 73. http://osfameron.vox.com/library/post/notes-on-chapter-2-of-soe.html 74. http://totherme.livejournal.com/4154.html 75. http://neilmitchell.blogspot.com/2007/05/does-xmonad-crash.html * [76]A simple echo server * [77]More deforestation * [78]State of the computer book market * [79]Pragmatic Haskell * [80]Analysing Haskell book sales * [81]Real-world Haskell: it's time * [82]Real-World Haskell * [83]Tim O'Reilly: Real World Haskell title under development * [84]Haskell: Ready for Prime Time * [85]Haskell's time has come * [86]Haskell Book in the Making! * [87]Finally, a book on how Haskell can be applied to 'real-world' problems! * [88]Haskell - Ready for the mainstream? * [89]Great news in the Haskell Books front * [90]Practical reasons for learning some functional languages * [91]Preconditions on XMonad * [92]Xmonad does status bars right by not doing them at all * [93]Perfect Programming Languages: Part 1, Syntactic Similarity * [94]Haskell diary, day 1 * [95]A functional programmer stole my job 76. http://abstractabsurd.blogspot.com/2007/05/couple-of-silly-examples.html 77. http://neilmitchell.blogspot.com/2007/05/13-faster-than-ghc.html 78. http://radar.oreilly.com/archives/2007/05/state_of_the_co_10.html 79. http://blogs.nubgames.com/code/?p=23 80. http://notes-on-haskell.blogspot.com/2007/05/analyzing-book-sales.html 81. http://www.realworldhaskell.org/blog/2007/05/23/real-world-haskell-its-time/ 82. http://changelog.complete.org/posts/612-Real-World-Haskell.html 83. http://radar.oreilly.com/archives/2007/05/real_world_hask.html 84. http://notes-on-haskell.blogspot.com/2007/05/haskell-ready-for-prime-time.h… 85. http://telematique.typepad.com/twf/2007/05/haskells_time_h.html 86. http://triple.aeoth.net/2007/05/25/haskell-book-in-the-making/ 87. http://binil.wordpress.com/2007/05/24/finally-a-book-on-how-haskell-can-be-… 88. http://blog.uncommons.org/?p=23 89. http://codemiscellany.blogspot.com/2007/05/great-news-in-haskell-books-fron… 90. http://kevinoncode.blogspot.com/2007/05/functional-languages-on-horizon.html 91. http://neilmitchell.blogspot.com/2007/05/preconditions-on-xmonad.html 92. http://gimbo.org.uk/blog/2007/05/30/xmonad-does-status-bars-right/ 93. http://disparatemathematician.blogspot.com/2007/05/perfect-programming-lang… 94. http://firstian.blogspot.com/2007/05/haskell-diary-day-1.html 95. http://ocamlnews.blogspot.com/2007/05/functional-programmer-stole-my-job.ht… * [96]Haskell incarnate: robots and Haskell * [97]Chapter 3 of SOE * [98]Implementing Network.HTTP with ByteStrings * [99]Signal handling in Haskell * [100]ML, Haskell and Coq * [101]Djinn, Coq, Monad and a bit of Haskell * [102]A beginner with Parsec * [103]A perceptron in Haskell * [104]Piffle: a packet filter language with a compiler written in Haskell * [105]OriDSEL: a DSL for origami * [106]Joel's compiler in OCaml and Haskell * [107]JGraph in Haskell * [108]A neural network in Haskell * [109]Scientific.Dimension: Type Arithmetic and Physical Units in Haskell * [110]Flattening an array of arrays * [111]Travelling Salesman Problem: Introduction (in Haskell) * [112]Parallel programming, functional vs. imperative languages * [113]The impossible is only possible sometimes * [114]More Scheming with Haskell * [115]How to write tolerably efficient optimzation code without really trying... 96. http://sigfpe.blogspot.com/2007/05/haskell-incarnate.html 97. http://osfameron.vox.com/library/post/chapter-3-soe.html 98. http://nominolo.blogspot.com/2007/05/networkhttp-bytestrings.html 99. http://therning.org/magnus/archives/285 100. http://www.rubrication.net/2007/04/21/how-a-real-module-system-should-work/ 101. http://www.alpheccar.org/en/posts/show/70 102. http://davblog48.blogspot.com/2007/05/parsec.html 103. http://jpmoresmau.blogspot.com/2007/05/perceptron-in-haskell.html 104. http://usr-share-morlock.blogspot.com/2007/05/piffle-packet-filter-language… 105. http://www.gaetanocaruana.com/2007/05/25/embedding-origami-constructs/ 106. http://wagerlabs.com/2007/5/26/who-let-the-dogs-out 107. http://equi-nox.blogspot.com/2007/05/jgraph-in-haskell.html 108. http://jpmoresmau.blogspot.com/2007/06/very-dumb-neural-network-in-haskell.… 109. http://liftm.wordpress.com/2007/06/03/scientificdimension-type-arithmetic-a… 110. http://julipedia.blogspot.com/2007/06/flattening-array-of-arrays.html 111. http://illicittech.blogspot.com/2007/06/travelling-salesman-problem.html 112. http://enfranchisedmind.com/blog/archive/2007/06/10/251 113. http://michaelspeer.blogspot.com/2007/06/impossible-is-only-possible-someti… 114. http://sami.samhuri.net/2007/6/14/more-scheming-with-haskell 115. http://sigfpe.blogspot.com/2007/06/how-to-write-tolerably-efficient.html * [116]Harpy: generating machine code from a Haskell * [117]A little DSL embedded in Haskell * [118]Generating more code with Harpy * [119]Representing DSL expressions in Haskell * [120]Disassembly * [121]A simple embedded compiler in Haskell * [122]Functional composition * [123]Beautiful Haskell implementation of a power set * [124]Constructability, Uncountability, and w-Haskell * [125]Uncountable Ordinals, part 2 * [126]Category Theory and Haskell 3 : Algebras and Monads * [127]The Supermarket Pricing Kata in Haskell * [128]Implementing a type for partial values * [129]Appreciating Constraint Programming * [130]Continuing with continuations in Haskell * [131]Find the Bug * [132]Haskell decision making * [133]Learning Haskell and Number Theory: The End of GCD * [134]A foray into number theory with Haskell * [135]Flatten Benchmark for Haskell 116. http://augustss.blogspot.com/2007/06/playing-with-harpy-recently-there-was.… 117. http://augustss.blogspot.com/2007/06/massive-overload-in-my-last-post-i-had… 118. http://augustss.blogspot.com/2007/06/generating-more-code-with-harpy-after.… 119. http://augustss.blogspot.com/2007/06/representing-dsl-expressions-in-haskel… 120. http://augustss.blogspot.com/2007/06/disassembly-harpy-package-also-contain… 121. http://augustss.blogspot.com/2007/06/simple-compiler-in-my-last-post-i.html 122. http://neilmitchell.blogspot.com/2007/06/functional-composition.html 123. http://community.livejournal.com/evan_tech/220036.html 124. http://blog.jbapple.com/2007/06/constructability-uncountability-and.html 125. http://blog.jbapple.com/2007/06/ordinals-part-2.html 126. http://www.alpheccar.org/en/posts/show/77 127. http://blog.moertel.com/articles/2006/04/28/the-supermarket-pricing-kata-in… 128. http://conal-elliott.blogspot.com/2007/07/implementing-type-for-partial-val… 129. http://boriken.frayser.org/wordpress/2007/07/04/appreciating-chr-constraint… 130. http://therning.org/magnus/archives/306 131. http://cdsmith.wordpress.com/2007/07/05/find-the-bug/ 132. http://realfiction.net/?q=node/123 133. http://cdsmith.wordpress.com/2007/07/05/learning-haskell-and-number-theory-… 134. http://www.akalin.cx/2007/07/06/a-foray-into-number-theory-with-haskell/ 135. http://notvincenz.blogspot.com/2007/07/flatten-benchmark.html * [136]Solving an arithmetic puzzle with Haskell * [137]Haskell DataPipe * [138]Refining my first steps with Parsec * [139]Equational Reasoning in Haskell * [140]Peano's Axioms Part I: Haskell and Type Theory, and Object Oriented Programming * [141]Making Haskell faster than C! * [142]Power serious: power series in ten one-liners * [143]Haskell for Programmers: a tutorial * [144]Parameterized Monads in Haskell * [145]Monomorphism and the unintentional fib * [146]Cohatoe - Contributing Haskell to Eclipse * [147]Getting started with HUnit * [148]A Neat Problem * [149]Parsing, CFGs, and Type Hacking * [150]Using haskell for reading raw ethernet frames * [151]A simple Haskell malware: X11 keylogger * [152]I'll have a Buchburger with fries: solving XKCD's menu puzzle 136. http://byorgey.wordpress.com/2007/06/21/solving-an-arithmetic-puzzle-with-h… 137. http://emilliken.blogspot.com/2007/07/haskell-datapipe.html 138. http://lstephen.wordpress.com/2007/06/22/refining-my-first-steps-with-parse… 139. http://neilmitchell.blogspot.com/2007/07/equational-reasoning-in-haskell.ht… 140. http://disparatemathematician.blogspot.com/2007/07/peanos-axioms-part-i-has… 141. http://neilmitchell.blogspot.com/2007/07/making-haskell-faster-than-c.html 142. http://www.cs.dartmouth.edu/~doug/powser.html 143. http://neugierig.org/software/darcs/haskell-for-programmers/haskell-for-pro… 144. http://comonad.com/reader/2007/parameterized-monads-in-haskell/ 145. http://koweycode.blogspot.com/2007/07/monomorphism-and-unintentional-fib.ht… 146. http://leiffrenzel.de/eclipse/cohatoe/ 147. http://leiffrenzel.de/papers/getting-started-with-hunit.html 148. http://cdsmith.wordpress.com/2007/07/17/a-neat-problem/ 149. http://cdsmith.wordpress.com/2007/07/19/parsing-cfgs-and-type-hacking/ 150. http://emilliken.blogspot.com/2007/07/using-haskell-for-reading-raw-etherne… 151. http://emilliken.blogspot.com/2007/07/simple-haskell-malware-x11-keylogger.… 152. http://sigfpe.blogspot.com/2007/07/ill-have-buchburger-with-fries.html Quotes of the Week * Smith's Law: Any sufficiently large test suite for a program written in a dynamic language will contain an ad-hoc, informally-specified, bug-ridden, slow, patchy implementation of half of the Haskell type system * pshaw: I think the key hook that allowed me to pass interview #2 was that I put the word 'Haskell' on my resume. * monochrom: Fear leads to uncertainty. Uncertainty leads to doubt. Doubt leads to theorem proving. * Adam Turoff: Let me start by being perfectly clear: if you are a professional programmer, then Haskell is in your future. * Apfelmus: In the end, I think that strong types is only one thing that makes Haskell programs work after compilation. The other ones are higher-order functions and *purity*. No type system can achieve what purity offers. About the Haskell Weekly News Each week, new editions are posted to [153]the Haskell mailing list as well as to [154]the Haskell Sequence and [155]Planet Haskell. [156]RSS is also available, and headlines appear on [157]haskell.org. Headlines are available as [158]PDF. To help create new editions of this newsletter, please see the [159]contributing information. Send stories to dons at cse.unsw.edu.au. The darcs repository is available at darcs get [160]http://www.cse.unsw.edu.au/~dons/code/hwn 153. http://www.haskell.org/mailman/listinfo/haskell 154. http://sequence.complete.org/ 155. http://planet.haskell.org/ 156. http://sequence.complete.org/node/feed 157. http://haskell.org/ 158. http://www.cse.unsw.edu.au/~dons/code/hwn/archives/20070723.pdf 159. http://haskell.org/haskellwiki/HWN 160. http://www.cse.unsw.edu.au/~dons/code/hwn

1 0

Speedy parsing
by Re, Joseph (IT) 22 Jul '07

22 Jul '07

I was hoping someone could direct me to material on how I might go about optimizing a small parsing program I wrote. Used for calculating differences between two files that store a hash of hashes (each line is a hash, each line has "key=value" pairs seperated by commas), the bottleneck seems to be in getting the data into memory (in a usable structure) quickly, as I'm working with extremely large files (>250,000 line, 100MB+ files are normal in size, some are quite larger, and I have to process a large number of them often). Extracting just the parsing elements of my current python implementation: FILE: compare.py > import sys > def parse(lines): > print "Parsing",len(lines),"lines..." > failed = 0 > hashes = {} > for line in lines: > try: > hash = {} > parts = line.split(",") > for part in parts: > k,v = part.split("=") > hash[k] = v > hashes[ hash["LogOffset"] ] = hash > except: > if line != "": > failed += 1 > if failed > 0: > print "[ERROR] Failed to parse:",failed,"lines" > print "...Parsing resulted in",len(hashes),"unique hashes" > return hashes > > def normalize(lines): > lineset = set() > for line in lines: > if "Type=Heartbeat" == line[0:14]: pass > elif line == "": pass > else: lineset.add( line ) #use set to get only uniques > return lineset > > def main(): > hashes = parse( normalize ( open(sys.argv[1]).readlines() )) > > if __name__ == '__main__': main() $ time python compare.py 38807lineFile Removed 52 bad lines Parsing 38807 lines... ...Parsing resulted in 38807 unique hashes real 0m3.807s user 0m3.330s sys 0m0.470s $ time python compare.py 255919lineFile Removed 0 bad lines Parsing 255919 lines... ...Parsing resulted in 255868 unique hashes real 0m30.889s user 0m23.970s sys 0m2.900s *note: profiling shows over 7.1 million calls to the split() function, to give you a good idea of the number of pairs the file contains. Once you factor in much increased filesizes, actually preforming the analysis, and running it on a few dozen files, my tests started to become quite time consuming (not to mention it takes 1GB of memory for just the 250K line files, although execution time is still much more important at the moment thanks to ram being cheap). Thusly, I figured I'd rewrite it in C, but first I wanted to give Haskell a shot, if only to see how it compared to python (hoping maybe I could convince my boss to let me use it more often if the results were good). The first thing I wanted to check was if parsec was a viable option. Without even putting the data into lists/maps, I found it too slow. FILE: compare_parsec.hs > {-# OPTIONS_GHC -O2 #-} > module Main where > import System.Environment (getArgs) > import Text.ParserCombinators.Parsec > > csv = do x <- record `sepEndBy` many1 (oneOf "\n") > eof > return x > record = field `sepBy` char ',' > field = many (anyToken) > > main = do > ~[filename] <- getArgs > putStrLn "Parsing log..." > res <- parseFromFile csv filename > case res of > Left err -> print err > Right xs -> putStrLn "...Success" $ time ./compare_parsec 38807lineFile Parsing log... ...Success real 0m13.809s user 0m11.560s sys 0m2.180s $ time ./compare_parsec 255919lineFile Parsing log... ...Success real 1m28.983s user 1m8.480s sys 0m9.530s This, sadly, is significantly worse than the python code above. Perhaps someone here can offer advice on more efficient use of parsec? Unfortunately I don't have profiling libraries for parsec available on this machine, nor have I had any luck finding material on the web. After this, I tried doing my own parsing, since the format is strict and regular. I tried pushing it to lists (fast, not very usable) and maps (much easier for the analysis stage and what the python code does, but much worse speedwise). FILE: compare_lists.hs > {-# OPTIONS_GHC -O2 -fglasgow-exts #-} > module Main where > import System.Environment (getArgs) > type Field = (String,String) > type Record = [Field] > type Log = [Record] > > main = do > ~[filename1] <- getArgs > file1 <- readFile filename1 > putStrLn "Parsing file1..." > let data1 = parseLog file1 > print data1 > putStrLn "...Done" > > -- parse file > parseLog :: String -> Log > parseLog log = foldr f [] (lines log) > where f "" a = a > f "\n" a = a > f x a = (parseRecord x):a > -- parse record > parseRecord :: String -> Record > parseRecord record = foldr (\x a -> (parseField x):a) [] (split ',' record) > -- parse field > -- no error detection/handling now > parseField :: String -> Field > parseField s = (takeWhile isntCharEq s, tail $ dropWhile isntCharEq s) > > isntCharEq :: Char -> Bool > isntCharEq '=' = False > isntCharEq _ = True > > split :: Eq a => a -> [a] -> [[a]] > split delim = foldr f [[]] > where > f x rest@(r:rs) > | x == delim = [] : rest > | otherwise = (x:r) : rs I wasn't sure the best way to force evaluation on this, so I opt'd to print it and direct stdout to /dev/null (and noted how long a program that just read and print the same file to /dev/null took as well). Any better suggestions are welcome. $ time ./compare_lists 38807lineFile > /dev/null real 0m4.958s (0m0.445s for the putStrLn $ readFile program) user 0m4.830s sys 0m0.110s $ time ./compare_lists 255919lineFile > /dev/null real 0m31.047s (0m2.620s for the putStrLn $ readFile program) user 0m30.310s sys 0m0.690s These speeds are relatively the same as python, but the data is easily usable in comparision, so finally I implemented the useful version: FILE: compare_maps.hs > {-# OPTIONS_GHC -O2 -fglasgow-exts #-} > module Main where > import qualified Data.Map as Map > import System.Environment (getArgs) > import Control.Monad > > type Field = (String,String) > type Record = Map.Map String String > type Log = Map.Map String Record > > main = do > ~[filename] <- getArgs > d <- liftM parseLog $ readFile filename > putStr $ strMaps d > -- parse file > parseLog :: String -> Log > parseLog logstr = foldr f Map.empty (lines logstr) > where f "" a = a > f "\n" a = a > f x a = let (k,v) = parseRecord1 x > in Map.insert k v a > -- parse record line > parseRecord1 :: String -> (String,Record) > parseRecord1 recordstr = do let r = parseRecord recordstr > (idRecord r, r) > > -- extract unique id used for comparision amoungst line hashes in other files > idRecord :: Record -> String > idRecord r = case (Map.lookup "LogID" r) of > Nothing -> "ERROR" > Just id -> id > > parseRecord :: String -> Record > parseRecord recordstr = foldr f Map.empty (split ',' recordstr) > where f x a = case parseField x of > Nothing -> a > Just (k,v) -> Map.insert k v a > -- parse k=v fields > parseField :: String -> Maybe Field > parseField "" = Nothing > parseField s = Just (takeWhile isntCharEq s, tail $ dropWhile isntCharEq s) > > isntCharEq :: Char -> Bool > isntCharEq '=' = False > isntCharEq _ = True > -- map functions > strMaps = Map.fold (\x a -> (strMap x) ++ "\n" ++ a) "" > strMap = unlines . map (\(k,v) -> k ++ ":" ++ v) . Map.toAscList > -- list functions > split :: Eq a => a -> [a] -> [[a]] > split delim = foldr f [[]] > where > f x rest@(r:rs) > | x == delim = [] : rest > | otherwise = (x:r) : rs $ time ./compare_maps 38807lineFile > /dev/null real 0m24.207s (0m0.445s for the putStrLn $ readFile program) user 0m22.430s sys 0m1.680s $ time ./compare_maps 255919lineFile > /dev/null real 5m24.927s (0m2.620s for the putStrLn $ readFile program) user 5m5.240s sys 0m12.770s Until this point I had only been throwing on -O2. I believe -fvia-C is included with -O currently, and I'm not well versed enough to know what others could help me out, so I left it at that. Next I tried checking out what the garbage collector was doing (I assume the footprint is smaller than python, but that would still be quite large). Flipping on -Sstderr I saw that only a third of the time spent was doing real work (67.9% doing GC). For the 38K file: 2,794,465,788 bytes allocated in the heap 1,956,668,360 bytes copied during GC (scavenged) 21,884,948 bytes copied during GC (not scavenged) 185,541,764 bytes maximum residency (16 sample(s)) 5329 collections in generation 0 ( 9.03s) 16 collections in generation 1 ( 5.99s) 523 Mb total memory in use MUT time 7.10s ( 7.80s elapsed) GC time 15.02s ( 16.68s elapsed) Total time 22.12s ( 24.48s elapsed) %GC time 67.9% (68.1% elapsed) For the 250K file: 17,509,820,952 bytes allocated in the heap 12,270,870,276 bytes copied during GC (scavenged) 136,831,020 bytes copied during GC (not scavenged) 1,307,822,788 bytes maximum residency (21 sample(s)) 33390 collections in generation 0 (121.65s) 21 collections in generation 1 ( 42.37s) 3244 Mb total memory in use MUT time 146.25s (151.51s elapsed) GC time 164.02s (172.73s elapsed) Total time 310.27s (324.24s elapsed) %GC time 52.9% (53.3% elapsed) Not being paticularly knowledgeable in this area, I tried some options I thought were reasonable after reading the (http://www.haskell.org/ghc/docs/latest/html/users_guide/runtime-control .html#rts-options-gc). The following are with the small (38K) file. Running with a larger heap (-H) didn't seem to help: 256m 35s 512m 37s 768m 37s 1g 29s Playing with the allocation area size (-A) didn't help either: 128k 29s 256k 25s (default) 512k 23s 768k 25s 1m 23s 2m 32s 5m 32s 10m 32s The 250K file shows improvement from the little bit I've played around with defaults -> 5m24s, 33.3K collections, 53% GC time -H1g -> 4m53s, 16.8K collecctions, 56% GC time -H3g -A5m -> 4m16s total time, 3500 collections, 52% GC time -H4g -A50m -> 4m26s total time, 350 collections, 57% GC time (-H3g -A5m and -H4g -A50m give approx. 4m16s total time, 3500 collections, but still 52% GC time), so I'll try to run some more tests with different options for it, but this still isn't even remotely close to python's speed, so I assume improving the code would prove more fruitful. At this point I'm out of ideas, so I was hoping someone could identify something stupid I've done (I'm still novice of FP in general, let alone for high performance) or direct me to a guide,website,paper,library, or some other form of help. For reference, the tests above were done on an 8 proc (possibly 4 real but hyperthreaded?) 2.8ghz Xeon workstation with 16gb memory runing an SMP enabled 2.4.21-47 linux kernel and ghc 6.6.1 Thanks -- Joseph Re -------------------------------------------------------- NOTICE: If received in error, please destroy and notify sender. Sender does not intend to waive confidentiality or privilege. Use of this email is prohibited when received in error.

5 7

Ray tracer
by Andrew Coppin 22 Jul '07

22 Jul '07

The "Haskell ray tracer" seems to be a pretty standard and widely-used example program. But has anybody ever seriously tried to make a "production-grade" implementation? (I.e., one that is user-friendly, efficient, and with lots of functionallity.)

7 14

Help with IO and randomR
by Niko Korhonen 22 Jul '07

22 Jul '07

I'm writing some code to generate a dither (=noise) signal. I'm trying to generate an infinite series of noise with triangular distribution but my code hangs into an infinite loop. The problem is that I'm not very good with Haskell IO yet and I can't figure out how to write this piece of IO code without it looping infinitely. So, in short, how do I do this without getting into an infinite loop: tpdfs :: (Int, Int) -> IO [Int] tpdfs (low, high) = do first <- getStdRandom (randomR (low, high)) second <- getStdRandom (randomR (low, high)) let r = (first + second) `div` 2 rest <- tpdfs (low, high) return (r : rest) Caller site: do nums <- tpdfs (2, 12) let ns = take 7 nums Niko

4 6