Thanks Bulat. FWIW, i take it that
http://www.haskell.org/haskellwiki/Shootout/Knucleotide is what Edward was referring to, with the shootouts. It seems that a lot of progress has been made but not much has been migrated back to hackage. Going back to my original question, I am now looking for a dead simple motivating example for showing the example of using a (good) hashtable over Data.Map, with a tangible demo of O(n) over O(n log n) running times. I mean, something where running an input of (10^4) size versus (10^6) size shows a noticeably laggier run when using Set versus hashtable. I don't think maybe my original example quite qualifies because I think in practice the computation is dominated by space complexity. However, I haven't yet ported it over to a hashtable version, so not sure. (And the shootout example doesn't satisfy my sense of "dead simple.") 2009/7/18 Bulat Ziganshin <bulat.zigans...@gmail.com>: > Hello Thomas, > > Saturday, July 18, 2009, 2:24:21 AM, you wrote: > >> Further, is there a hashtable implementation for haskell that doesn't >> live in IO? Maybe in ST or something? > > import Prelude hiding (lookup) > import qualified Data.HashTable > import Data.Array > import qualified Data.List as List > > > data HT a b = HT (a->Int) (Array Int [(a,b)]) > > -- size is the size of array (we implement a closed hash) > -- hash is the hash function (a->Int) > -- list is assoclist of items to put in hash > create size hash list = HT hashfunc > (accumArray (flip (:)) > [] > (0, arrsize-1) > (map (\(a,b) -> (hashfunc a,(a,b))) > list) > ) > > where arrsize = head$ filter (>size)$ iterate (\x->3*x+1) 1 > hashfunc a = hash a `mod` arrsize > > > lookup a (HT hash arr) = List.lookup a (arr!hash a) > > > main = do let assoclist = [("one", 1), ("two", 2), ("three", 3)] > hash = create 10 (fromEnum . Data.HashTable.hashString) assoclist > print (lookup "one" hash) > print (lookup "zero" hash) > > > -- > Best regards, > Bulat mailto:bulat.zigans...@gmail.com > > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe