August 2007 - Libraries

There are too many error handling conventions used in library code!
by dons＠cse.unsw.edu.au 13 Aug '11

13 Aug '11

This article on the 8 different error handling strategies various common Haskell libs use: http://www.randomhacks.net/articles/2007/03/10/haskell-8-ways-to-report-err… got me thinking: we need to standardise/recommend a small set of methods for library error handling. The lack of consistent error reporting between libs results in verbose code, as we're not able to use a single error handling technique when gluing together code from different libs (i.e. we can't just use Maybe or Either/ErrorT). (It's always nice when you *can* use, say, a Maybe monad to glue code from a number of sources, but eventually you reach code with a different error system, and the Maybe monad breaks down). So, some questions I think we can tackle: * can we identify error handling strategies from the list that should not be used anymore? (throwDyn?) * can we move some of the outlying libraries to a more consistent error framework? * do we need more support for gluing together our different error systems? (it should be easier to glue code using , say, Maybe/Either). * what role does MonadError play here, as a generic error handler? * can we make precise recommendations about which error strategies to use? -- Don

11 16

Data.Map, Data.IntMap documentation
by Andriy Palamarchuk 19 Mar '08

19 Mar '08

Improved, fixed documentation for Data.Map, Data.IntMap. Moved time complexity Big-O values to the end of function descriptions. Added examples. For the initial review I submitted only changes for Data.Map. I'll update IntMap for the final review. Deadline - August 27 (two weeks). Ticket: http://hackage.haskell.org/trac/ghc/ticket/1611 Haddock output: http://hackage.haskell.org/trac/ghc/attachment/ticket/1611/Data-Map.html?fo… The module source and diff are also attached to the ticket. Andriy ____________________________________________________________________________________ Pinpoint customers who are looking for what you sell. http://searchmarketing.yahoo.com/

17 50

Trac/1417 - add pseudoterminal support to the unix library
by Bryan O'Sullivan 18 Sep '07

18 Sep '07

This is a very simple enhancement. openPseudoTerminal :: IO (Fd, Fd) getSlaveTerminalName :: Fd -> IO FilePath Here's the ticket: http://hackage.haskell.org/trac/ghc/ticket/1417 The code ought to work on Linux, Solaris, BSD, HP/UX, and Cygwin, too. I've compile-tested it on Linux, using both openpty and explicit open of /dev/ptmx. I propose a discussion period of one week. Thanks, <b

1 1

Proposal: Test.HUnit documentation (#1632)
by Leif Frenzel 07 Sep '07

07 Sep '07

Hi everybody, I have recently written a tutorial for using HUnit and noticed that there was no Haddock library documentation yet, so I thought I might contribute some :-) As described on http://haskell.org/haskellwiki/Library_submissions I have created a trac ticket (#1632). Please let me know if anything else needs to be done to make this fit for the library :-) Thanks && ciao, Leif

2 3

ByteString I/O Performance
by Peter Simons 06 Sep '07

06 Sep '07

> import System.IO > import Foreign ( allocaBytes ) > import qualified Data.ByteString as Str > bufsize :: Int > bufsize = 4 * 1024 In order to determine I/O performance, a random 512 MB file is copied from standard input to standard output. All test programs have been compiled with GHC 6.6.1 using "-O2 -funbox-strict-fields" for optimization. The time to beat for this test comes from /bin/cat: $ dd if=/dev/urandom of=test.data bs=1M count=512 $ time /bin/cat <test.data >/dev/null real 0m2.097s 0m2.135s 0m2.100s user 0m0.036s 0m0.028s 0m0.024s sys 0m2.060s 0m2.108s 0m2.076s The first entry is implemented using static buffer I/O: > catBuf :: Handle -> Handle -> IO () > catBuf hIn hOut = allocaBytes bufsize input > where > input ptr = hGetBuf hIn ptr bufsize >>= output ptr > output _ 0 = return () > output ptr n = hPutBuf hOut ptr n >> input ptr real 0m2.747s 0m2.737s 0m2.758s user 0m0.524s 0m0.416s 0m0.632s sys 0m2.224s 0m2.304s 0m2.124s The second entry is implemented with ByteString: > catString :: Handle -> Handle -> IO () > catString hIn hOut = Str.hGet hIn bufsize >>= loop > where > loop buf | Str.null buf = return () > | otherwise = Str.hPut hOut buf >> catString hIn hOut real 0m7.852s 0m7.817s 0m7.887s user 0m4.764s 0m4.800s 0m4.748s sys 0m3.080s 0m3.000s 0m3.108s When Data.ByteString.Char8 is used instead, the program produces almost identical results. Data.ByteString.Lazy, however, came out differently: real 0m8.184s 0m8.086s 0m8.067s user 0m5.104s 0m5.252s 0m4.948s sys 0m2.940s 0m2.808s 0m3.120s ByteString turns out to be more than two times slower than ordinary buffer I/O. This result comes as a surprise because ByteString _is_ an ordinary memory buffer, so it feels reasonable to expected it to perform about the same. The reason why ByteString cannot compete with hGetBuf appears to be Data.ByteString.Base.createAndTrim. That function allocates space with malloc(), reads data into that buffer, allocates a new buffer, and then copies the data it has just read from the old buffer into the new one before returning it. This approach is quite inefficient for reading large amounts of data. It is particularly odd that Data.ByteString.readFile relies on the same mechanism. The required buffer size is known in advance. There is no point in reading data into a temporary buffer. I may have misread the implementation, but my impression is that readFile currently requires 2*n bytes of memory to read a file of size n. It feels like there is plenty of room for optimization. :-) > main :: IO () > main = do > mapM_ (\h -> hSetBuffering h NoBuffering) [ stdin, stdout ] > catString stdin stdout

13 32

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

03 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