- Libraries - Haskell.org

Re: Text.ParserCombinators.* is a bad name
by dons＠cse.unsw.edu.au 09 Mar '06

09 Mar '06

zednenem: > Bernard James POPE writes: > > > On Wed, Mar 08, 2006 at 04:42:08PM +1100, Donald Bruce Stewart wrote: > > > namespace should be deprecated in favour of: > > > > > > Text.Combinators.ReadP > > > Text.Combinators.Parsec > > > Text.Combinators.HughesPJ > > > > Sounds reasonable. I wonder whether HughesPJ is also a candidate for > > renaming to something more descriptive? (No offence to John and Simon) > > One disadvantage of this scheme is that it obscures the difference > between the parsing combinators and the pretty-printing combinators. > > We wouldn't want to make name of the HughesPJ module too generic, as > there are also other libraries of pretty printing combinators out there, > such as Daan Leijen's PPrint. Yeah, that was one issue. It's not obvious to me what the alternative to HughesPJ would be though. -- Don P.S. It's good to see mailing with a provocative subject line is so effective for getting responses -- a little tip I picked up from Haskell' ;)

2 1

Further Edison comments
by David Menendez 08 Mar '06

08 Mar '06

Some additional thoughts and speculations about Edison: (1) The documentation for FiniteMapX warns that the *With functions are unsafe. > The passed in combining functions are used to choose which element is > kept in the case of duplicates. They are required to satisfy the > precondition that, given two equal elements, they return a third > element equal to the other two. That doesn't make sense to me. Unlike the corresponding functions from SetX, duplication of keys leads to combining elements. It's perfectly reasonable to do things like |Assoc.unionWith (+)| or |Assoc.insertWith (&&)|. (2) I wonder if it would make more sense for Assoc.adjustOrInsert to take a function and a default value, i.e., adjustWithDefault :: FiniteMapX k m => a -> (a -> a) -> k -> m a -> m a (a, a -> a) is isomorphic to (Maybe a -> a), but avoids creating a temporary (Maybe a) value. (3) I have a sketch of a finite-map-to-finite-relation adaptor, newtype Rel m a = Rel (m [a]) instance (FiniteMapX m k) => AssocX (Rel m) k ... Implementing functions like |delete| would be easier if |FiniteMapX| included |update|, a.k.a. |adjustOrDelete|. update :: FiniteMapX k m => (a -> Maybe a) -> k -> m a -> m a WIth it, I could define |delete| more efficiently: delete k (Rel m) = Rel $ A.update f k m where f [a] = Nothing f (a:as) = Just as (4) Sequence and AssocX replicate several functions from their superclasses. It's a small thing, but it bothers me have to define |fmap| and |map| (especially since the documentation only says that they're "ordinarily" the same). I suggest leaving these functions in the Edison interface, but removing them from the classes. That is, Data.Edison.Seq would define |empty|, |singleton|, |append|, |map|, and |concatMap| as aliases: empty :: Sequence s => s a empty = mzero singleton :: Sequence s => a -> s a singleton = return And each implementation would define the usual specialized functions: empty :: Seq a empty = ... append :: Seq a -> Seq a -> Seq a append = ... instance MonadPlus Seq where { mzero = empty; mplus = append } This preserves Edison's interface while eliminating the duplication (and possible conflicts) in the class dictionaries. The difference would only be noticeable in the instance declarations. (5) Many of the unsafe functions have preconditions which can be checked using |assert|. In my SkewBinary heap, for example, I have unsafeInsertMin k a h = assert (null h || k <= root h) $ T k a h E That sort of thing might be useful during development. (6) I've implemented a SkewBinary heap as an associated collection and collection instances for Data.IntSet. If you're interested, I can send you a copy or submit a patch. -- David Menendez <zednenem(a)psualum.com> <http://www.eyrie.org/~zednenem/>

2 1

darcs patch: Only import Control.Concurrent when using GHC
by Einar Karttunen 08 Mar '06

08 Mar '06

Wed Mar 8 17:21:24 EET 2006 Einar Karttunen <ekarttun(a)cs.helsinki.fi> * Only import Control.Concurrent when using GHC

1 0

Annoucing alternative to Text.Regex
by Chris Kuklewicz 08 Mar '06

08 Mar '06

This message is cross-posted to haskell-cafe(a)haskell.org and libraries(a)haskell.org Hi, Working on the shootout (specifically http://shootout.alioth.debian.org/gp4/benchmark.php?test=regexdna&lang=all ), it was impossible to use Text.Regex since it was too slow (it would reach the timeout limit, such as an hour, where TCL takes 3.21 seconds ). So we had to work around this by implementing our own regex engine. I have tooled up an all-parsec version that I think can be a nearly drop-in-alternative to Text.Regex. I will describe it a bit and then ask for advice. It takes the string form of the regular expression and uses Parsec to create a (data Pattern) tree structure. This recognizes all of "man re_format" including back references, missing only the [[:>]] or [[<:]] extension (word boundaries). It also accepts new modifiers '?' and '+' to be used like "a*?" and "a*+" for lazy and possessive matching. The Pattern form is amenable to simplification, and some easy simplification are performed. Then the Pattern is transformed in a Parsec parser that will match the input (from the beginning only) and return all the captured sub-expressions. It also supports (get|set|update)UserState functions. It should return the longest match when all the pattern elements are greedy, i.e. no lazy or possessive modifiers are used. With lazy or possessive modifiers the longest alternative is used, but this may not be the longest overall match. (Parsec keeps track of line and column position, but not the number of characters, which had to be added.) Note that the pattern "(.)Q\1" can be used to match strings like "aQa", and "(a|b\1)+" matches all of "ababba". The Text.Regex compatibility code embeds the generated Parsec parser into more complicated parsers and runs them to emulate the different functions in the Text.Regex interface. It is possible to extend all of this in several ways: 1) Turn the Pattern into simpler parsec, e.g. if the expression captures are not needed 2) When possible, turn the Pattern into a faster DFA parser instead of Parsec 3) Create parsers that with different semantics than "longest match", e.g. left-biased 4) Creates parsers that return all matches 5) Employ smart optimizations for special forms of Pattern 6) With an earlier version, I made a proof of principle String -> ExpQ transformer that created Parsec at compile time using Template Haskell. This could be updated. Not done: testing. (If you have clever things to throw at it, pass them along). Not done: benchmarking (though it should usually beat Text.Regex). And now I want to ask for advice. If there is interest I could post the code somewhere, but I don't own a stable place to put it at the moment. Is there a canonical place on the net to put small Haskell modules (28 kB uncompressed) ? Is there some darcs-repository I could insert it into ? Also, is there a library style guide somewhere with best practices?

2 2

Edison 1.2rc2
by Robert Dockins 07 Mar '06

07 Mar '06

Greetings! The second release candidate for Edison 1.2 is now ready for comments. The notable changes from RC1 are: * add strict variants of all folds and reduces * reverse argument orders to 'rcons' and 'lookup*' in Sequence * Add symbolic operators for lcons, rcons, append, and lookup from the Sequence API * Add symbolic operators for subsetEq, difference, intersection and union from the set API * rename 'single' to 'singleton' in all APIs * rename 'intersect' to 'intersection' in Collection and Associated Collection APIs * add 'adjustOrInsert' to the Associated Collection API (see http://www.haskell.org//pipermail/libraries/2006-February/ 004952.html for a use case) And the following are the remaining major issues I'd like to get feedback about: -- Edison defines 'subset' and 'subsetEq' in the set API. Data.Set has operations with the same meanings named 'isProperSubsetOf' and 'isSubsetOf'. I am considering adoping the Data.Set names, but they are quite a bit longer. Also what about the meaning of "subset" vs "proper subset"? What do you find most intuitive? -- Data.Map defines 'isSubmapOfBy' and 'isProperSubmapBy'. Edison has no corresponding API methods. Are they important enough to add? -- What do you think about the symbolic operators? Is the fact that (++) clashes with the Prelude a problem? Should the operators be folded into the "Data.Edison" module instead? (see http://www.eecs.tufts.edu/~rdocki01/docs/edison/Data-Edison- Sym.html) In addition, I'm interested in any API related feedback you might have. Code and docs can be found at the project website: http://www.eecs.tufts.edu/~rdocki01/edison.html Or you can go directly to the haddock docs: http://www.eecs.tufts.edu/~rdocki01/docs/edison/index.html Or the darcs repo: http://www.eecs.tufts.edu/~rdocki01/edison/ Thanks, Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG

7 14

n-Tuple maps
by Jean-Philippe Bernardy 07 Mar '06

07 Mar '06

Hello Adrian, On 3/6/06, Adrian Hey <ahey(a)iee.org> wrote: > Hello Jean-Philippe, > > I haven't had much time to study this, but in the light of recent > discussions about generalised tries I played about a little last night > and did have a go at producing n-Tuple maps from instances of your classes. > e.g. for pairs I ended up trying to define something like this.. > > instance (MapLike c1 k1 c2, MapLike c2 k2 a) => MapLike (Map2 c1) (k1,k2) a > where.. Not sure I got what you want to do exactly, but here's what I came up with: (using Indexed because it's lighter, but the idea is the same for Map.) module Map2 where import Data.Collections newtype Map2 c1 c2 k1 k2 v2 = Map2 c1 instance (Indexed c1 k1 c2, Indexed c2 k2 v2) => Indexed (Map2 c1 c2 k1 k2 v2) (k1,k2) v2 where (!) (Map2 c1) (k1,k2) = (c1 ! k1) ! k2 > I must admit I found it hard going, but maybe I'm just using it wrong and > I didn't have much time to play about with alternatives. Perhaps you'd care > to give it a shot. You "just" need to witness the types you define Map2 for as parameters. A bit tricky, I grant you, but nonetheless logical. Once I got used to it I didn't find it any more difficult than the constructor-class approach. Cheers, JP.

2 1

Applicative and Functor
by Ashley Yakeley 07 Mar '06

07 Mar '06

Shouldn't Applicative be a subclass of Functor? "<$>" can then be dropped. The Functor laws are this: fmap id = id fmap (a . b) = (fmap a) . (fmap b) These are already implied by the Applicative laws: (<$>) id = id Proof: LHS = (<$>) id = \v -> id <$> v = \v -> (pure id) <*> v -- "pure application" = \v -> v -- "identity" = id = RHS QED. (<$>) (a . b) = ((<$>) a) . ((<$>) b) Proof: LHS = (<$>) (a . b) = \v -> (a . b) <$> v = \v -> pure (a . b) <*> v -- "pure application" = \v -> (pure ((.) a) <*> (pure b)) <*> v -- "homomorphism" = \v -> ((pure (.) <*> (pure a)) <*> (pure b)) <*> v -- "homomorphism" = \v -> (pure a) <*> ((pure b) <*> v) -- "composition" = \v -> (a <$> (b <$> v)) -- "pure application" = ((<$>) a) . ((<$>) b) = RHS QED. -- Ashley Yakeley

2 8

a proposal regarding libraries
by Isto Aho 04 Mar '06

04 Mar '06

Hello, What do you think about the following proposal to try to activate people to build up new not-yet-seen Haskell libraries? I remember a discussion a couple of months ago where somebody said that it is more important to have imperfect libraries than to not have a perfect one. This proposal aims for populating your favorite missing libs... First, the libs could be diveded into two parts: to those that are under construction (where some reorganization may occur in near future ~ dev libs) and to those that are more or less stable (where reorganization is not likely to occur in the next few years ~ stable libs). And these libs could be distributed with the Haskell compilers so that they are usable instantly. Second, to populate the dev libs with new funcs, it would be relatively easy to organize monthly competitions with the new HaskellWiki-pages. Idea could be something like - On the first day of the month, a lib design is released on the HaskellWiki, giving 12 competitions a year. - Who completes most of the funcs, documentation, examples FIRST, etc, wins the competition. - Competition tasks (e.g. an individual func) are weighted somehow. - The HaskellWiki has page histories, which can be used to make judgements in cases where a task has no clear winner. - Prices: a name on HaskellWiki Hall of the Fame page or something similar... If there is enough interes in this kind of activity, there is a need for a couple of volunteers to organize everything and to work as judges on the competition days (or weeks). They should decide, what the competition is about etc. What do you think? Pros & Cons? Would you take part in this kind of competition(s), if these were organized? Anybody interested in developing this idea further? I'll guess many people have their favorite missing libs that could be build this way in collaboration and so do I. br, Isto

4 10

library reorganisation
by Simon Marlow 04 Mar '06

04 Mar '06

This mailing list seems to be an appropriate place to discuss: http://cvs.haskell.org/trac/ghc/ticket/710 Rather than keep adding comments to the ticket, I'll continue the discussion here. I don't suggest changing the module name of Text.Html. Ross suggests moving it to the network package - I'm abivalent about that. A completely separate package (html) would be fine by me. In reply to maeder: yes the package boundaries do reflect implementation dependencies. I don't think this is a big problem. In theory we could rename /everything/ in base to be PackageBase.* and then re-export the actual interfaces from a bunch of separate packages, but that doesn't really buy much, and it's a lot of work. Having said that, I'm open to arguments for extracting Data.Array.* into a separate package. I almost suggested removing Text.Printf, but it seems too small to put in a package of its own and I don't know where else to put it :-) If we had a separate 'text' package it could go there, maybe with Text.PrettyPrint? Cheers, Simon

4 5

RFC: Collection Framework, reprise.
by Jean-Philippe Bernardy 03 Mar '06

03 Mar '06

Hello, I'm glad you see so many good point in my design. I must say however that the operator names are (c) Ross Paterson :) On 2/21/06, Robert Dockins <robdockins(a)fastmail.fm> wrote: > Well, I have to begin with the caveat that I am not a data structures > expert, and that the design of Edison is almost entirely due to Chris > Okasaki. That said, I can certainly share my opinion. In no > particular order: > -- Your use of two type parameters to model read-only or unobservable > collections is very interesting. I wonder, though, how useful it > actually is. I facilitates some interesting possibilities with > views, but I can't think of any compelling use cases. I sort of > dislike the fact that it can turn certain of the class methods > "useless", but maybe the idea just hasn't grown on me yet. The truth is, I hope this will become nicer when (if) we move to associated types. I need to play a bit more with Phrac to have a clearer idea though. > -- I like the idea of views generally, and I'm now trying to think if > there is a good way to work something like them into Edison. > -- The 'isSingleton' method seems unnecessary. Are singleton > collections interesting enough to supply a special test for them? This is based on Christan Maeder idea. We are planning to move to AVL trees for A. Hey, which do not provide a O(1) size function. A singleton test thus becomes valuable, and since costs next to nothing to add to the class I decided to to it. > -- Your 'lookup' method has a Monad context, which I assume is the > 'NotJustMaybe' pattern, but 'front' and 'back' return Maybe. You > should probably pick one style and stick to it. True. > -- Qualified infix functions look horrible. I know you say this > module should be imported unqualified, but with Prelude clashes > people qualify it anyway. I'd suggest you stick to regular prefix > functions for your class methods and define the infix functions as > the appropriate aliases. That way people importing qualified can > still use something reasonable looking. > -- In a related thread I've been discussing argument orders. I think > I've just about come to the decision that all the Edison API > functions will take the collection argument last, including the > troublesome 'rcons'. If you take my suggestion to remove infix > symbols from your classes, I suggest you also make your right cons > and index functions take the collection argument last. However, I'd > probably leave the symbols as is, so that, e.g., (|>) = (flip rcons). If i understand this correctly, you suggest that regular functions should have a prefix meaning, whereas operators should have infix meaning (also in the light of your answer to Ross). I remember some peope spoke against this when we tuned Data.Map (& friends) API some years ago. I guess the reason is that some functions cannot be assigned a clear enough operator (isSubsetOf, etc.) > -- In fact, I like your right and left insert symbols so much, I may > adopt them myself. > -- You claim that 'union' takes an unspecified element in the case of > duplicates, but you also claim it is commutative. You need to > specify in what sense you claim commutativity; your collection class > doesn't require an Eq or Ord instance, and the claim seems very > suspect if you mean up to identity. Similar with intersection. This has been written in a hurry, and I didn't mean anything very formal. We have re-hashed implied meanings of Eq and Ord quite a few times however, and the general idea is that we require Eq to mean equality, and similarly for Ord, otherwise all bets are off. This is better stated in a general comment rather than on the definition on union though. > -- Does 'adjust' affect all elements with the given key, or just a > single unspecified one? The class has the (implicit) assumption that a key cannot exist twice. The semantic could be generalized however. > -- 'Indexed' doesn't have any notion of bounds. That seems like a > pretty necessary concept. Humm, I see now that MapLike is a subclass > of Indexed. Perhaps then you should have 'DenseIndexed' or > 'ArrayLike' which has bounds related methods together with the > "denseness" property. It seems like the class you suggest to add would become a replacement for the Array class. > > Overall, I'd say the methods you have carved out seem to be the ones > that are most-used, with the notable exception of 'head' and 'tail' > for sequences. Rather, I intend to start with those. It seems easier to add than to remove. > If you are attempting to go for a fairly minimal set > of operations (that's more or less what I read your design goals as > saying), then the only method I'd consider adding is a strict fold. > People get irritated if they can't, e.g., sum the elements in a > collection without building a gajillion unnecessary closures. Every day I pray for a genius to come with the generic solution to eliminate unnecessary lazyness :) Thanks again for the helpful comments. JP.

11 17