[Haskell-cafe] Pure hashtable library
Jules Bean
jules at jellybean.co.uk
Thu Aug 28 05:07:44 EDT 2008
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
More information about the Haskell-Cafe
mailing list