January 2008 - Libraries

Add 'subsequences' and 'permutations' to Data.List (ticket #1990)
by Twan van Laarhoven 10 Jan '08

10 Jan '08

Hello all, As Thomas Hartman noted in a recent cafe thread [1], haskell 1.3 included the functions 'subsequences' and 'permutations'. I think these functions are quite useful, and I don't know why they were ever removed. This is a proposal to add these two functions to Data.List. The implementation is taken directly from the Haskell 1.3 report [2]. Trac ticket: #1990 Discussion period ends: January 7th (since there is a holiday comming up) Twan [1] http://article.gmane.org/gmane.comp.lang.haskell.cafe/33535 [2] http://haskell.cs.yale.edu/haskell-report/List.html

8 21

Tests in Cabal
by Adrian Hey 10 Jan '08

10 Jan '08

Hello, I've been playing about with the option to add tests to packages and have modified the Setup.hs as follows.. import Distribution.Simple import MyPackage main :: IO () main = defaultMainWithHooks (simpleUserHooks {runTests = myTests}) myTests :: Args -> Bool -> PackageDescription -> LocalBuildInfo -> IO () myTests _ _ _ _ = <whatever> Which I think is the right thing to do if I understand the docs. The first problem I come up against is that in order to do this practically all the modules from the package need compiling by runghc (even during the configure stage presumably). As I guess most people will be using runHaskell/runghc to do this it seems like this will all take quite a bit of time. In my case the process fails completely because the package library files need CPPing and is seems runghc doesn't do this (by default at least). Is this really the way tests are supposed to be included? It doesn't seem workable to me. I wonder if it would be better to just build the lib first (without tests) and then separately build one or more test executables? What does everyone else do about this? Thanks -- Adrian Hey

3 3

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