Bulat Ziganshin wrote:
Hello haskell-cafe,
solving one more task that uses English dictionary, i've thought: why we don't
yet have pure hashtable library? There is imperative hashtables, pretty complex
as they need to rebuild entire table as it grows. There is also simple assoc
lists and tree/trie implementations, but there is no simple non-modifiable
hashes.
how should it look:
* hashtable is represented as an array of assoc lists: Array Int [(a,b)]
* interface to extract data from ht is the same as from assoc list:
lookup :: HT a b -> a -> Maybe b
* ht may be built from assoc list. we should just know it's size beforehand in
order to create Array of reasonable size. constructor also need a hashing
function:
create :: [(a,b)] -> Int -> (a->Int) -> HT a b
given these constraints, it should be just a 10-20 lines of code, and provide
much better efficiency than any tree/trie implementations
Prove it.
To get "much better efficient" than a trie, the hash function has to be
so fast that it is faster than following (log n) pointers, and yet also
so "perfect" that it doesn't generate too many collisions.
As you correctly say, a simple implementation is easy to do, so why not
do it and see how it performs? :)
Jules
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
