March 2007 - Haskell-Cafe

A simple parsing task for parsec.
by paolino 29 Mar '07

29 Mar '07

Hi, I had a bad time trying to parse the words of a text. I suspect I miss some parsec knowledge. In the end it seems working, though I haven't tested much and this example contains the main features I was looking. *Main> parseTest (parseLine eof) "paolo@gmail sara,mimmo! 9ab a9b ab9 cd\n" ["paolo@gmail","sara","mimmo","cd"] --------------------- manyTillT body terminator joiner = liftM2 joiner (manyTill body (lookAhead terminator)) terminator wordChar = letter <|> oneOf "_@" <?> "a valid word character" nonSeparator = wordChar <|> digit wordEnd = do x <- wordChar notFollowedBy nonSeparator return x word = manyTillT wordChar (try wordEnd) (\b t -> b ++ [t]) <?> "a word" wordStart = do (try nonSeparator >> unexpected "non separator") <|> anyChar lookAhead wordChar nextWord = manyTill anyChar (try wordStart) >> (try word <|> nextWord) parseLine end = do f <- option [] $ return `fmap` try word r <- many $ try nextWord manyTill anyChar end return (f ++ r) ----------- Any comment to simplify this code is welcome. Paolino.

1 0

A simple parsing task for parsec.
by paolino 29 Mar '07

29 Mar '07

Hi, I had a bad time trying to parse the words of a text. I suspect I miss some parsec knowledge. In the end it seems working, though I haven't tested much and this example contains the main features I was looking. *Main> parseTest (parseLine eof) "paolo@gmail sara,mimmo! 9ab a9b ab9 cd\n" ["paolo@gmail","sara","mimmo","cd"] --------------------- manyTillT body terminator joiner = liftM2 joiner (manyTill body (lookAhead terminator)) terminator wordChar = letter <|> oneOf "_@" <?> "a valid word character" nonSeparator = wordChar <|> digit wordEnd = do x <- wordChar notFollowedBy nonSeparator return x word = manyTillT wordChar (try wordEnd) (\b t -> b ++ [t]) <?> "a word" wordStart = do (try nonSeparator >> unexpected "non separator") <|> anyChar lookAhead wordChar nextWord = manyTill anyChar (try wordStart) >> (try word <|> nextWord) parseLine end = do f <- option [] $ return `fmap` try word r <- many $ try nextWord manyTill anyChar end return (f ++ r) ----------- Any comment to simplify this code is welcome. Paolino.

1 0

Monad/Functor Book
by Dominic Steinitz 29 Mar '07

29 Mar '07

> On 3/27/07, Dave at haskell.org <Dave at haskell.org> wrote: > > Given the amount of material posted at haskell.org and elsewhere > > explaining IO, monads and functors, has anyone considered publishing > > a comprehensive book explaining those subjects? (I am trying to > > read all the material online, but books are easier to read and don't > > require sitting in front of a computer to do so. Plus I can write in > > books :-). ) > > I've thought about writing extended tutorials on the relationship > between Haskell programming and category theory but there's a problem > I run into. It's tempting to make the identifications: > types<->objects, Haskell function<->arrows, suitably polymorphic > functions<->natural transformations, and so on. But the fact is, this > doesn't really work in the obvious way even though it seems like it > should at first (eg. Haskell functions aren't always total functions > in the mathematical sense and if you allow partial functions you can > do weird stuff). So either: > > (1) we need some technical work to patch up the differences (and > unfortunately I don't know what the patch-up is), > (2) we restrict ourselves to certain types of Haskell function for > which the theory works or > (3) we deliberately leave things a little vague. > > I usually tend to go for option (3), but that wouldn't be satisfactory > for an extended treatment. > > Has anyone else given this subject much thought? > -- > Dan Dan, It's a long time since I looked at this so this might be a complete red herring but have you thought about using the category of \omega-CPOs. Types are then objects (\omega-cpos) and functions are then arrows (continuous functions in the \omega-cpo sense). These papers may be of use: 1. Meijer http://research.microsoft.com/~emeijer/Papers/CWIReport.pdf 2. Mitchell Wand: Fixed-Point Constructions in Order-Enriched Categories 3. Freyd: Recursive Types Reduced to Inductive Types. Dominic.

1 0

Prologue junk? - compiling lambdabot:Plugin.Pl.Transform
by Iain Alexander 29 Mar '07

29 Mar '07

I'm trying to build lambdabot 4.0 with ghc-6.4.1 (gcc (GCC) 3.4.2 (mingw- special)) and Cabal-1.1.6.1 on WinXP SP2. I've got as far as Plugin.Pl.Transform.hs, and I get *** Mangler g:\ghc\ghc-6.4.1\perl g:\ghc\ghc-6.4.1\ghc-asm C:\DOCUME~1\IAINAL~1\LOCALS~1\Tem p\ghc2736.raw_s C:\DOCUME~1\IAINAL~1\LOCALS~1\Temp\ghc2736.s 4 Prologue junk?: _s7f7_ret: xorl %ecx, %ecx xorl %eax, %eax movl %ecx, 8(%esp) movl %eax, 12(%esp) /APP Transform.hs uses {-# OPTIONS -fvia-C -O2 -optc-O3 #-} I've tried and failed to make sense of why the mangler's failing. I don't know if this is a known problem with 6.4.1 on XP. I'm not sure what to try next. I could turn off the aggressive optimisation, but I don't know how much that would cost me. I've got 6.4.2 installed, so I could try that, although I'd need to rebuild all the prerequisites. Anything else? -- Iain Alexander ia(a)stryx.demon.co.uk

2 1

cost of modules
by Fawzi Mohamed 29 Mar '07

29 Mar '07

ehm, never post from someone's else computer with a new mailer... sorry for the double posts (to glasgow-haskell-users(a)haskell.org and here). Simon Peyton-Jones wrote: > Generally speaking GHC will inline *across* modules just as much as > it does *within* modules, with a single large exception. > > If GHC sees that a function 'f' is called just once, it inlines it > regardless of how big 'f' is. But once 'f' is exported, GHC can > never see that it's called exactly once, even if that later turns out > to be the case. This inline-once optimisation is pretty important > in practice. > > So: do not export functions that are not used outside the module > (i.e. use an explicit export list, and keep it as small as possible). This is very interesting to know, as it explains a strange effect that I was seeing: I had an algorithm and I began to add variants of it as separate functions in the same module. Then I saw the original function (which I had not touched) get slower and slower. I even wondered if the compiler was not maybe taking common parts of my functions out of them to reduce the evaluations making my original function slower, but then it was that it wasn't inlining anymore some functions. This means the with haskell (with ghc) cleaning up old code and keeping the modules as clean as possible pays off even more than in other languages... good to know, and very important when benchmarking various algorithms: commenting out a variant is better as having it as separate function.... Fawzi

2 2

Re: [Haskell-cafe] Newbie: a parser for a list of objects?
by Daniel Fischer 29 Mar '07

29 Mar '07

> -----Ursprüngliche Nachricht----- > Von: "Dmitri O.Kondratiev" <dokondr(a)gmail.com> > Gesendet: 26.03.07 16:44:12 > An: haskell-cafe(a)haskell.org > Betreff: [Haskell-cafe] Newbie: a parser for a list of objects? > Please see my questions inside comments {-- --} : > Thanks! > > --- > module Parser where > > import Data.Char > > type Parse a b = [a] -> [(b, [a])] > > {-- > Newbie: a parser for a list of objects? > > I am working with the section 17.5 "Case study: parsing expressions" of the book "Haskell The Craft of Functional Programming", where a parser for a list of objects is defined. > I called this function pList in order to avoid confusion with 'list' as a term for data structure. > > Please help me to understand how pList works (please, see the rest of the code at the end of this message): > --} > > pList :: Parse a b -> Parse a [b] > pList p = (succeed []) `alt` > ((p >*> pList p) `build` (uncurry (:))) > > > {-- > First of all, I don't quite understand why there must be a choice ('alt') between the function ('succeed') that always returns an empty list and the other part? This results in adding [] to the front, why? > Well, if the parser p doesn't succeed, we don't want the whole thing to fail. And p will (almost certainly) fail when the end of input is reached. So without the alternative 'succeed []', we'd get pL1 dig "12" = [(('1':y),rem) | (y,rem) <- pL1 dig "2"] = [(('1':y),rem) | (y,rem) <- [(('2':z),rem2) | (z,rem2) <- pL1 dig ""]] = [(('1':y),rem) | (y,rem) <- [(('2':z),rem2) | (z,rem2) <- []] = [(('1':y),rem) | (y,rem) <- []] = [] because dig "" = [] > I thought that 'simplified' version of pList should still work fine. Trying to prove this I wrote : > --} > > pL1 :: Parse a b -> Parse a [b] > pL1 p = (p >*> pL1 p) `build` (uncurry (:)) > > {-- > Which, as expected, does not work correctly - just gives an empty list [] - but I don't understand why: because the parser eventually fails when the end of input is reached. > > *Parser> t1 "12345" > [] > *Parser> > > Also, I don't understand why the textbook version of pList gives this result: > > *Parser> test "12345" > [("","12345"),("1","2345"),("12","345"),("123","45"),("1234","5"),("12345","")] That's because of the order of alt's arguments: (succeed [] `alt` p) inp = [([],inp)] ++ (p inp) with pList p = ((p >*> pList p) `build` (uncurry (:))) `alt` succeed [] the resulting list woulde be reversed. > > *Parser> > > In particular, I don't understand where the first element ("","12345") of the resulting list comes from? > > I am trying to figure out how pList recursively unfolds. To my mind operators in the expression: > > > (succeed []) `alt`((p >*> pList p) `build` (uncurry (:))) > > has the following execution order: > 1) >*> > 2) 'build' > 3) 'alt' > No, the first argument of alt gets evaluated first, because (p1 `alt` p2) inp = (p1 inp) ++ (p2 inp), thus we need p1 inp first. Then we see we haven't hit bottom, so we need the second argument of (++) (resp. alt). So next we need to evaluate p, then pList p, combine the results of those with the second argument of build, uncurry (:). > It seems that operation >*> should be done as many times as many elements the input list has. Right? > Unfortunately not. Let's stay with pList dig. Say your input starts with n digits. >From the example above you can conjecture that length (pList dig inp) == (n+1). Now in the outermost (dig >*> pList dig) branch, you apply (pList dig) to an input beginning with (n-1) digits, returning a list of length n, to each element of this list you adjoin the first digit, resulting in n + (n-1) + ... + 1 = n*(n+1)/2 applications of (>*>). (Lesson: you need an exclusive choice, using the second parser only if the first one fails and a maximal munch combinator in your library, too) > > Signature: > > (>*>) :: Parse a b -> Parse a c -> Parse a (b, c) > > implies that second argument of the expression: > > p >*> pList p > > should be of type 'Parse a c' but in this application it is of type 'Parse a b -> Parse a [b]' > c is [b], so p >*> pList p has type Parse a (b,[b]), then (p >*> pList p) `build` (uncurry (:)) has type Parse a [b] > How can that be? > How recursion termination conditinon is expressed in pList? recursion terminates when p fails. HTH, Daniel > --} > > none :: Parse a b > none inp = [] > > succeed :: b -> Parse a b > succeed val inp = [(val, inp)] > > suc:: b -> [a] -> [(b, [a])] > > suc val inp = [(val, inp)] > > spot :: (a -> Bool) -> Parse a a > spot p [] = [] > spot p (x:xs) > | p x = [(x, xs)] > | otherwise = [] > > alt :: Parse a b -> Parse a b -> Parse a b > alt p1 p2 inp = p1 inp ++ p2 inp > > bracket = spot (=='(') > dash = spot (== '-') > dig = spot isDigit > alpha = spot isAlpha > > infixr 5 >*> > > (>*>) :: Parse a b -> Parse a c -> Parse a (b, c) > > (>*>) p1 p2 inp = [((x,y), rem2) |(x, rem1) <- p1 inp, (y, rem2) <- p2 rem1] > > build :: Parse a b -> (b -> c) -> Parse a c > build p f inp = [ (f x, rem) | (x, rem) <- p inp] > > test = pList dig > t1 = pL1 dig > > > -----------------------------------------------------------------

2 5

ANNOUNCE: binary 0.3 - bigger, better, faster
by Lennart Kolmodin 29 Mar '07

29 Mar '07

Greetings friends! I'm pleased to announce binary 0.3! The 'binary' package provides efficient serialization of Haskell values to and from lazy ByteStrings. ByteStrings constructed this way may then be written to disk, written to the network, or further processed (e.g. stored in memory directly, or compressed in memory with zlib or bzlib). In total 14 people have contributed code and many more given feedback and cheerleading on #haskell@freenode. Thanks to all of you! It's available through Hackage: tarball: http://hackage.haskell.org/packages/archive/binary/binary-0.3.tar.gz darcs: darcs get http://darcs.haskell.org/binary homepage: http://www.cse.unsw.edu.au/~dons/binary.html It's been a while since the last release of binary [1] the 25th of January earlier this year. Lets have a look of what's changed since then: API additions ------------- The first thing you're going to notice that differs is the polished API. Being used by more people now than it was in January, we've added features that where missing before. More functions has been added to the Get/Put monads giving information over bytes read, remaining bytes etc for whenever you need to do custom serialization. You can now also read and write words in host endian order. Instances has been added to handle Double, Float and Ratio. Performance ----------- Decoding speed has been tuned by a rewrite and is currently about half the speed of the lightning fast encoding. Don't hesitate to give feedback on #haskell or by mail, we've always got time for a chat :) The Binary Strike Force, Lennart Kolmodin Duncan Coutts Don Stewart Spencer Janssen David Himmelstrup Björn Bringert Ross Paterson Einar Karttunen John Meacham Ulf Norell Tomasz Zielonka Stefan Karrmann Bryan O'Sullivan Florian Weimer [1] http://article.gmane.org/gmane.comp.lang.haskell.general/14800 -- "The only thing that interferes with my learning is my education." -- Albert Einstein

1 0

(no subject)
by Matthew Brecknell 29 Mar '07

29 Mar '07

I'm attempting to construct an abstract data type with a generalised (deferred) representation. For a simple motivating example, say I am building an abstract data type with this representation: > newtype Foo1 k e = Foo1 (Data.Map.Map k (Data.Set.Set e)) While this is a fine default representation, I would like to be able to substitute IntMap for Map or IntSet for Set in cases where k or e happen to be Int, or simple list-based map and set implementations for types lacking an Ord instance. Following is a prototype of the approach I've come up with so far. It's been quite an adventure just getting this to type-check (due to lack of experience with MPTCs and FDs), so I'd be grateful for comments on whether it is likely to withstand use in real programs, other ways to solve the problem, etc. > {-# LANGUAGE FunctionalDependencies #-} > > -- Map class, with generic newtype wrapper instance. > > class MapLike k v m | m -> k v where > emptyM :: m > insertWithM :: (v -> v -> v) -> k -> v -> m -> m > toListM :: m -> [(k,v)] > > newtype Map m k v = Map m > > instance MapLike k v m => MapLike k v (Map m k v) where > emptyM = Map emptyM > insertWithM f k v (Map m) = Map (insertWithM f k v m) > toListM (Map m) = toListM m > > -- Set class, with generic newtype wrapper instance. > > class SetLike e s | s -> e where > singletonS :: e -> s > unionWithS :: (e -> e -> e) -> s -> s -> s > toListS :: s -> [e] > > newtype Set s e = Set s > > instance SetLike e s => SetLike e (Set s e) where > singletonS e = Set (singletonS e) > unionWithS f (Set s1) (Set s2) = Set (unionWithS f s1 s2) > toListS (Set s) = toListS s > > -- Abstract datatype Foo, whose representation is deferred > -- through the Map and Set newtype wrappers. > > newtype Foo m k s e = Foo (Map m k (Set s e)) > > class FooLike k e s m | m -> k s, s -> e where > emptyF :: m > insertWithF :: (e -> e -> e) -> k -> e -> m -> m > toListF :: m -> [(k,e)] > > instance (MapLike k (Set s e) m, SetLike e s) => FooLike k e (Set s e) (Foo m k s e) where > emptyF = Foo emptyM > insertWithF f k e (Foo m) = Foo (insertWithM (unionWithS f) k (singletonS e) m) > toListF (Foo m) = [ (k,e) | (k,s) <- toListM m, e <- toListS s ] Note that the FooLike class is not strictly necessary to the approach, since its methods could be written as top-level functions, but I thought it couldn't hurt. It does have the advantages of consolidating class constraints in one place, making functional dependencies explicit, and supporting further composition using the same technique.

1 1

Can we do better than duplicate APIs? [was: Data.CompactString 0.3]
by Benjamin Franksen 28 Mar '07

28 Mar '07

[sorry for the somewhat longer rant, you may want to skip to the more technical questions at the end of the post] Twan van Laarhoven wrote: > I would like to announce version 0.3 of my Data.CompactString library. > Data.CompactString is a wrapper around Data.ByteString that represents a > Unicode string. This new version supports different encodings, as can be > seen from the data type: > > [...] > > Homepage: http://twan.home.fmf.nl/compact-string/ > Haddock: http://twan.home.fmf.nl/compact-string/doc/html/ > Source: darcs get http://twan.home.fmf.nl/repos/compact-string After taking a look at the Haddock docs, I was impressed by the amount of repetition in the APIs. Not ony does Data.CompactString duplicate the whole Data.ByteString interface (~100 functions, adding some more for encoding and decoding), the whole interface is again repeated another four times, once for each supported encoding. Now, this is /not/ meant as a criticism of the compact-string package in particular. To the contrary, duplicating a fat interface for almost identical functionality is apparently state-of-the-art in Haskell library design, viz. the celebrated Data.Bytesting, whose API is similarly repetitive (see Data.List, Data.ByteString.Lazy, etc...), as well as Map/IntMap/SetIntSet etc. I greatly appreciate the effort that went into these libraries, and admire the elegance of the implementation as well as the stunning results wrt. efficiency gains etc.. However I fear that duplicating interfaces in this way will prove to be problematic in the long run. The problems I (for-)see are for maintenance and usability, both of which are of course two sides of the same coin. For the library implementer, maintenance will become more difficult, as ever more of such 'almost equal' interfaces must be maintained and kept in sync. One could use code generation or macro expansion to alleviate this, but IMO the necessity to use extra-language pre-processors points to a weakness in the language; it be much less complicated and more satisfying to use a language feature that avoids the repetition instead of generating code to facilitate it. On the other side of teh coin, usability suffers as one has to lookup the (almost) same function in more and more different (but 'almost equal') module interfaces, depending on whether the string in question is Char vs. Byte, strict vs. lazy, packed vs. unpacked, encoded in X or Y or Z..., especially since there is no guarantee that the function is /really/ spelled the same everywhere and also really does what the user expects.(*) I am certain that most, if not all, people involved with these new libraries are well aware of these infelicities. Of course, type classes come to mind as a possible solution. However, something seems to prevent developers from using them to capture e.g. a common String or ListLike interface. Whatever this 'something' is, I think it should be discussed and addressed, before the number of 'almost equal' APIs becomes unmanageable for users and maintainers. Here are some raw ideas: One reason why I think type classes have not (yet) been used to reduce the amount of API repetition is that Haskell doesn't (directly) support abstraction over type constraints nor over the number of type parameters (polykinded types?). Often such 'almost equal' module APIs differ in exactly these aspects, i.e. one has an additional type parameter, while yet another one needs slightly different or additional constraints on certain types. Oleg K. has shown that some if these limitations can be overcome w/o changing or adding features to the language, however these tricks are not easy to learn and apply. Another problem is the engineering question of how much to put into the class proper: there is a tension between keeping the class as simple as possible (few methods, many parametric functions) for maximum usability vs. making it large (many methods, less parametric functions) for maximum efficiency via specialized implementations. It is often hard to decide this question up front, i.e. before enough instances are available. (This has been stated as a cause for defering the decision for a common interface to list-like values or strings). Since the type of a function doesn't reveal whether it is a normal function with a class constraint or a real class method, I imagine a language feature that (somehow) enables me to specialize such a function for a particular instance even if it is not a proper class member. Or maybe we have come to the point where Haskell's lack of a 'real' module system, like e.g. in SML, actually starts to hurt? Can associated types come to the rescue? Cheers Ben -- (*) I know that strictly speaking a class doesn't guarantee any semantic conformance either, but at least there is a common place to document the expected laws that all implementations should obey. With duplicated module APIs there is no such single place.

4 7

Re: Why the Prelude must die
by Lennart Augustsson 28 Mar '07

28 Mar '07

I agree, I think this is what we need. Plus a decision of what names the builtin syntax refers to, like the type of 'a'. -- Lennart On Mar 26, 2007, at 23:30 , Ashley Yakeley wrote: > Sebastian Sylvan wrote: >> The solution is simple: >> * If there is a "module M where" clause in the beginning of the file, >> then it's a "proper" module and shouldn't import the Prelude. >> * If there is no module declaration then it's a "quick'n dirty >> script" >> and should have the Prelude implicitly imported. >> * Interactive interpreters should probably import the Prelude. >> That should take of most issues. > > I think this is ideal. I've always thought writing "import Prelude" > was a good idea if one wants one's module to import the Prelude. > It's one less corner case. > > -- > Ashley Yakeley > > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://www.haskell.org/mailman/listinfo/libraries

5 4