Am Montag 22 Juni 2009 21:31:50 schrieb Kamil Dworakowski: > On Jun 22, 6:46 am, Bulat Ziganshin <bulat.zigans...@gmail.com> wrote: > > Hello Kamil, > > > > Monday, June 22, 2009, 12:01:40 AM, you wrote: > > > Right... Python uses hashtables while here I have a tree with log n > > > > you can try this pure hashtable approach: > > > > 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 implent 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,b))
Typo: should be 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) > > It does not compile: > > No instance for (Num (String, b)) > arising from the literal `3' at foo.hs:23:61 > Possible fix: add an instance declaration for (Num (String, b)) > In the expression: 3 > In the expression: ("three", 3) > In the expression: [("one", 1), ("two", 2), ("three", 3)] > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe