November 2008 - Haskell-Cafe

Fixity parsing, Template Haskell
by Reiner Pope 23 Nov '08

23 Nov '08

This post follows on from a discussion about a month ago, called "Haskell Syntax Inside Quasiquote". To summarise, suppose I want to create a Haskell quasiquoter for lists, eg [$list|1,x^2,y,3|] (representing the list [1,x^2,y,3]) Ideally, this would allow arbitrary Haskell expressions for each element of the list (provided, of course, that the types are correct). To write this list quasiquoter, I would need to parse Haskell expressions. This is doable[1], but is necessarily buggy when infix operators are concerned. For instance, a user of the list quasiquoter may define two new operators, (+*) and (+^), and then write [$list|1+*2+^3|] Being able to correctly parse such an expression depends on known the two operator's fixities, which is currently impossible. The problem is that potentially non-local fixity declarations affect parsing. As far as I can see, the correct solution is to change the Template Haskell AST representation of fixity expressions from > data Exp = ... > | InfixE (Maybe Exp) Exp (Maybe Exp) to something like > type Op = Exp --- because TH doesn't distinguish operators from expressions > data Exp = ... > | InfixE [Exp] [Op] --- length [Exp] == 1 + length [Op], always > | LeftSection Exp Op > | RightSection Op Exp Apart from splitting of the sections, the important difference is that the expressions are parsed as a list of expressions separated by operators. So, my example above would be parsed as something like InfixE [parseExp "1", parseExp "2", parseExp "3"] ["+*", "+^"] Then, when Template Haskell performs the splice, it could correctly resolve the fixities. Of course, this would require a change to Template Haskell, so a second-best solution would be to forbid unparenthesised expressions in my quasiquoter. Then, parsing can proceed correctly without knowing the fixities. This would be easiest to do if haskell-src-exts changed its AST in a similar way to described above for Template Haskell. Any thoughts? Cheers, Reiner Pope [1] For instance, see haskell-src-meta, which uses haskell-src-exts as a parser, and then converts the AST into a form that Template Haskell recognises.

3 8

why 'try' not work in parsec
by Changying Li 23 Nov '08

23 Nov '08

Hi. I read 'write yourself a scheme in 48 hours' and try to modify its code. now part of code is : parseList :: Parser LispVal parseList = liftM List $ sepEndBy parseExpr spaces parseDottedList :: Parser LispVal parseDottedList = do head <- endBy parseExpr spaces tail <- char '.' >> spaces >> parseExpr return $ DottedList head tail parseExpr :: Parser LispVal parseExpr = parseAtom <|> parseString <|> parseNumber <|> parseQuoted <|> do char '(' skipMany space x <- (try parseList) <|> parseDottedList char ')' return x but I got an error when parse (1 . 2): Lisp>>> (1 . 2) Parse error at "lisp" (line 1, column 4): unexpected "." expecting space, letter, "\"", digit, "'", "(" or ")" I think it failed in parseList because when I rewrite 7th line in parseExpr as: x <- (try parseDottedList) <|> parseList it work. so my question is: if it is failed in parseList, why didn't 'try' work? why not the parseExpr try parseDottedList ? -- Thanks & Regards Changying Li

2 2

Type question in instance of a class
by Maurício 23 Nov '08

23 Nov '08

Hi, Why is this wrong? ---- class MyClass r where function :: r -> s data MyData u = MyData u instance MyClass (MyData v) where function (MyData a) = a ---- GHC says that the type of the result of 'function' is both determined by the "rigid type" from MyClass and the "rigid type" from MyData. But why can't both be the same? What am I doing wrong? Thanks for your help, Maurício

18 31

implementing python-style dictionary in Haskell
by kenny lu 23 Nov '08

23 Nov '08

Dear all, I am trying to implement the python-style dictionary in Haskell. Python dictionary is a data structure that maps one key to one value. For instance, a python dictionary d = {'a':1, 'b':2 } maps key 'a' to 1, 'b' to 2. Python dictionary allows for update. e.g. the statement d['a'] = 3 changes the value pointed by 'a' from 1 to 3. Internally, python dictionary is implemented using hash table. My first attempt is to use Data.HashTable. However it was immediately abandoned, as I realize the memory usage is unreasonably huge. == SECOND ATTEMPT == My second attempt is to use Data.Map {-# OPTIONS_GHC -fglasgow-exts #-} module Main where import qualified Data.HashTable as HT import qualified Data.IntMap as IM import qualified Data.Map as DM import qualified Data.ByteString.Char8 as S import Data.Char -- the Dict type class class Dict d k v | d -> k v where empty :: d insert :: k -> v -> d -> d lookup :: k -> d -> Maybe v update :: k -> v -> d -> d -- Let's use string as key type Key = String -- insert key-value pairs into a dictionary fromList :: Dict d k a => [(k,a)] -> d fromList l = foldl (\d (key,val) -> insert key val d) empty l instance Dict (DM.Map S.ByteString a) Key a where empty = DM.empty insert key val dm = let packed_key = S.pack key in DM.insert packed_key val dm lookup key dm = let packed_key = S.pack key in DM.lookup packed_key dm update key val dm = let packed_key = S.pack key in DM.update (\x -> Just val) packed_key dm Which kinda works, however since Map is implemented using a balanced tree, therefore, when as the dictionary grows, it takes a long time to insert new key-value pair. == THIRD ATTEMPT == My third attempt is to use Data.IntMap -- an implementation of Dict using IntMap instance Dict (IM.IntMap a) Key a where empty = IM.empty insert key val im = let int_key = fromIntegral (HT.hashString key) in IM.insert int_key val im lookup key im = let int_key = fromIntegral (HT.hashString key) in IM.lookup int_key im update key val im = let int_key = fromIntegral (HT.hashString key) in IM.update (\x -> Just val) int_key im This implementation is faster than the Map approach, however this implementation can't handle collision well, two keys which are hashed into the same integer will overwrite each other. == FOURTH ATTEMPT == My fourth implementation is to use Trie. The idea is to split a string (a key) into a list of 4-character chunks. Each chunk can be mapped into a 32-bit integer without collision. We then insert the value with this list of chunks into the Trie. -- an implementation of Dict using Trie instance Dict (Trie a) Key a where empty = emptyTrie insert key val trie = let key_chain = chain key in insertTrie key_chain val trie lookup key trie = let key_chain = chain key in lookupTrie key_chain trie update key val trie = let key_chain = chain key in updateTrie key_chain val trie -- an auxillary function that "splits" string into small pieces, -- 4 characters per piece, 4 chars = 32 bit chain :: Key -> [Key] chain k | length k > 4 = let (k',ks) = splitAt 4 k in (k':chain ks) | otherwise = [k] -- a collision-free hash function which turns four chars into Int32 safehash :: [Char] -> Int safehash cs | length cs > 4 = error "safehash failed." | otherwise = sum [ (ord c)*(256^i) | (c,i) <- zip cs [0..3] ] -- a trie datatype data Trie a = Trie [a] (IM.IntMap (Trie a)) -- the empty trie emptyTrie = Trie [] (IM.empty) -- insert value into the trie insertTrie :: [String] -> a -> Trie a -> Trie a insertTrie [] i (Trie is maps) = Trie (i:is) maps insertTrie (word:words) i (Trie is maps) = let key = safehash word in case IM.lookup key maps of { Just trie -> let trie' = insertTrie words i trie maps' = IM.update (\x -> Just trie') key maps in Trie is maps' ; Nothing -> let trie = emptyTrie trie' = insertTrie words i trie maps' = IM.insert key trie' maps in Trie is maps' } -- lookup value from the trie lookupTrie :: [String] -> Trie a -> Maybe a lookupTrie [] (Trie vs _) = case vs of [] -> Nothing (x:_) -> Just x lookupTrie (word:words) (Trie is maps) = let key = safehash word in case IM.lookup key maps of Just trie -> lookupTrie words trie Nothing -> Nothing -- update the trie with the given value. updateTrie :: [String] -> a -> Trie a -> Trie a -- we only update the first value and leave the rest unchanged. updateTrie [] y (Trie (x:xs) maps) = Trie (y:xs) maps updateTrie (word:words) v (Trie is maps) = let key = safehash word in case IM.lookup key maps of Just trie -> let trie' = updateTrie words v trie maps' = IM.update (\x -> Just trie') key maps in Trie is maps' Nothing -> Trie is maps == BENCH MARK == I have a main function which builds a dictionary from a text file. Each line of the file is a key-value pair separated by a space. e.g. key1 1 key2 2 ... main :: IO () main = do { content <- readFile "in.txt" ; let -- change this following type annotation -- to change different type of the dictionary -- dict :: DM.Map S.ByteString Int -- dict :: IM.IntMap Int dict :: Trie Int dict = fromList (map parse_a_line (lines content)) ; case Main.lookup "key256" dict of { Just v -> putStrLn (show v) ; Nothing -> putStrLn "Not found" } -- read a line here so that we can pause the program -- and look at the memory usage. ; v <- readLn ; putStrLn v } where parse_a_line :: String -> (Key,Int) parse_a_line line = case words line of [key,val] -> (key,read val) _ -> error " parse error. " I tested all three implementations by building a dictionary of size 1000000. The result shows that the Map and the Trie approaches handle collision well, but the IntMap approach does not. Here is a comparison of memory usage Map : 345 MB IntMap : 146 MB Trie : 282 MB Python : 94 MB Here is a comparison of execution time (on an intel dual core 2.0G) Map: 26 sec IntMap: 9 sec Trie: 12 sec Python: 2.24 sec The above number shows that my implementations of python style dictionary are space/time in-efficient as compared to python. Can some one point out what's wrong with my implementations? I've attached my code in the tgz file. Cheers, Kenny

13 28

Haskell Weekly News: Issue 94 - November 22, 2008
by Brent Yorgey 22 Nov '08

22 Nov '08

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20081122 Issue 94 - November 22, 2008 --------------------------------------------------------------------------- Welcome to issue 94 of HWN, a newsletter covering developments in the [1]Haskell community. Lots of interesting reading this week! Martin Escardo writes about [2]finite search over infinite search spaces expressed as a monad; Conal Elliott writes about [3]the unambiguous choice operator and [4]merging partial values; Luke Palmer on [5]restricted data types and [6]Udon, his system for universal distributed object management; a post about [7]incremental parsing in Yi; Ryan Ingram on [8]parametric higher-order abstract syntax; Issue #12 of [9]the Monad.Reader; and much more! Announcements The Monad.Reader - Issue 12: Summer of Code Special. Wouter Swierstra [10]announced Issue 12 of [11]the Monad.Reader, featuring articles by Max Bolingbroke, Roman Cheplyaka, and Neil Mitchell describing their Summer of Code projects. Turbinado V0.1. Alson Kemp [12]announced the release of [13]Turbinado, an MVC web framework for Haskell. EEConfig-1.0. Bartosz Wojcik [14]announced the release of [15]EEConfig, a simple library for reading parameters from a configuration file. Discussion Proof of a multi-threaded application. Silviu Andrica [16]asked about the possibility of proving the correctness of a multi-threaded application written in Haskell, leading to a discussion of STM, model checking, and related issues. Monadic bind with associated types + PHOAS?. Ryan Ingram [17]wrote about using parametric higher-order abstract syntax to get the benefits of HOAS (using the embedding language to express binding and substitution) while still being able to inspect or optimize the resulting expressions. Blog noise [18]Haskell news from the [19]blogosphere. * Ashish Hanwadikar: [20]More on Haskell DSL. * Real-World Haskell: [21]Real World Haskell in the Wild!. * Conal Elliott: [22]Merging partial values. * John Goerzen (CosmicRay): [23]If Programming Languages Were Christmas Carols. * Conal Elliott: [24]Functional concurrency with unambiguous choice. * >>> Martin Escardo: [25]A Haskell monad for infinite search in finite time. * The GHC Team: [26]Redesigning GHC's build system. * Luke Palmer: [27]Restricted Data Types. * Yi: [28]Incremental Parsing in Yi. * Roman Cheplyaka: [29]The Monad Reader, SoC special. * Darcs: [30]camp irregular news #1. * Eric Kow (kowey): [31]iterative committing. * >>> Joey Hess: [32]a year of haskell (not really). * FP Lunch: [33]The origin of species. * Luke Palmer: [34]Udon Sketch #2. * John Goerzen (CosmicRay): [35]Real World Haskell Update. * Real-World Haskell: [36]When will you see us on bookstore shelves?. * Paul Potts: [37]Reading Real World Haskell. * Darcs: [38]darcs 2.1.2 released!. * Darcs: [39]darcs weekly news #12. * Russell O'Connor: [40]Haskell Lesson. * Conal Elliott: [41]Enhancing a Zip. * Conal Elliott: [42]Proofs for left fold zipping. * >>> Andrew Birkett: [43]Why do they call it: Referentially transparent. * >>> Andrew Birkett: [44]Why do they call it: Referentially transparent (II). Quotes of the Week * dons: instance Ord OCaml, oh wait. hang on. OCaml can't do that. * BONUS: as you can see, one of the best parts of Haskell is #haskell. * ddarius: head [] :: FlyingMonkeys About the Haskell Weekly News New editions are posted to [45]the Haskell mailing list as well as to [46]the Haskell Sequence and [47]Planet Haskell. [48]RSS is also available, and headlines appear on [49]haskell.org. To help create new editions of this newsletter, please see the information on [50]how to contribute. Send stories to byorgey at cis dot upenn dot edu. The darcs repository is available at darcs get [51]http://code.haskell.org/~byorgey/code/hwn/ . References 1. http://haskell.org/ 2. http://math.andrej.com/2008/11/21/a-haskell-monad-for-infinite-search-in-fi… 3. http://feeds.feedburner.com/~r/conal/~3/461480571/ 4. http://feeds.feedburner.com/~r/conal/~3/461534658/ 5. http://lukepalmer.wordpress.com/2008/11/20/restricted-data-types/ 6. http://lukepalmer.wordpress.com/2008/11/19/udon-sketch-2/ 7. http://yi-editor.blogspot.com/2008/11/incremental-parsing-in-yi.html 8. http://www.haskell.org//pipermail/haskell-cafe/2008-November/050768.html 9. http://www.haskell.org/haskellwiki/The_Monad.Reader 10. http://www.haskell.org//pipermail/haskell-cafe/2008-November/050786.html 11. http://www.haskell.org/haskellwiki/The_Monad.Reader 12. http://www.haskell.org//pipermail/haskell/2008-November/020811.html 13. http://www.turbinado.org/ 14. http://www.haskell.org//pipermail/haskell/2008-November/020810.html 15. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/EEConfig 16. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/47728 17. http://www.haskell.org//pipermail/haskell-cafe/2008-November/050768.html 18. http://planet.haskell.org/ 19. http://haskell.org/haskellwiki/Blog_articles 20. http://feedproxy.google.com/~r/typepad/ahanwadi/ashishs_niti/~3/n41w6S_82SE… 21. http://www.realworldhaskell.org/blog/2008/11/22/real-world-haskell-in-the-w… 22. http://feeds.feedburner.com/~r/conal/~3/461534658/ 23. http://changelog.complete.org/archives/825-if-programming-languages-were-ch… 24. http://feeds.feedburner.com/~r/conal/~3/461480571/ 25. http://math.andrej.com/2008/11/21/a-haskell-monad-for-infinite-search-in-fi… 26. http://ghcmutterings.wordpress.com/2008/11/21/redesigning-ghcs-build-system/ 27. http://lukepalmer.wordpress.com/2008/11/20/restricted-data-types/ 28. http://yi-editor.blogspot.com/2008/11/incremental-parsing-in-yi.html 29. http://physics-dph.blogspot.com/2008/11/monad-reader-soc-special.html 30. http://blog.darcs.net/2008/11/camp-irregular-news-1.html 31. http://koweycode.blogspot.com/2008/11/iterative-commiting.html 32. http://kitenet.net/~joey/blog/entry/a_year_of_haskell___40__not_really__41_… 33. http://sneezy.cs.nott.ac.uk/fplunch/weblog/?p=132 34. http://lukepalmer.wordpress.com/2008/11/19/udon-sketch-2/ 35. http://changelog.complete.org/archives/814-real-world-haskell-update 36. http://www.realworldhaskell.org/blog/2008/11/18/when-will-you-see-us-on-boo… 37. http://praisecurseandrecurse.blogspot.com/2008/11/reading-real-world-haskel… 38. http://blog.darcs.net/2008/11/darcs-212-released.html 39. http://blog.darcs.net/2008/11/darcs-weekly-news-12.html 40. http://r6.ca/blog/20081116T213644Z.html 41. http://feeds.feedburner.com/~r/conal/~3/454447926/ 42. http://feeds.feedburner.com/~r/conal/~3/454297817/ 43. http://www.nobugs.org/blog/archives/2008/11/12/why-do-they-call-it-referent… 44. http://www.nobugs.org/blog/archives/2008/11/12/why-do-they-call-it-referent… 45. http://www.haskell.org/mailman/listinfo/haskell 46. http://sequence.complete.org/ 47. http://planet.haskell.org/ 48. http://sequence.complete.org/node/feed 49. http://haskell.org/ 50. http://haskell.org/haskellwiki/HWN 51. http://code.haskell.org/~byorgey/code/hwn/

1 0

Do I need an account to report build of Hacakge packages?
by Ahn, Ki Yung 22 Nov '08

22 Nov '08

I am just curious about how cabal report works. I recently figured out that there is a report command in cabal and it reports the reports generated by --build-reports option when building a package. Is this because I don't have an account on Hackage yet, or because of some other reasons? And if I make an account, where how I put that information in cabal config file? I've looked into the cabal config file and tried to change this myself before, but it wasn't very self explanatory to me. For instance, I tried to make the build-reports on by default, deleting haskell comment like double dashes "--" and put True flag after the colon, but keep getting parse error from cabal. I looked up the manual but it says that the config file is self explanatory, which isn't to me at all. Are there any documentations on this available anywhere? === error messages when I tried to report the build log === kyagrd@kyagrd:~$ cabal report Sending: POST http://hackage.haskell.org/buildreports HTTP/1.1 Content-Type: text/plain Content-Length: 281 Accept: text/plain Creating new connection to hackage.haskell.org Received: HTTP/1.1 404 Not Found Date: Fri, 21 Nov 2008 23:52:14 GMT Server: Apache/2.2.3 (Debian) Alternates: {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-2} {language cs} {length 745}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-1} {language de} {length 766}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-1} {language en} {length 611}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-1} {language es} {length 759}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-1} {language fr} {length 771}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-1} {language ga} {length 813}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-1} {language it} {length 692}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-2022-jp} {language ja} {length 749}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset euc-kr} {language ko} {length 703}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-1} {language nl} {length 688}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-2} {language pl} {length 707}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-1} {language pt-br} {length 753}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-1} {language ro} {length 689}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-5} {language sr} {length 716}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-1} {language sv} {length 722}}, {"HTTP_NOT_FOUND.html.var" 1 {type text/html} {charset iso-8859-9} {language tr} {length 755}} Vary: accept-language,accept-charset Content-Length: 418 Content-Type: text/html; charset=iso-8859-1 cabal: Unrecognised response from server. kyagrd@kyagrd:~$ cabal --version cabal-install version 0.6.0 using version 1.6.0.1 of the Cabal library

4 5

varargs zip
by Jason Dusek 22 Nov '08

22 Nov '08

It came up on IRC last night that there is no "generic" zip in Haskell. I decided to write one as an example, but it only half works. When the argument lists are all definitely of one type, instance selection works as expected; however, with numeric types, for example, things don't work out. I'm not sure how to express the idea that the result tuple determines the arguments types, with either of functional dependencies or associated types. -- _jsn |...example...| http://github.com/jsnx/haskell-demos/tree/master/generic_zip%2FGenericZip.hs

5 5

Re: [Haskell] Does GHC support the standard CPP functionalities?
by Malcolm Wallace 22 Nov '08

22 Nov '08

[moved to haskell-cafe] > {-# LANGUAGE CPP #-} > > module Packer where > > #define FLASH_APP_START 1 > #define FLASH_APP_END 2 > #define INSERT_SECTION(x) (#x, (FLASH_##x##_START, FLASH_##x##_END)) The CPP stringization operator # and the token-catenation operator ## are ANSI additions over the traditional K+R CPP. Ghc uses the - traditional flag to exclude them, because both # and ## are valid Haskell operators, and most people would not want them to be removed by the CPP preprocessor. There are also some other lexical differences between Haskell and C which make it a good ides for ghc to use cpp -traditional. However, if you really want to use ANSI additions, you can switch to cpphs, which does know about the lexical syntax of Haskell. http://haskell.org/cpphs To use it with ghc, you will need to pass the following extra options: ghc -cpp -pgmPcpphs -optP--cpp -optP-ansi Unfortunately, I'm not certain I can guarantee that the -ansi flag will take effect - it depends on whether ghc internally adds the - traditional argument before or after it. Regards, Malcolm

1 0

Operator cheat sheet, and monadic style q
by Owen Smith 22 Nov '08

22 Nov '08

Greetings, I'm a longtime Haskell-curious programmer who, after a few aborted attempts at getting started and long nights staring at academic papers, finally managed to get the bug. I've been pleased with my progress so far, but a couple of things have bugged me enough to seek advice from the rest of y'all. 1. Contending with the use of frequently unfamiliar non-alphanumeric operators has been an uphill battle for me. I think the main reason for this is that I've had no luck in Googling up their definitions (my primary approach for dealing with every other unknown in the Haskell universe) due to their very non-alphanumeric nature. I'm curious if 1) anyone has compiled a cheat sheet of common operators and their meanings/modules, in some sort of text-search-friendly format (e.g. spelling out the operator characters, listing alternate names), or 2) a better way for searching for these things? 2. There's a lot I need to learn about good Haskell style, especially coming from a C++ background. Even my experience in Lisp seems to result in way more parentheses than Haskell coders are comfortable with. :-) In particular, I'm curious about how people actually use monadic operators. The following simple forms with the Maybe monad, for example, appear to be equivalent (hope I and QuickCheck are right about that!): foo :: Int -> Maybe Int bar :: Int -> Maybe Int baz :: Int -> Maybe Int baz n = (foo n) >>= bar baz n = bar =<< (foo n) baz n = (foo >=> bar) n baz n = (foo <=< bar) n and I'm thinking the latter two are more idiomatically written as: baz = foo >=> bar -- I think this one is my fave, naively speaking baz = bar <=< foo Yeah, so "there's more than one way to do it"--though I would never have known about =<<, >=>, and <=< from looking at the introductory material I've seen on the subject. What do people here prefer using in what circumstances? Or is everyone off using do notation or arrows instead? :-) Thanks for the help! -- O

4 3

Counting beta reductions for a Haskell program...
by kk08 22 Nov '08

22 Nov '08

Does GHC supports/has a command for counting total beta reductions taken by a program? Thanks. -- View this message in context: http://www.nabble.com/Counting-beta-reductions-for-a-Haskell-program...-tp2… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 4