On 6/19/07, apfelmus <[EMAIL PROTECTED]> 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 [EMAIL PROTECTED] Silence is the perfectest herald of joy: I were but little happy, if I could say how much. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
