- Libraries - Haskell.org

typo in Data.Binary documentation
by Chad Scherrer 09 Jan '08

09 Jan '08

The latest Data.Binary documentation says instance of Binary should have get . put == id But this doesn't typecheck! I'm guessing it's probably supposed to say decode . encode == id -Chad

4 3

[Fwd: Re: Maps]
by Christian Maeder 08 Jan '08

08 Jan '08

-------- Original Message -------- Subject: Re: Maps Date: Tue, 08 Jan 2008 05:35:07 -0800 From: Mike Hamburg <mike(a)mikehamburg.com> To: Christian Maeder <Christian.Maeder(a)dfki.de> CC: paul(a)cogito.org.uk References: <47832E64.3090008(a)dfki.de> So here's an approximation of my problem. I have a map of objects, possibly aggregated from different sources. They have (in a case of medium complexity) type (t,u) where the t represents the source and u represents the position within that source. They're derived from something like a Map t (Map u v), but it is convenient for other reasons to represent this as an actual Map (t,u) v. (It's possible that I'll end up hacking around this with some type class or another, but let's ignore that possibility for now.) I need to efficiently represent ranges of objects to be viewed or deleted from this map, in such a way that the map library can extract or delete them quickly. But I might have, say, only a t value, and no values of u available. On Tue, 2008-01-08 at 09:03 +0100, Christian Maeder wrote: > I'm not quite sure what you are asking for here. Why does the first > argument take both a key and a value, and what is the Ordering saying? > >From your description I was expecting something more like: > > interval :: k -> k -> Map k v -> Map k v > > Are you saying that if the Ordering is "EQ" then the key is within the > range? Yes. The "ordering" produced is a sort of disjunctive ordering: it's either LT all, or GT all, or EQ at least one element in the interval. I suppose my version should really have type (k -> Ordering) -> Map k v -> Map k v because the values shouldn't come into play unless they're monotonically dependent on the keys. > Take a look at my Ranged Sets library (on Hackage) for a complete > treatment of the concept of ranges within an ordered type. I can > imagine something like > > rangedSetMap :: RSet k -> Map k v -> Map k v Something like an RSet, with the following operations: union, singleton, Range -> RangeSet, ... upcast :: RangeSet t -> RangeSet (t,u) -- and similar for other product types intersection, difference :: Map k v -> RangeSet k -> Map k v > where the resulting Map only contains the keys that are in the RSet. At > present you would have to do that by iterating through the Map, but I > can imagine a more efficient method. Alternatively the Boundary type > defined in that library might be used: it splits an ordered type into > values above and below a boundary. (Two Boundary values make a Range, > and an ordered list of non-overlapping Ranges is an RSet). Yes. But I think what you need to efficiently implement this is some sort of implicit cut, of the form (k -> Something) -> Map k v -> (Map k v, Map k v). > Paul. Also, I'm sort of curious: in C/C++/Java/etc, you can produce a Dense type which has: instance (Eq, Ord, Bounded) Dense between :: Dense -> Dense -> Dense -- if a < b then a < between a b < b This is sort of a lie: between is not referentially transparent, in that two calls to (between a b) may produce results that aren't ==. Still, the efficiency is impressive: ==, >, <, etc are O(1) 'between' is O(log n) where n Dense's are currently live. You can actually make it O(1), but the constant is big, so people don't. total space usage is O(n) integers of 2(log n) bits each Is there any way to even approach this in Haskell? I mean, you can use [Int], but that's not nearly so fast... Mike

3 2

ANN: Build fixed for regex-base,posix,compat,pcre
by ChrisK 07 Jan '08

07 Jan '08

ANNOUNCEMENT: Build fixed for regex-base, regex-posix, regex-compat, regex-pcre The changes are mainly to the Cabal build files to support ghc-6.8 and ghc-6.6 simultaneously. They definitely work with cabal version 1.2.3.0 (required for regex-pcre). The regex-base, regex-posix, and regex-compat packages also seem to work with cabal-1.2.2.0 (but not regex-pcre). The darcs repositories under http://darcs.haskell.org/packages/regex-unstable/ hold the new code. I have uploaded new versions of the most popular regex-* packages to hackage: Mon Jan 7 13:18:00 PST 2008 ChrisKuklewicz regex-pcre-0.94.1 Mon Jan 7 13:05:57 PST 2008 ChrisKuklewicz regex-posix-0.93.1 Mon Jan 7 13:04:49 PST 2008 ChrisKuklewicz regex-base-0.93.1 Mon Jan 7 06:50:54 PST 2008 ChrisKuklewicz regex-compat-0.91 I would like to thank everyone who sent me updated, and particularly Olivier Boudry who sent patches. These build fixes have only been tested with ghc-6.6.1 on Mac OS X 10.5.1 (powerpc) and with ghc-6.8.2 on Linux (x86). Happy New Year, Chris Kuklewicz

1 0

[Fwd: Re: Maps, was Re: GHC source code improvement ideas]
by Christian Maeder 07 Jan '08

07 Jan '08

-------- Original Message -------- Subject: Re: Maps, was Re: GHC source code improvement ideas Date: Fri, 04 Jan 2008 14:38:22 -0800 From: Mike Hamburg <mike(a)mikehamburg.com> To: Christian Maeder <Christian.Maeder(a)dfki.de> References: <477D987C.2090806(a)gmail.com> <477E3D69.5000307(a)gmail.com> <477E5301.8010700(a)dfki.de> On Fri, 2008-01-04 at 16:38 +0100, Christian Maeder wrote: > Simon Marlow wrote: > > Regarding Data.Map, I'd be interested in trying out AVL trees instead, > > to see if they have better performance, but then we'd have to import the > > code of course. > > Surely, we want the best maps possible for ghc and as public library > (and minimize maintenance). > > The problem is to agree on a suitable interface. I would suggest to take > (or only slightly change) Daan's interface (the current Data.Map) and > improve the underlying implementation possibly using (i.e. Adrian Hey's) > AVL trees. If anyone is off tweaking the Data.Map library, I have a simple request (which I sometimes end up implementing in hacked up versions of Data.Map). There should be some way to extract an implicitly defined interval from the map, i.e. interval :: (k -> v -> Ordering) -> Map k v -> Map k v or partitionMonotoneWithKey :: (k -> v -> Bool) -> Map k v -> (Map k v, Map k v) or similar. The important thing about these operations is that they can be made to run in O(log n) time if you have the tree structure of the map, and (so far as I know) can't if you don't. An example of when this is useful is if you have a Map (a,b) c, and wish to extract the submap for a particular a-value, or a range of a-values. Mike

2 1

new language extensions
by Duncan Coutts 07 Jan '08

07 Jan '08

All, GHC 6.8 has a lot of new names for language extensions which are not yet listed in Language.Haskell.Extension: UnicodeSyntax PatternSignatures UnliftedFFITypes LiberalTypeSynonyms TypeOperators PArr RecordWildCards RecordPuns DisambiguateRecordFields OverloadedStrings GADTs MonoPatBinds RelaxedPolyRec ExtendedDefaultRules UnboxedTuples DeriveDataTypeable ConstrainedClassMethods These are the extension names you can list in the "extensions:" field in a .cabal file and are also in the {-# LANGUAGE #-} pragma. So I propose we add all of these to the Extension enumeration data type. I'd like to keep this addition separate from the proposal to make Extension a String or newtype String, since I expect even in that case we need a central list of extensions so different implementations can agree on names when they implement the same extensions, or to ensure they pick different names for different extensions. It'd also be nice if we could document all these extensions in the Language.Haskell.Extension module so we can refer to it from the cabal documentation about the extensions field. Duncan

5 10

Generalise type of forever
by Don Stewart 07 Jan '08

07 Jan '08

It's been pointed out by a couple of people that the type of forever is overly constrained. We get a few more useful programs for free if we change the type: [generalise type of 'forever' from returning m () to m a Don Stewart <dons(a)galois.com>**20080107062656] { hunk ./Control/Monad.hs 42 - , forever -- :: (Monad m) => m a -> m () + , forever -- :: (Monad m) => m a -> m a hunk ./Control/Monad.hs 190 -forever :: (Monad m) => m a -> m () +forever :: (Monad m) => m a -> m a } In particular, fail breaks out nicely. > forever Nothing Nothing Deadline: 12th January. -- Don

2 2

bytestring 0.9.0.4
by Don Stewart 05 Jan '08

05 Jan '08

2.5 years after the first release, bytestring 0.9.0.4 is now available on hackage, http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bytestring-0.9.0… Changes since the 0.9 release include: * support for bytestring literals (use -XOverloadedStrings) * make Data.ByteString.Lazy.Char8.lines lazier * fixes Handle resource leak in getContents/readFile * faster isSpace operations * performance improvements The most notable change is the instance IsString for strict and lazy bytestrings, enabling bytestrings to be written as direct string literals, without needing 'pack'. That is, the following is valid: import Data.ByteString.Char8 main = print ("abcdef" :: ByteString) (and the compile will even turn the pack into a no-op at compile time). Or, using the (soon to be released pcre-light package), bytestring regex literals can be written as: compile "a(.*)b" where compile :: ByteString -> Either String Regex With -XOverloadedStrings, the 'pack'for the regex is inferred. -- Don & Duncan

2 2

Case-insensitive formats for Data.Time.Format?
by Bjorn Buckwalter 27 Dec '07

27 Dec '07

Hello all, Is there a compelling reason to not make the formats in Data.Time.Format case-insensitive when parsing? This would apply to the months, weekdays, time zone. (I see there are already two formats %p and %P corresponding (confusingly) to AM/PM and am/pm respectively.) What got me thinking about this is that I'm being supplied with dates on the format "26 DEC" which will not parse without munging. I suspect such situations are fairly common? Also, is there a way to have the parser assume a century of 20 with the format %y? Thanks, Bjorn

2 2

getOpt return record of type a rather than [a]
by Henning Thielemann 19 Dec '07

19 Dec '07

The current version of System.Console.GetOpt.getOpt returns a list of values, where the element type has usually one constructor per option. data Flag = Verbose | Version | Input String | Output String | LibDir String What I more like to receive is a record consisting of one constructor and many fields, where optional options are of type Maybe, options with multiple occurrence are of type list. data Flag = Flag { verbose :: Bool, version :: Bool, input :: Maybe FilePath, output :: Maybe FilePath, libdir :: FilePath } Then we would need data ArgDescr a = NoArg (a -> a) ReqArg (String -> a -> a) String OptArg (String -> a -> a) String e.g. OptArg (\path flags -> flags {input = Just path}) "FILE" I feel this approach is so natural, that someone must have implemented it already.

5 7

Build Log Question
by Dominic Steinitz 17 Dec '07

17 Dec '07

I was about to update the crypto package when I noticed that there is now a "build log" on each package page. What does this mean and what should I do as package maintainer? Many thanks, Dominic. >> Step 1 - configuring Crypto-3.0.3 > > Configuring Crypto-3.0.3... > Setup.hs: At least the following dependencies are missing: > NewBinary -any > >>> Terminated due to an error. >>> Step 1 - configuring ASN1-0.0.1 > > Configuring ASN1-0.0.1... > Setup.hs: At least the following dependencies are missing: > NewBinary -any > >>> Terminated due to an error.

2 1