July 2011 - Haskell-Cafe

Parsing workflow
by Nils Schweinsberg 21 Jan '12

21 Jan '12

Hi! I'm having a really hard time to write a correct parser for a small language I've developed. I have been trying to write a parser using parsec, but always get a lot of error messages like "unexpected "\n", expected ..., new-line or..." when trying to run the parser. Then I read about the happy parser and really liked the separation of lexing the text into tokens and parsing the actual logic behind those tokens. Since I couldn't get familiar with the lexer "alex" I gave up on the alex-happy-approach again and went back to parsec. But with that lexer->parser idea on my mind, my parser currently looks a lot like a lexer. So I came up with the idea of using a combination of parsec and happy, where I generate a list of tokens for my text via parsec and analyse it with happy. My questions would be: - Is this a valid approach? - What is your workflow on parsing complex data structures? - What about performance? Since my project is going to be an interpreted language parsing performance might be interesting aswell. I've read that happy is in general faster than parsec, but what if I combine both of them as I said above? I guess that parsing a simple list of tokens without any nested parser structures would be pretty fast? - Do you have any other ideas on how to improve my parser? - What are your general thoughts on happy vs. parsec? Thanks for any replies, Nils

10 17

Proposal to incorporate Haskell.org
by Don Stewart 16 Dec '11

16 Dec '11

Hello everyone. The haskell.org committee[1], in the interest of the long-term stability of the open source Haskell community infrastructure, has decided to incorporate haskell.org as a legal entity. This email outlines our recommendation, and seeks input from the community on this decision. The committee's proposal is that haskell.org incorporate as an entity under the Software Freedom Conservancy umbrella organization (the same group that Darcs joined recently): http://sfconservancy.org/ If we proceed with this move, haskell.org will be a legal entity, and registered as a non-profit, allowing us to more directly accept (US tax-deductible) donations, and to invest in assets that benefit the Haskell open source community. We welcome your feedback on the proposal attached below. -- Don Stewart (on behalf of the Haskell.org committee) ------------------------------------------------------------------------ = A proposal for the incorporation of Haskell.org = In recent years, haskell.org has started to receive assets, e.g. money from Google Summer Of Code, donations for Hackathons, and a Sparc machine for use in GHC development. We have also started spending this money: in particular, on hosting haskell.org itself. There is also interest in running fundraising drives for specific things such as Hackathon sponsorship and hosting fees. However, haskell.org doesn't currently exist as a legal entity, meaning that these assets have had to be held on our behalf by other entities, such as Galois and various universities. This leads to tricky situations, with no-one being sure who should decide how the haskell.org assets can be used. To solve these problems, we propose that haskell.org applies to become a member project of the Software Freedom Conservancy (SFC) <http://conservancy.softwarefreedom.org/>. The SFC is a non-profit organization that provides free financial and administrative services to open source projects. Additionally, it has 501(c)(3) status, meaning donations from the US are tax-deductible. The SFC would hold haskell.org's money and other assets, and would be able to accept donations on behalf of haskell.org. The haskell.org committee, as described here [2], will make decisions on spending assets and other decisions related to governing the non-profit. Before proceeding, we are inviting input from the community in the form of specific objections or queries regarding the plan. We've tried to answer some of the most likely questions: Q: Does this mean that my Haskell project must now be covered by a copyleft licence such as GPL? A: No, but Haskell projects using haskell.org resource should use an Open Source licence <http://www.opensource.org/licenses/alphabetical>. Q: Will it still be possible to use community.h.o to host non-open-source material, such as academic papers? A: An overall minority of such content, as is the current situation, is not a problem. Q: Will it still be possible to have job ads on the haskell.org mailing lists and website? A: Yes. Q: Will this affect our ability to host the Haskell Symposium <http://www.haskell.org/haskell-symposium/> and Industrial Haskell Group<http://industry.haskell.org/> webpages within haskell.org? A: No. Q: What will be the relationship between haskell.org and other organizations such as the Haskell Symposium and Industrial Haskell Group? A: Those organisations will continue to exist as separate entities. Q: If an umbrella non-profit organisation "The Haskell Foundation" was created, would haskell.org be able to join it? A: Yes. It's likely that in such a scenario, the Haskell Foundation would become the owner of the haskell.org domain name, with the cost divided between the members. The entity that is part of the SFC would be renamed "community.haskell.org" in order to avoid confusion. [1]: http://www.haskell.org/haskellwiki/Haskell.org_committee [2]: http://www.haskell.org/haskellwiki/Haskell.org_committee#Operation

10 16

Hexpat: Lazy I/O problem with huge input files
by Aleksandar Dimitrov 10 Dec '11

10 Dec '11

Hello Haskell Cafe, I really hope this is the right list for this sort of question. I've bugged the folks in #haskell, they say go here, so I'm turning to you. I want to use Hexpat to read in some humongous XML files (linguistic corpora,) since it's the only Haskell XML library (I could find) that takes ByteStrings as input. I stumbled on a problem when using one of the examples from the docs of Text.XML.Expat.Tree. The "cookbook recipe" there suggests *first* processing the data, and only then looking into the parser error to see if there has been an error. I understand this should prevent the parse tree from being fully evaluated before use. Unfortunately, that is not what happens on my system (ghc 6.12.1, if that's of importance.) This is the code from the docs, that I modified to read files: > import Text.XML.Expat.Tree > import System.Environment (getArgs) > import Control.Monad (liftM) > import qualified Data.ByteString.Lazy as C >· > -- This is the recommended way to handle errors in lazy parses > main = do > f <- liftM head getArgs >>= C.readFile > let (tree, mError) = parse defaultParseOptions f > print (tree :: UNode String) >· > -- Note: We check the error _after_ we have finished our processing > -- on the tree. > case mError of > Just err -> putStrLn $ "It failed : "++show err > Nothing -> putStrLn "Success!" Given a 42M test file, an invocation like this: % ghc --make -O2 Hexpat.hs % ./Hexpat input.xml > dump.xml will gobble up some 2Gigs of RAM (at least. I usually kill it before it starts thrashing the swap space, since that almost crashes my entire machine.) If I remove the last 3 lines: > import Text.XML.Expat.Tree > import System.Environment (getArgs) > import Control.Monad (liftM) > import qualified Data.ByteString.Lazy as C > > main = do > f <- liftM head getArgs >>= C.readFile > let (tree, mError) = parse defaultParseOptions f > print (tree :: UNode String) the same invocation and input file barely uses a megabyte or two of RAM and finishes really quickly. Why is that? Is this a mistake in the Hexpat docs, or am I doing something wrong? Lazy IO has always been a little bit of a mystery to me, and just when I thought I had it... Thanks for any help on the matter! Aleks

3 3

Class instances in haddock documentation missing
by Joachim Breitner 28 Aug '11

28 Aug '11

Hi, the haddock information generated on hackage lists class instances per class and per data type e.g. on http://hackage.haskell.org/packages/archive/base/4.3.1.0/doc/html/Data-Eq.h… or http://hackage.haskell.org/packages/archive/xhtml/3000.2.0.1/doc/html/Text-… For some reason, the documentation generated on Debian does not. Does anybody have an idea why that could be? We use ./Setup haddock --hyperlink-source to build the documentation, using the haddock that is shipped with ghc (2.9.2 at the moment). Greetings, Joachim -- Joachim "nomeata" Breitner Debian Developer nomeata(a)debian.org | ICQ# 74513189 | GPG-Keyid: 4743206C JID: nomeata(a)joachim-breitner.de | http://people.debian.org/~nomeata

1 1

Please take the State of Haskell, 2011 survey
by Johan Tibell 23 Aug '11

23 Aug '11

Hi all, I've put together a quick, 12-question State of Haskell, 2011 survey: http://blog.johantibell.com/2011/07/its-time-for-this-years-state-of.html The survey will hopefully give us some insight into how people use Haskell and perhaps also some ideas on how Haskell tools and libraries could be improved. This is the second year I run this survey. New from last year are specific questions on library support and reasoning about run-time performance. P.S. Please direct replies to this email to haskell-cafe(a)haskell.org. Cheers, Johan

4 5

AVL Tree in a pattern matching way
by larry.liuxinyu 15 Aug '11

15 Aug '11

Hi, I browsed the current AVL tree implementation in Hackage http://hackage.haskell.org/packages/archive/AvlTree/4.2/doc/html/src/Data-T… AVL tree denote the different of height from right sub-tree to left sub-tree as delta, to keep the balance, abs(delta)<=1 is kept as invariant. So the typical implementation define N (Negative), P (Positive), and Z (zero) as the tree valid nodes (and the Empty as the trivial case). When a new element is inserted, the program typically first check if the result will break the balance, and process rotation to keep the balance of the tree. Some other pure functional implementation takes the same approach, for example: Guy Cousineau and Michel Mauny. ``The Functional Approach to Programming''. pp 173 ~ 186 Consider the elegant implementation of Red-black tree in pattern matching way by Chris Okasaki, I tried to use the same method in AVL tree, and here is the result. module AVLTree where -- for easy verification, I used Quick Check package. import Test.QuickCheck import qualified Data.List as L -- for verification purpose only -- Definition of AVL tree, it is almost as same as BST, besides a new field to store delta. data AVLTree a = Empty | Br (AVLTree a) a (AVLTree a) Int insert::(Ord a)=>AVLTree a -> a -> AVLTree a insert t x = fst $ ins t where -- result of ins is a pair (t, d), t: tree, d: increment of height ins Empty = (Br Empty x Empty 0, 1) ins (Br l k r d) | x < k = node (ins l) k (r, 0) d | x == k = (Br l k r d, 0) -- For duplicate element, we just ignore it. | otherwise = node (l, 0) k (ins r) d -- params: (left, increment on left) key (right, increment on right) node::(AVLTree a, Int) -> a -> (AVLTree a, Int) -> Int -> (AVLTree a, Int) node (l, dl) k (r, dr) d = balance (Br l k r d', delta) where d' = d + dr - dl delta = deltaH d d' dl dr -- delta(Height) = max(|R'|, |L'|) - max (|R|, |L|) -- where we denote height(R) as |R| deltaH :: Int -> Int -> Int -> Int -> Int deltaH d d' dl dr | d >=0 && d' >=0 = dr | d <=0 && d' >=0 = d+dr | d >=0 && d' <=0 = dl - d | otherwise = dl -- Here is the core pattern matching part, there are 4 cases need rebalance balance :: (AVLTree a, Int) -> (AVLTree a, Int) balance (Br (Br (Br a x b dx) y c (-1)) z d (-2), _) = (Br (Br a x b dx) y (Br c z d 0) 0, 0) balance (Br a x (Br b y (Br c z d dz) 1) 2, _) = (Br (Br a x b 0) y (Br c z d dz) 0, 0) balance (Br (Br a x (Br b y c dy) 1) z d (-2), _) = (Br (Br a x b dx') y (Br c z d dz') 0, 0) where dx' = if dy == 1 then -1 else 0 dz' = if dy == -1 then 1 else 0 balance (Br a x (Br (Br b y c dy) z d (-1)) 2, _) = (Br (Br a x b dx') y (Br c z d dz') 0, 0) where dx' = if dy == 1 then -1 else 0 dz' = if dy == -1 then 1 else 0 balance (t, d) = (t, d) -- Here are some auxiliary functions for verification -- check if a AVLTree is valid isAVL :: (AVLTree a) -> Bool isAVL Empty = True isAVL (Br l _ r d) = and [isAVL l, isAVL r, d == (height r - height l), abs d <= 1] height :: (AVLTree a) -> Int height Empty = 0 height (Br l _ r _) = 1 + max (height l) (height r) checkDelta :: (AVLTree a) -> Bool checkDelta Empty = True checkDelta (Br l _ r d) = and [checkDelta l, checkDelta r, d == (height r - height l)] -- Auxiliary functions to build tree from a list, as same as BST fromList::(Ord a)=>[a] -> AVLTree a fromList = foldl insert Empty toList :: (AVLTree a) -> [a] toList Empty = [] toList (Br l k r _) = toList l ++ [k] ++ toList r -- test prop_bst :: (Ord a, Num a) => [a] -> Bool prop_bst xs = (L.sort $ L.nub xs) == (toList $ fromList xs) prop_avl :: (Ord a, Num a) => [a] -> Bool prop_avl = isAVL . fromList . L.nub And here are my result in ghci: *AVLTree> test prop_avl OK, passed 100 tests. The program is available in github: http://www.google.com/url?sa=D&q=https://github.com/liuxinyu95/AlgoXY/blob/… I haven't provided delete function yet. Cheers. -- Larry, LIU https://github.com/liuxinyu95/AlgoXY

2 1

logic and types
by Patrick Browne 13 Aug '11

13 Aug '11

Hi, Below are some questions about the logical interpretation of types and type classes. Thanks, Pat module J where type Id = String type Position = Integer data Person = Person Id Position deriving Show -- Is this an axiom at type level? class Pos a where getPos :: a -> Position -- The :type command says -- forall a. (Pos a) => a -> Position -- How do I write this in logic? (e.g. implies, and, or, etc) -- What exactly is being asserted about the type variable and/or about the class? -- I am not sure of the respective roles of => and -> in a logical context -- Is the following a fact at type level, class level or both? instance Pos Person where getPos (Person i p) = p -- Is it the evaluation or the type checking that provides a proof of type correctness? -- getPos(Person "1" 2) This message has been scanned for content and viruses by the DIT Information Services E-Mail Scanning Service, and is believed to be clean. http://www.dit.ie

6 8

For class Monoid; better names than mempty & mappend might have been: mid (mident) & mbinop
by KC 08 Aug '11

08 Aug '11

It would be easier for beginners to "grok". -- -- Regards, KC

6 6

Re: [Haskell-cafe] Github support for cabal files
by Greg Weber 08 Aug '11

08 Aug '11

I think the haddock description field is a great barrior to documentation. I don't want to clutter my cabal file with lengthy documentation. Michael Snoyberg and I could not figure out how to document the Hamlet syntax because there is no way (as far as I know) to have literal unescaped, uninterpreted text. [1] When I go to a github repo, I expect that I can scroll down to the README and I will get a good overview. When I go to hackage, I expect nothing more than a synopsis, and I hope I can follow several links to find the information I am looking for. It is suggested that the description field should point to a top level module with all the documentation, but although haddock is good for documenting code, it is not an ideal overview style, and not all packages lend themselves well to having one top-level module. I would like a description field that just points to an external (README) file. Cabal could either use the pandoc library, or to avoid that dependency directly it could use the pandoc executable (that would have to be installed first by those of us that want this feature). Alternatively it could just allow an html file for the description and make me responsible for writing a script that runs pandoc and then invokes sdist. [1] http://hackage.haskell.org/package/hamlet

4 3

Fwd: shootout
by Ben 03 Aug '11

03 Aug '11

hello cafe-istas -- for those of you who are into these things, a lot of the shootout programs are suffering from "make errors" and thus do not have benchmarks. http://shootout.alioth.debian.org/u64q/haskell.php best, ben Begin forwarded message: > From: Don Stewart <dons00(a)gmail.com> > Date: July 30, 2011 9:52:12 AM PDT > To: Ben <midfield(a)gmail.com> > Cc: Don Bruce Stewart <dons(a)cse.unsw.edu.au> > Subject: Re: shootout > > Best to bring this up on haskell-cafe@ > > On Sun, Jul 31, 2011 at 12:34 AM, Ben <midfield(a)gmail.com> wrote: >> FYI, a lot of the haskell programs on the shootout suffer from "make errors" and thus do not have benchmarks. >> >> best, ben

3 2