[Haskell-cafe] Re: String Hashing

[Thomas Conway]

On 6/19/07, apfelmus <apfelmus at quantentunnel.de> wrote:
>  Trie it is,
>  not balanced tree.
>  A logarithm in this
>  would be new to me. :)

True enough, my braino.

> As a side node, Mr. Exp says: 64 is large enough for the size needs of
> any logarithm.

Que?

> > type HashTable k v = TVar (Array Int (TVar [(k,v)]))
>
> Don't you want a TArray Int [(k,v)]?

Essentially the same.

> In any case, you could be able to set up an infinite trie and have lazy
> evaluation allocate space as needed:
>
>  type Trie a = Branch (TVar a) (Trie a) (Trie a)

Tree-like structure's are quite hostile to highly concurrent manipulation.

It helps to introduce TVar indirections at each level:

data Trie a = Branch (TVar a) (TVar (Trie a)) (TVar (Trie a))

Then you can update a subtree without having to modify the spine of the tree.

There is some very fine work on this by Kim Larsen (and others), see
for example http://citeseer.ist.psu.edu/2986.html

T.
-- 
Dr Thomas Conway
drtomc at gmail.com

Silence is the perfectest herald of joy:
I were but little happy, if I could say how much.