[Haskell-cafe] Re: String Hashing

Thomas Conway wrote:

On 6/19/07, apfelmus wrote:

...

Trie it is, not balanced tree. A logarithm in this would be new to me. :)

True enough, my braino.

So, accessing a key in a trie is O(key size in bits), not much different from a hash table.

...

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

Que?

A pun(y) formulation of the fact that (log n <= 64) for (almost) any finite map situation you'll ever encounter because 2^64 = 16 Exabyte.

...

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.

What I wanted to point out is that the spine simply doesn't need to be modified at all. In other words, you have an infinite tree residing in memory and insertion/deletion happens by updating the TVars that hold the values (and probably should be of type TVar (Maybe a) then). Of course, there can't be infinite trees in memory :) but lazy evaluation makes it appear as if. In fact, every branch will be modified at most once before the first read and subsequent accesses are read-only. I don't know whether or how this is implemented in concurrent GHC at the moment, but I think that this can safely be implemented with a lock whereas dead-lock means that the program denotes _|_ anyway. Regard, apfelmus