[Haskell-cafe] Pure hashtable library

[Jules Bean]

Jason Dusek wrote:
 > Jules Bean <jules at jellybean.co.uk> wrote:
 >> Jason Dusek wrote:
 >>> I would much rather have a pure Trie that is foldable. If we
 >>> have a Trie, we get a space efficient sorted list, too.
 >> Well, Data.Sequence can be used as a space efficient sorted
 >> list which is Foldable - if you make the decision to insert
 >> elements into it in a sorted way, obviously.
 >>
 >> What advantages would a Trie have over Data.Sequence?
 >
 >   A trie is guaranteed sorted -- so using a trie amounts to a
 >   "type level" guarantee for binary search and any other
 >   algorithm that relies on sortedness.

...No more so than a simple wrapper over a Data.Sequence which puts the 
elements in the right place.

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), so 
asymptotically tries are identical for 'uniformly distributed' keys 
although fingertrees are faster if there is a bias towards elements near 
the ends of the lists.

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

Jules