Jason Dusek wrote: > Jules Bean <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
