- Libraries - Haskell.org

ANNOUNCE: Cabal 1.2.0 released
by Thomas Schilling 07 Sep '07

07 Sep '07

The Haskell Cabal The Common Architecture for Building Applications and Libraries. <http://www.haskell.org/cabal> We are pleased to announce that Cabal version 1.2.0 is now available. Changes: The major new feature in this release is support for Cabal configurations. This allows package authors to more easily adopt their package descriptions to different system parameters such as operating system, architecture, or compiler. In addition, some optional features may be enabled or disabled explicitly by the package user. Many other new features and tool support has been added, among others: - Support for hscolour (haddock links to coloured source code). - Support for pkg-config (allows specifying dependencies on many C libraries). - Specification of build-tool dependencies. - Better default installation paths on Windows. - Seperate "includes" and "install-includes" fields - Install paths can be specified relative to each other. - Many more new small features, command line flags and bugfixes. For a more exhaustive list, see http://www.haskell.org/cabal/release/rc/changelog Please note that this is a .0 release, so we would appreciate any feedback or bug reports. Note also, that the hooks API changed, so it's quite likely that many non-trivial Setup.[l]hs files will break. We hope, however, that much of those files' functionality can now be expressed using configurations. This version (or a bug fix update) will be included in GHC version 6.8.1. For other Haskell implementations or older versions of GHC you can install it separately: Download: http://www.haskell.org/cabal/download.html http://haskell.org/cabal/release/rc/cabal-1.2.0.tar.gz Documentation: http://www.haskell.org/cabal/release/rc/doc/users-guide/ http://www.haskell.org/cabal/release/rc/doc/API/Cabal See both the README file and the changelog for interface changes: http://www.haskell.org/cabal/release/rc/changelog Bugs: Report bugs using our bug tracker: http://hackage.haskell.org/trac/hackage/newticket or at the libraries(a)haskell.org (please CC to cabal-devel(a)haskell.org) mailing list (note that this is subscriber only).

5 5

darcs patch: Link against GNUreadline.framework, if it's available.
by Judah Jacobson 06 Sep '07

06 Sep '07

I noticed that the HEAD readline package wasn't linking against the GNUreadline framework (as distributed for Mac OS X on the ghc-6.6.1 downloads page). The following patch fixes that. I've tested it on OS X (both with and without the framework), but someone should probably double-check that it works fine on non-Mac systems. Also note that for this to work correctly, it requires a bugfix that I just sent to cvs-ghc: http://permalink.gmane.org/gmane.comp.lang.haskell.cvs.ghc/23055 Thank, -Judah * Link against GNUreadline.framework, if it's available. This can be overridden by setting --with-readline-includes or --with-readline-libraries. M ./HsReadline_cbits.c -2 +1 M ./configure.ac -20 +39 M ./include/HsReadline.h -1 +7 M ./readline.buildinfo.in +1

3 2

Request for code review - Knuth Morris Pratt for Data.Sequence
by Justin Bailey 04 Sep '07

04 Sep '07

Using the code developed for ByteStrings by myself, Christ Kuklewicz and Daniel Fischer, I've implemented Knuth-Morris-Pratt substring searching on Data.Sequence "Seq" values. Attached you'll find the library in kmp.zip.safe. The algorithm is implemented in the module Data.Sequence.KMP. At the root, SpeedTest.hs can be compiled on Windows with the "prof_compile.bat" file included (you'll need to install the "regex-dfa" and "regex-base" packages from Hackage to build). SpeedTest searches for a known value in the 7 MB file "endo.dna" (which can be downloaded from http://www.icfpcontest.org/endo.zip) using several different algorithms and methods: strict and lazy bytestrings, regular expressions, and the KMP algorithm for "Seq" values. SpeedTest is pretty fast but I worry about its space usage. It may just be the nature of Seq values, but I cannot get it to run in constant space when I think it should be. I'm especially interested in help here. All comments and feedback are welcome. Since the zip file includes a darcs context file, feel free to send patches. Justin

1 0

Adding IdentityT to mtl
by dons＠cse.unsw.edu.au 04 Sep '07

04 Sep '07

I wanted an IdentityT today, for extending xmonad. (The idea is to allower user-defined monad transformers, so users can plug in their own semantics easily). By default it would use IdentityT, which I note is not in mtl! Here's roughly what it would be: ----------------------------------------------------------------------------- -- | -- Module : Identity.hs -- License : BSD3-style (see LICENSE) -- module IdentityT where import Control.Monad.Trans -- -- IdentityT , a parameterisable identity monad, with an inner monad -- The user's default monad transformer -- newtype IdentityT m a = IdentityT { runIdentityT :: m a } instance (Functor m, Monad m) => Functor (IdentityT m) where fmap f = IdentityT . fmap f . runIdentityT instance (Monad m) => Monad (IdentityT m) where return = IdentityT . return m >>= k = IdentityT $ runIdentityT . k =<< runIdentityT m fail msg = IdentityT $ fail msg instance (MonadIO m) => MonadIO (IdentityT m) where liftIO = IdentityT . liftIO Any reasons why this shouldn't be in mtl? -- Don

3 5

RFD: deprecate permissions-related stuff in System.Directory
by Simon Marlow 31 Aug '07

31 Aug '07

System.Directory has the following: Permissions( Permissions, readable, -- :: Permissions -> Bool writable, -- :: Permissions -> Bool executable, -- :: Permissions -> Bool searchable -- :: Permissions -> Bool ) getPermissions -- :: FilePath -> IO Permissions setPermissions -- :: FilePath -> Permissions -> IO () I propose to deprecate all this, in favour of using platform-specific functionality instead. Here's why: * Most uses of `getPermissions` are wrong. If you use `getPermissions` to predict whether a future operation will fail or not, then the right thing to do is to perform the operation and catch the failure exception. The result of `getPermissions` is immediately stale, and cannot be relied on alone. * The meaning of these operations on Windows is not clear. Windows has a much more elaborate access control model than Unix. For example, permissions can be inherited. Windows' emulation of the Unix `access()` function doesn't support the execute bit, and only has partial support for the other bits. * There doesn't seem to be a good least-common-denominator for access control, so we should provide good platform-specific support instead. (one problem here is that we don't have good platform-specific support for Windows, yet). These functions are hardly ever used. I did a Google code search for setPermissions and aside from implementations of setPermissions itself and tests for it, I came up with: * copying permissions from one file to another. This is used in the implementation of `copyFile`. We can and should do this natively. * one use in Wash * some uses in old versions of Cabal, when installing files (Cabal now uses `copyFile`). There are a few more uses of `getPermissions`, but as pointed out above, these are usually flawed. In any case they can usually be replaced by openFile. This isn't a proper proposal because I haven't written any code, but if we reach agreement in principle, I'll submit a real proposal. Cheers, Simon

4 8

Re: Data.HashTable.hashInt seems somewhat sub-optimal
by Jan-Willem Maessen 30 Aug '07

30 Aug '07

On Aug 30, 2007, at 9:56 AM, <Simon.Frankau(a)barclayscapital.com> wrote: > Jan-Willem Maessen wrote: >> Sigh. >> >> I've included a fix below, but I don't have a standard GHC checkout >> available to me (only the test sandbox I used to get the code in the >> first place) so I haven't generated a patch. Note the mentioned >> "reasonability tests", which hopefully should forestall such obvious >> infelicities in future. > > Hi. > > Sorry to be a bit negative, but I don't think the hash function you > suggest is good for a number of reasons: > > 1) I don't think you're implementing the algorithm Thorkil Naur > suggests. I believe (although I haven't had the time to check) that > the > scheme is equivalent to using the output of mulLo, not mulHi. So, we > lose whatever theoretical underpinnings the original has. Thorkil's scheme (from Knuth) used the higher-order bits. As I noted in my previous email, we're using the low-order bits to index the hash table. This was forced on me by legacy hash functions. A compromise position here (mentioned in my last mail) might be to post-multiply any incoming hash, and then pick off the high-order bits. This penalizes programmers who take the time to write a decent hash function for their data type. > 2) Signed multiplication is being used. I think unsigned > multiplication > is probably necessary to get the intended behaviour. For example, with > unsigned multiplication, multiplying by the original 'golden' and > taking > the the top 32 bits is equivalent to multiplying by the golden ratio, > while with signed multiplication it is equivalent to multiplying by > the > golden ratio minus one. Actually, I've simply used the bits directly. Signed twos-complement multiplication is the same as unsigned twos-complement multiplication (with all the unintuitive overflow behavior that entails). viz: > Numeric.showHex ((0x80000001 :: Int32) * 2) "" "2" > Numeric.showHex ((0xa0000000 :: Int32) * 2) "" "40000000" > 3) The original code was equivalent to a multiplication by a fixed > point > number less than one. Yes, and the low order bits of the hash are computed based only on the low order bits of the input data. > The new code is equivalent to multiplying by a > fixed point number slightly greater than one. I think this misses an > important behaviour which hash functions should have: They should > smear > out ranges of integers. Let's keep the intended application in mind: we're going to be taking low-order bits from the hashed data. We only need enough smearing to guarantee that this happens. That said, I'll quickly agree that we'd like more smearing than that if we can get it. > Why? People tend to hash lists with a fold > which, for example, hashes the previous result, and then xors in or > adds > the new value. This is in general a rotten way to hash a list of things, which is why presentations of hashing don't use it for hashing strings. Interestingly Knuth does not cover this topic in detail and mentions the use of addition or xor offhandedly. > If the hashes of small integers are small integers, we > have the situation where transposing two elements of a list of small > integers, and making a minor adjustment to one of those values will > result in a clash. In other words, we're not making effective use > of the > available range of numbers. Hence, for example, the use of 'magic' in > hashString. We effectively have a choice here: 1) Use a decent hash for individual elements, and combine them in a simple way (eg sum) 2) Use a decent method for combining elements I've tried to use (2). Indeed, if I were designing the library from scratch I'd include a function for combining hashes together. > I understand your concerns that > > A) The hash function should be cheap to evaluate, and need not be > particularly strong. > > However, It should not be unnecessarily weak. A decent hash should > allow > small sets of values (e.g. short lists of ints) to hash to unique > values. If they do not, scaling falls apart, since rehashing with > larger > table sizes will not necessarily shorten the longer hash chains. I > think > we can find a hash function with better behaviour which is still cheap > to evaluate. I think I've demonstrated that they do. (Actually, I tried an additional test last night in which I had testp draw only from ['a'..'z'], and that worked well too, especially with Ian's simplified function using + instead of xor.) Perhaps you disagree? But I'm happy to entertain suggestions of cheap hash functions. Recall that you can create a hash table with any hash function you like; testing better hash functions with Data.HashTable is really pretty easy and doesn't require the source code to the library at all! > B) If the low bits are zero, it would be nice if the low bits of the > hash weren't always zero. > > A scheme using mulLo doesn't have good behaviour here. Possible > variations which are quick to evaluate and have this property are: > * xor/add together the output of mulHi and mulLo This is worth a try, since we're (sort of) doing the work anyhow. [I say sort of because on many architectures mulHi and mulLo are independent instructions, though I believe on x86 one instruction does both.] > * Put a rotation step in. Rotation, of course, just moves the problem elsewhere. > The downside to these is that these 'adjustments' could well break > neat > behaviour seen in the theory. I'm afraid I don't have the time to test > these alternatives. > > So, I'm sorry I don't really have anything particularly > constructive to > say, but I thought it still worth mentioning what I think are > weaknesses > in the scheme. I agree that it's not without flaws (no cheap hash is, and the high- order zeros are definitely a concern). But I'll reiterate that I believe it's pretty good *for the intended application* while agreeing that *something better probably exists.* -Jan > > Thanks, > Simon Frankau. > >> On Aug 26, 2007, at 1:42 PM, Thorkil Naur wrote: >> >>> Hello, >> [snip] >>> In the 2nd edition of Knuth's The Art of Computer Programming, Vol >>> 3, Sorting >>> and Searching there is a discussion of hash functions on pp. >>> 514-520. One of >>> the techniques suggested for hashing a one-word (i.e. essentially >>> fixed-size) >>> key is the following multiplicative scheme: >>> >>> h(K) = floor ( M*(((A/w)*K)) mod 1) ) >>> >>> where w is the word-size (say, 2^32), M is the desired limit of the >>> hash >>> function (for efficiency, probably a suitable power of 2) and, >>> finally, A is >>> some integer constant. What happens here is that we consider the >>> (word) K as >>> a fraction with the binary point at the left end of the word rather > >>> than at >>> the right, thus getting a fraction with a value between 0 and 1. >>> This value >>> we then multiply by A and cut off the integer part, once again >>> getting a >>> fractional value between 0 and 1. And finally, we multiply by M and > >>> cut away >>> the fractional part to get an integer value between 0 and M-1. And, > >>> sure, >>> Knuth suggests various variants of selecting the multiplier A >>> related to the >>> golden ratio (sqrt(5)-1)/2 = 0.6180... to gain suitable spreading >>> of hashes >>> for keys in arithmetic progressions. (K, K+d, K+2d, ...). >> >> In the fix below I ended up using twice the golden ratio (a value of >> A greater than one). The inverse of the golden ratio (which is 1 + >> golden) didn't work well at all. >> >>> But what we are dealing with in the hashString function is what >>> Knuth would >>> call a multiword or variable-length key. Such cases, Knuth >>> suggests, "can be >>> handled by multiple-precision extensions of [e.g. the >>> multiplicative scheme] >>> above, but it is generally adequate to speed things up by combining > >>> the >>> individual words together into a single word, then doing a single >>> multiplication ... as above." >> >> But combining things into a single word requires having a good >> combining mechanism, which is hard in general---particularly with a >> type like Char that appears to have a large range but in practice >> only has a very small one. >> >>> Neither of the above definitions of f implement a multiple- >>> precision extension >>> of the multiplicative hashing scheme that involves the golden > ration. >> >> [snip] >> I actually did do a bakeoff between multiple hashing schemes, and >> have a version of Data.HashTable that requires separate import of a >> hashing technique. The multiplicative hash worked better in the >> bakeoff than either the modulus hash used in older versions of the >> library, or a couple of versions of the Bob Jenkins hash. >> >> Could I convince someone with a checked out repository to cut and >> paste this into Data.HashTable and generate a patch / check it in? >> >> Thanks, >> >> -Jan >> >> >> Here's the fix: >> >> >> -- >> > ---------------------------------------------------------------------- > -- > >> ----- >> -- Sample hash functions >> >> -- $hash_functions >> -- >> -- This implementation of hash tables uses the low-order /n/ bits >> of >> the hash >> -- value for a key, where /n/ varies as the hash table grows. A good > >> hash >> -- function therefore will give an even distribution regardless of > /n/. >> -- >> -- If your keyspace is integrals such that the low-order bits between >> -- keys are highly variable, then you could get away with using >> 'fromIntegral' >> -- as the hash function. >> -- >> -- We provide some sample hash functions for 'Int' and 'String' >> below. >> >> golden :: Int32 >> golden = 1013904242 -- = round ((sqrt 5 - 1) * 2^32) :: Int32 >> -- was -1640531527 = round ((sqrt 5 - 1) * 2^31) :: Int32 >> -- but that has bad mulHi properties (even adding 2^32 to get its >> inverse) >> -- Whereas the above works well and contains no hash duplications for >> -- [-32767..65536] >> >> hashInt32 :: Int32 -> Int32 >> hashInt32 x = mulHi x golden + x >> >> -- | A sample (and useful) hash function for Int and Int32, >> -- implemented by extracting the uppermost 32 bits of the 64-bit >> -- result of multiplying by a 33-bit constant. The constant is from >> -- Knuth, derived from the golden ratio: >> -- > golden = round ((sqrt 5 - 1) * 2^32) >> -- We get good key uniqueness on small inputs >> -- (a problem with previous versions): >> -- (length $ group $ sort $ map hashInt [-32767..65536]) == 65536 >> + >> 32768 >> -- >> hashInt :: Int -> Int32 >> hashInt x = hashInt32 (fromIntegral x) >> >> -- hi 32 bits of a x-bit * 32 bit -> 64-bit multiply >> mulHi :: Int32 -> Int32 -> Int32 >> mulHi a b = fromIntegral (r `shiftR` 32) >> where r :: Int64 >> r = fromIntegral a * fromIntegral b >> >> -- | A sample hash function for Strings. We keep multiplying by the >> -- golden ratio and adding. The implementation is: >> -- >> -- > hashString = foldl' f golden >> -- > where f m c = fromIntegral (fromEnum c) * magic + hashInt32 m >> -- > magic = 0xdeadbeef >> -- >> -- Where hashInt32 works just as hashInt shown above. >> -- >> -- Knuth argues that repeated multiplication by the golden ratio >> -- will minimize gaps in the hash space, and thus it's a good choice >> -- for combining together multiple keys to form one. >> -- >> -- Here we know that individual characters c are often small, and >> this >> -- produces frequent collisions if we use fromEnum c alone. A >> -- particular problem are the shorter low ASCII and ISO-8859-1 >> -- character strings. We pre-multiply by a magic twiddle factor to >> -- obtain a good distribution. In fact, given the following test: >> -- >> -- > testp :: Int32 -> Int >> -- > testp k = (n - ) . length . group . sort . map hs . take n $ ls >> -- > where ls = [] : [c : l | l <- ls, c <- ['\0'..'\xff']] >> -- > hs = foldl' f golden >> -- > f m c = fromIntegral (fromEnum c) * k + hashInt32 m >> -- > n = 100000 >> -- >> -- We discover that testp magic = 0. >> >> hashString :: String -> Int32 >> hashString = foldl' f golden >> where f m c = fromIntegral (fromEnum c) * magic + hashInt32 m >> magic = 0xdeadbeef > ---------------------------------------------------------------------- > -- > For important statutory and regulatory disclosures and more > information about Barclays Capital, please visit our web site at > http://www.barcap.com. > > Internet communications are not secure and therefore the Barclays > Group does not accept legal responsibility for the contents of this > message. Although the Barclays Group operates anti-virus > programmes, it does not accept responsibility for any damage > whatsoever that is caused by viruses being passed. Any views or > opinions presented are solely those of the author and do not > necessarily represent those of the Barclays Group. Replies to this > email may be monitored by the Barclays Group for operational or > business reasons. > > Barclays Capital is the investment banking division of Barclays > Bank PLC, a company registered in England (number 1026167) with its > registered office at 1 Churchill Place, London, E14 5HP. This email > may relate to or be sent from other members of the Barclays Group. > ---------------------------------------------------------------------- > --

1 0

Re: Data.HashTable.hashInt seems somewhat sub-optimal
by Ian Lynagh 30 Aug '07

30 Aug '07

On Thu, Aug 16, 2007 at 05:06:53PM +0100, Simon.Frankau(a)barclayscapital.com wrote: > I tried submitting this bug through the tracker, but it seemed to give > me permissions errors - probably a firewall issue here. Due to spammers you need to log in to the bug tracker (user guest, password guest), so that's another possibility. > Prelude> Data.HashTable.hashInt 0 > 0 > Prelude> Data.HashTable.hashInt 1 > -1 > Prelude> Data.HashTable.hashInt 2 > -1 > Prelude> Data.HashTable.hashInt 3 > -2 > Prelude> Data.HashTable.hashInt 4 > -2 > Prelude> Data.HashTable.hashInt 5 > -2 > Prelude> Data.HashTable.hashInt 6 > -3 > Prelude> Data.HashTable.hashInt 7 > -3 > Prelude> Data.HashTable.hashInt 8 > -4 > Prelude> Data.HashTable.hashInt 9 > -4 > Prelude> Data.HashTable.hashInt 10 > -4 > Prelude> Data.HashTable.hashInt 200 > -77 > Prelude> Data.HashTable.hashInt 201 > -77 > Prelude> Data.HashTable.hashInt 202 > -78 > > I prefer to use hashing to decrease the likelihood of collisions, not > increase them. ;) > > I think the original algorithm was quite possibly supposed to use the > bottom 32 bits of the result, Based on http://www.brpreiss.com/books/opus4/html/page213.html http://www.brpreiss.com/books/opus4/html/page214.html it looks like you're right. I'll change it from hashInt :: Int -> Int32 hashInt x = mulHi (fromIntegral x) golden to hashInt :: Int -> Int32 hashInt x = fromIntegral x * golden which gives better results: Prelude> Data.HashTable.hashInt 0 0 Prelude> Data.HashTable.hashInt 1 -1640531527 Prelude> Data.HashTable.hashInt 2 1013904242 Prelude> Data.HashTable.hashInt 3 -626627285 Prelude> Data.HashTable.hashInt 4 2027808484 Prelude> Data.HashTable.hashInt 5 387276957 Prelude> Data.HashTable.hashInt 6 -1253254570 I'm also suspicious of this, though: -- | A sample hash function for Strings. We keep multiplying by the -- golden ratio and adding. -- -- Note that this has not been extensively tested for reasonability, -- but Knuth argues that repeated multiplication by the golden ratio -- will minimize gaps in the hash space. hashString :: String -> Int32 hashString = foldl' f 0 where f m c = fromIntegral (ord c + 1) * golden + mulHi m golden should this be where f m c = (fromIntegral (ord c + 1) + m) * golden ? Does Knuth (TAOCP?) say? Thanks Ian

4 9

Data.List.groupBy with non-transitive equality predicate
by Henning Thielemann 30 Aug '07

30 Aug '07

I was used to use groupBy to split a list before every element that satisfies a predicate. E.g. splitting before every capital Prelude> groupBy (\_ c -> not $ Char.isUpper c) "Hello World" ["Hello ","World"] I also wanted to use this for splitting after specific elements. But this fails. I get Prelude> groupBy (\c _ -> c /= ',') "1, 2, 3, 4" ["1, 2, 3, 4"] but I wanted ["1,", " 2,", " 3,", " 4"] I assumed that 'groupBy' would compare adjacent elements, but it seems to compare the leading element of each block with subsequent elements. Since the documentation doesn't tell which elements are actually compared it seems to assume that the comparison is commutative and transitive. Maybe this point should be made clearer. Additionally I think that comparing neighbouring elements is a useful behaviour and I suggest an according variant of 'groupBy' for Data.List. Opinions?

5 5

darcs patch: added a bit of documentation to the readline library
by ijones＠syntaxpolice.org 25 Aug '07

25 Aug '07

Sun Aug 19 01:31:06 PDT 2007 ijones(a)syntaxpolice.org * added a bit of documentation to the readline library

2 1

darcs patch: add cross-referencing between posix and process modules
by ijones＠syntaxpolice.org 25 Aug '07

25 Aug '07

Sun Aug 19 00:39:30 PDT 2007 ijones(a)syntaxpolice.org * add cross-referencing between posix and process modules

2 1