- Haskell-Cafe - Haskell.org

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

Re: Why the Prelude must die
by David House 28 Mar '07

28 Mar '07

On 28/03/07, Jeffrey Yasskin <jyasskin(a)gmail.com> wrote: > I would vote for a Combinators module with the most important > combinators, and a somewhat larger Prelude to support quick scripts > and demonstrations. I'd hate to have to import a module just to get at ($). Like I've mentioned before, some combinators are so ubiqutos they're almost like syntax. Seeing as the actual syntax will always be in scope, these common combinators would also have to be in scope all the time, which means placing them in the narrowed Prelude. -- -David House, dmhouse(a)gmail.com

1 0

Haskell and a new web developement mailinglist?
by Marc Weber 28 Mar '07

28 Mar '07

I've been talking to Chris Eidhof the last days and we'd like to suggest adding another specialized haskell mailinglist: Haskell and web developement. I think the global interest will increase in the feature, libraries are evolving and it would be nice to have a place to discuss them. Any comments? If there is no veto where can I request it? haskell-admin(a)haskell.org ? Marc

5 7

cost of modules
by Fawzi Mohamed 28 Mar '07

28 Mar '07

I decided to cleanup my program by splitting it in different modules. As I was curious about the cost of splitting it, or dually the efficiency of the intermodule optimization I timed it before and after the split. These are the results (ghc-6.6.20070129 on Linux AMD64): Original: 3 Modules with the computational one with an export list real 0m0.385s user 0m0.378s sys 0m0.003s time:100% Variant 1: split computational module in 6 submodules without export list, kept computational module reexporting the stuff with an export list real 0m0.467s user 0m0.464s sys 0m0.003s time: 122% Variant 2: like Variant 1 but removing the old computational module (no reexport list) 134% real 0m0.513s user 0m0.506s sys 0m0.003s All the functions in my modules have type specialized signatures, so non-specialization should almost never be an issue. The module with the Main function was not the exported one. So 20% speed hit, I had hoped for 0, but it is not unbearable (even if my code has to be as fast as possible, this was a very short run), probably I will keep it split to have cleaner code. Not I will have to write an export list for each module a see it the things improve, and how much. If someone has an idea on how else I can improve timings please tell me. Fawzi

7 9

infinite lists
by Matthias Fischmann 27 Mar '07

27 Mar '07

hi, it just took me an eternity to undestand a bug in my code *after* i had narrowed it down to eight lines or so. and as these bugs go, i feel very good about having found it and have to share it. although it's probably not that exciting to anybody except me. (-: here is the bug, narrowed to four lines. a function that only sometimes terminates. f = do n <- randomRIO (0,5) let l = replicate n '*' i = join $ repeat l -- infinite extension print (take 12 i) how many seconds does it take you to shout "you idiot!"? :-) spoiler below. (what would have been your fix?) cheers, matthias =================================================================== spoiler. the problem is that l is sometimes empty, and taking an element out of an infinite concatenation of empty lists takes even longer than understanding that that takes quite long. just deal with the empty-list case separately: g = do n <- randomRIO (0,5) let l = replicate n '*' i | null l = [] | otherwise = join $ repeat l print (take 12 i)

3 3

(newbie) instance Enum MyType where, smarter way?
by Adrian Neumann 27 Mar '07

27 Mar '07

-----BEGIN PGP SIGNED MESSAGE----- Hash: RIPEMD160 Hello, I defined an enumeration datatype like this data MyType = One | Two | Four | Eight and want to make it an instance of the class Enum. deriving Enum won't do what I want, as it labels the items 0,1,2,3. Is there a better way to do this than instance Enum MyType where fromEnum One = 1 fromEnum Two = 2 ... toEnum 8 = Eight Something like instance Enum MyType where fromEnum One = 1 fromEnum x = 2*pred x toEnum 1 = One toEnum x = succ (toEnum x `div` 2) Which doesn't work because succ and pred are not (properly?) defined. Is there a way to let deriving Enum do *some* of work (i.e. defining succ and pred) while manually defining the other functions? -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.7 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGCTRJ11V8mqIQMRsRA4GFAJwKaxQoKdEW91pHUskzJadDvh7lXgCeLg6P dmQKcjRZEg4fqoZfQ4jOuhg= =RWQ+ -----END PGP SIGNATURE-----

3 2