On 6/19/07, apfelmus
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@gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.