September 2004 - Libraries

Network.CGI, POST and QUERY_STRING
by Philippa Cowderoy 04 Oct '04

04 Oct '04

Would it be possible to expose urlDecode from Network.CGI, or to automatically parse the query string in response to a POST rather than just parsing the data on stdin? -- flippa(a)flippac.org

3 5

RE: Data.HashTable and duplicate keys
by Simon Marlow 28 Sep '04

28 Sep '04

On 28 September 2004 12:49, George Russell wrote: > Einar wrote (snipped): > > I recently noticed that Data.HashTable silently > > accepts duplicate keys and keeps all the values. > > This is very counterintuitive from the interface > > and makes updating a hashtable quite tedious > > (lookup + delete + insert). > > Gosh, I'm glad *someone* told me of this bizarre behaviour. > Why on earth hash tables should mimic association lists of > all things is a mystery to me. (Should GHC also insert > delay loops to simulate their poor performance?) > > Sigh, off I go to fix my code. Just as well I only use > hash tables in one place. Making insert do delete+insert is pretty inefficient if you know that the key isn't in the table. Providing update (==delete+insert) seems a reasonable solution, no? Cheers, Simon

4 3

RE: Data.HashTable and duplicate keys
by Simon Marlow 28 Sep '04

28 Sep '04

On 28 September 2004 13:37, Marcin 'Qrczak' Kowalczyk wrote: > "Simon Marlow" <simonmar(a)microsoft.com> writes: > >> Making insert do delete+insert is pretty inefficient if you know that >> the key isn't in the table. Providing update (==delete+insert) >> seems a reasonable solution, no? > > This depends whether the implementation uses buckets for elements with > the same hash modulo size (like in OCaml), or stores elements directly > in the array, with some conflict resolution strategy (like in Python). > > I don't know which scheme is more efficient in general. Buckets are > easier to implement if deletion is to be supported, but a flat array > may have a faster optimistic case. Their memory overhead is similar > because a flat array can't be as dense as an array of buckets. The implementation uses buckets. I think buckets are also easier if the hash tables are variable in size (which ours are). I've now added update :: HashTable key val -> key -> val -> IO Bool to the interface, and improved the documentation. Cheers, Simon

1 0

Re: Data.HashTable and duplicate keys
by George Russell 28 Sep '04

28 Sep '04

Einar wrote (snipped): > I recently noticed that Data.HashTable silently > accepts duplicate keys and keeps all the values. > This is very counterintuitive from the interface > and makes updating a hashtable quite tedious > (lookup + delete + insert). Gosh, I'm glad *someone* told me of this bizarre behaviour. Why on earth hash tables should mimic association lists of all things is a mystery to me. (Should GHC also insert delay loops to simulate their poor performance?) Sigh, off I go to fix my code. Just as well I only use hash tables in one place.

1 0

RE: Data.HashTable and duplicate keys
by Simon Marlow 28 Sep '04

28 Sep '04

On 28 September 2004 05:43, Ben Rudiak-Gould wrote: > On Mon, 27 Sep 2004, Einar Karttunen wrote: > >> I recently noticed that Data.HashTable silently >> accepts duplicate keys and keeps all the values. >> This is very counterintuitive from the interface >> and makes updating a hashtable quite tedious >> (lookup + delete + insert). > > OCaml's Hashtbl also works this way. It makes sense if you think of a > hash table as a speedier drop-in replacement for an association list: > Data.HashTable.insert behaves like consing a new (key,val) pair onto > the front of an association list, and Data.HashTable.delete and > Data.HashTable.lookup behave like the corresponding list functions. I > agree 100% that it should be documented, of course. > > However, playing around with HashTable just now, I noticed the > following (GHCi): > > Prelude> hash <- Data.HashTable.fromList id [(1,'a'),(1,'b')] > Prelude> Data.HashTable.lookup hash 1 >>= print > Just 'b' > > This is clearly wrong, and makes me think that Data.HashTable's > behavior given identical keys wasn't well thought out. I'm in favor > of plagiarizing OCaml's Hashtbl interface, which has the update > function (called replace) as well as other useful operations like > copy and find_all. By all means go ahead and fix this, I won't have time to look into it in the short term. Cheers, Simon

2 1

Data.HashTable and duplicate keys
by Einar Karttunen 28 Sep '04

28 Sep '04

Hello I recently noticed that Data.HashTable silently accepts duplicate keys and keeps all the values. This is very counterintuitive from the interface and makes updating a hashtable quite tedious (lookup + delete + insert). Mentioning the feature in the documentation and providing an update function would be very nice. e.g. update :: HashTable k v -> k -> (v -> v) -> IO Bool or update :: HashTable k v -> k -> (v -> (v, w)) -> IO (Maybe w) with the result marking whether the key was present in the hashtable. On the other hand, if it is a bug I hope it will be solved quickly. The behaviour can be demonstrated with main = do ht <- new (==) hashInt insert ht 1 1 insert ht 1 2 toList ht >>= print - Einar Karttunen

2 1

new HsDNS version available
by Peter Simons 26 Sep '04

26 Sep '04

In case anyone is using my Haskell bindings to the GNU ADNS library, you might be interested to know that a new version of the package is available here: http://cryp.to/hsdns/ There have been quite a few significant improvements recently, most of which concern exception-safety, efficiency, and documentation. PollResolver.hs, in particular, has been cleaned up a lot. Peter

1 0

Benchmarking (again:-)
by Adrian Hey 11 Sep '04

11 Sep '04

Hello, I enclose a copy of some results I posted in a c.l.f thread FYI.. > Adrian Hey wrote: > >> It would be nice to have some data for other tree types too, like >> red-black trees maybe. > > Malcolm Wallace sent me some code for red-black and 234 trees which is > used in nhc98 compiler. It contains no set operations, or even delete, but > I thought it would be interesting to see how these compared with my own > AVL implementation and DData.Set (weight balanced) for simple insert, > lookup (and delete if available). > > So here are my results for trees of 500000 Int elements (execution times > and comparison counts) for ordered data and random data. > > Ordered Data (times in mS) > AVL DData.Set RedBlack 234 > ------------------------------------------- > Insert 150 366 217 255 > Lookup 53 76 116 114 > Delete 126 135 --- --- > > Ordered Data (Comparisons) > AVL DData.Set RedBlack 234 > ---------------------------------------------- > Insert 8975713 15689425 12668235 13167977 > Lookup 8975732 9166555 9132570 9132601 > Delete 6785282 6612512 --- --- > > Random Data (times in mS) > AVL DData.Set RedBlack 234 > ------------------------------------------- > Insert 763 1003 815 852 > Lookup 153 181 224 215 > Delete 803 ??? --- --- > > Random Data (Comparisons) > AVL DData.Set RedBlack 234 > ---------------------------------------------- > Insert 8953286 9155823 9104153 9106882 > Lookup 9184653 9418309 9331310 9332922 > Delete 8229843 8405601 --- --- > > Notes: > * These figures are for the entire test (not per element). > The timing measurements are averaged over 10 runs (same > test data each run). > * The Insert test constructs a tree by inserting a list of > Ints into an empty tree. > * The Lookup test checks each Int in the original list is > a member of the set (in the same order that they appear > in the list). > * The Delete test deletes each element from the set > successively, resulting in an empty set (in the order > they appear in the original list). > * There are no results for deletion from RedBlack or 234 > trees (because these functions don't exist :-) > * There is no timing result for deletion of random data from > DData.Set because the test segfaults???. But only with > random data and only when I try to time it, not with ordered > data and not if I just count comparisons. Ermm.. > > The actual execution times may be suspect (a lot will depend on > implementation details, so they don't necessarily reflect on the > algorithm). > > But the comparison counts tell us something. DData.Set, RedBlack, and > 234 all seem to be struggling with insertion of ordered data, but for AVL > it makes virtually no difference. I think my earlier remark about the > AVL algorithm being difficult to improve on is justified by these results. > > So I still say AVL is a darned good algorithm that takes a lot of beating > in practice. But I'd still be interested in being proven wrong :-) Regards -- Adrian Hey

1 0