March 2006 - Libraries

Re: [Haskell-cafe] STUArray
by Frederik Eaton 12 Mar '06

12 Mar '06

On Sun, Mar 12, 2006 at 09:05:58AM +0300, Bulat Ziganshin wrote: > Hello Frederik, > > Sunday, March 12, 2006, 5:58:42 AM, you wrote: > > FE> Perhaps some sort of warning in the documentation for STUArray is in > FE> order, until Bulat's code can be incorporated? > > excellent idea. you can make diff for Data.Array.ST/IO and send it to the > libs maillist $ diff -u libraries/base/Data/Array/IO.hs{.old,} --- libraries/base/Data/Array/IO.hs.old 2006-03-12 07:29:28.000000000 +0000 +++ libraries/base/Data/Array/IO.hs 2006-03-12 07:24:27.000000000 +0000 @@ -11,6 +11,8 @@ -- -- Mutable boxed and unboxed arrays in the IO monad. -- +-- XXX I'm not sure what to put here. +-- ----------------------------------------------------------------------------- module Data.Array.IO ( [1]$ diff -u libraries/base/Data/Array/ST.hs{.old,} --- libraries/base/Data/Array/ST.hs.old 2006-03-12 07:29:58.000000000 +0000 +++ libraries/base/Data/Array/ST.hs 2006-03-12 07:39:41.000000000 +0000 @@ -10,6 +10,15 @@ -- -- Mutable boxed and unboxed arrays in the 'Control.Monad.ST.ST' monad. -- +-- Beware that it is currently not easy to use STArray +-- polymorphically, since conditioning on "forall s . MArray (STUArray +-- s) e (ST s)" is impossible. Hopefully this should be fixed soon +-- (with an Unboxed class, Bulat Ziganshin is working on it). +-- +-- See http://www.mail-archive.com/haskell%40haskell.org/msg17085.html +-- +-- Use IOArray if you want your element types to be polymorphic. +-- ----------------------------------------------------------------------------- module Data.Array.ST (

1 0

darcs patch: add Data.Set.notMember and Data.Map.notMember / generalized infix notation use case
by Jean-Philippe Bernardy 11 Mar '06

11 Mar '06

Patch applied. Still, In time, I suppose the somewhat ugly not (element `member` set) sould be addressed by a mixture of generalized infix notation and the definition of such an operator: f /. g = \x y -> f (g x y) allowing element `not/.member` set Cheers, JP. On 3/11/06, Cale Gibbard <cgibbard(a)gmail.com> wrote: > > I don't like notElem either > > > > > * quite useful for cleaning up guards: > > > > > > f x | not (x `Set.member` map) && foo = ... > > > is hard to read. > > > > You may swap quards (or the "then" and "else" branches of "if"), or > > avoid the infix notation (which is horrible in this case anyway). > > > Although I'd normally agree with negated versions of things being > somewhat redundant, the infix version here is rather important, since > one often wants the code to look the same way as the mathematics. The > symbols \in and \not\in are both usually written infix, and that's not > going to change soon. Putting the membership operation in between is > nice, because we read the guard here as "If x is a member of xs > then..." rather than "If member x xs then..." anyway. Perhaps if the > proposal to allow somewhat more general expressions as infix operators > goes through (which I'm actually ambivalent about), I'd feel different > about this case. > > If you want to reduce redundancy, let's unify the 3 separate ways to > say 'map'. :) > > - Cale > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://www.haskell.org/mailman/listinfo/libraries >

1 0

Trie implementation
by Keith Wansbrough 10 Mar '06

10 Mar '06

Hi... I was writing some code yesterday to walk over a directory tree, and needed a Trie. Not seeing one around, I wrote a basic implementation of the functions I needed (attached below). Has anyone else done this? Should I polish it up and offer it for inclusion in Data? --KW 8-)

7 8

Range queries and Data.Map
by Einar Karttunen 10 Mar '06

10 Mar '06

Hello Data.Map seems to lack a way to perform range queries like "fetch all elements between keys low and high". The naive implementation is easy: range :: Ord k => k -> k -> Map.Map k v -> [(k,v)] range low high = toList . fst . split high . snd . split low But this is not very fast for larger maps. Maybe this operation could be provided in Data.Map? - Einar Karttunen

2 1

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

10 Mar '06

* Firstly, a library naming issue. Text.ParserCombinators feels like a clunkey name. This week I was working on a set of regex combinators, that ideally would go under: Text.Combinators.Regex but we're stuck with Text.ParserCombinators.Regex. Making me think that: Text.ParserCombinators.ReadP Text.ParserCombinators.Parsec Text.PrettyPrint.HughesPJ namespace should be deprecated in favour of: Text.Combinators.ReadP Text.Combinators.Parsec Text.Combinators.HughesPJ Reflecting the wide variety of text-manipulation combinators we use. The latter seem more elegant. Parsec in particular can lead to some noisy import statements in its current namespace. * Secondly, an FAQ on #haskell is "Where is fst3/snd3/thd3?" Lacking some fun generic system for hacking at tuples, perhaps fst3/snd3/thd3 should be put back into the base library under Data.Tuple, next to fst/snd? I note they were in (at least some versions of) Haskel 1.2, and they're even defined locally in GHC.PArr. I'll draft the patches if people think these are reasonable. Cheers, Don

12 18

unboxed arrays for nhc/jhc
by Bulat Ziganshin 09 Mar '06

09 Mar '06

Hello , i'm now working on alternative unxboxed arrays implementation, based on the Oleg Kiselyov idea this implementation is already compatible with Hugs and GHC, now i plan to make it NHC-compatible. i have the following question - is NHC implements 1) strict ST monad 2) unsafeIOtoST operation 3) Data.Array.* if nhc don't supports ST/unsafeIOtoST, then i plan to use the following ST monad emulation: type ST a = IO a unsafeIOtoST = id runST = unsafePerformIO also i plan to use this emulation layer for JHC. is this can work? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

3 6

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