[Haskell-cafe] Pure hashtable library

[Richard A. O'Keefe]

On 28 Aug 2008, at 9:07 pm, Jules Bean wrote:
> Insert for Data.Sequence is log(i) where i is the position of the  
> insertion; clearly bounded by log(n). toList is O(n) and index is  
> (at worst) log(i).
>
> I think the corresponding operations with tries are log(n),

Let the key you want to insert have length L.
Then insertion into a trie is O(L), independent of the size of the  
collection.
If the "alphabet" the key's elements are drawn from is large,
you can use a Ternary Search Tree, and insertion is
then O(L.lg B) where B is the branching factor.
There are fast Trie construction algorithms which are linear
in the total size of the collection, \sum_{i=1}^{n}L_i.

The worst case for Data.Sequence is where keys mostly vary at
the end, in which case comparisons take O(L) time, and the
cost is O(L.lg n), where n is usually much bigger than B.

> So, it's all in the constants, isn't it?

No.