Re: [Haskell-cafe] Pure hashtable library

Jason Dusek wrote:

Jules Bean 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

Jason Dusek wrote: 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