Re: Re[2]: [Haskell-cafe] Pure hashtable library
On Aug 27, 2008, at 4:31 PM, Bulat Ziganshin wrote: Hello Jan-Willem, Wednesday, August 27, 2008, 4:06:11 PM, you wrote: One obvious way to make non-modifiable hash tables useful is to eat your own tail non-strictly--- aggregate a set of hash table entries, construct a hash table from them, and plumb the resulting hash table into the original computation by tying the knot. This works really well if you can construct the bucket lists lazily and if you specify the table size up front. i think it's impossible since you need to scan whole assoclist to build list of entries for any value of hash function. I think this is because I wasn't quite clear enough about the problem I was solving. I think you'll agree that we can use an assocList non- strictly in the following sense: * We can do lookups that succeed so long as we can compute all keys up to and including the key that matches. * We never do non-strict lookups that fail, as that would require examining the entire assocList. Now I can build a hashtable with the same property from an assocList, albeit very inefficiently, using code like this (untested): lazyArray :: (Ix i) = (i,i) - [(i,v)] - Array i [v] lazyArray bnds kvs = array bnds [ (k, map snd . filter ((k==) . fst) $ kvs) | k - range bnds ] makeHash :: (Eq k, Hashable k) = [(k,v)] - Array Int [(k,v)] makeHash assocList = lazyArray (0,n-1) labeledAssocList where labeledAssocList = [ (hashToSize n k, (k,v)) | (k,v) - assocList ] We label each assocList element with its corresponding hash bucket (labeledAssocList); each bucket then contains exactly the elements of assocList that map to that bucket, in exactly the order in which they occurred in assocList. The LazyArray library in hbc essentially did exactly what the lazyArray function I've shown above does, only the input list is traversed once rather than having a separate traversal for each bucket. This can actually be implemented using the ST monad augmented by unsafeFreezeSTArray and unsafeInterleaveST; indeed the State in Haskell paper by Peyton Jones and Launchbury gives the implementation of a very similar function. I have code for LazyArray based on the above paper that works with GHC, but I haven't needed it in a while. -Jan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Pure hashtable library
On 27 Aug 2008, at 10:09, Bulat Ziganshin wrote: Hello Jason, Wednesday, August 27, 2008, 11:55:31 AM, you wrote: given these constraints, it should be just a 10-20 lines of code, and provide much better efficiency than any tree/trie implementations Much better efficiency in what way? instead of going through many levels of tree/trie, lookup function will just select array element by hash value and look through a few elements in assoc list: data HT a b = HT (a-Int) -- hash function (Array Int [(a,b)]) HT.lookup (HT hash arr) a = List.lookup (arr!hash a) a Which makes two assumptions. One is that your array is big enough (believable), and the other, that your font is big enough. Bob ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: Re[2]: [Haskell-cafe] Pure hashtable library
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Thomas Davie Much better efficiency in what way? instead of going through many levels of tree/trie, lookup function will just select array element by hash value and look through a few elements in assoc list: data HT a b = HT (a-Int) -- hash function (Array Int [(a,b)]) HT.lookup (HT hash arr) a = List.lookup (arr!hash a) a Which makes two assumptions. One is that your array is big enough (believable), and the other, that your font is big enough. ... and the other, that your font is big enough. Que? This is lost on me. Care to explain? Alistair * Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. * ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Pure hashtable library
On 27 Aug 2008, at 10:39, Bayley, Alistair wrote: From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Thomas Davie Much better efficiency in what way? instead of going through many levels of tree/trie, lookup function will just select array element by hash value and look through a few elements in assoc list: data HT a b = HT (a-Int) -- hash function (Array Int [(a,b)]) HT.lookup (HT hash arr) a = List.lookup (arr!hash a) a Which makes two assumptions. One is that your array is big enough (believable), and the other, that your font is big enough. ... and the other, that your font is big enough. Que? This is lost on me. Care to explain? Sorry, I probably should have sent that, it was a dig at the fact that the message was sent with all the text in font-size 930 or so. Bob ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
