Jules Bean <[EMAIL PROTECTED]> wrote: > 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.
If by a wrapper you mean a function, well that's not type level at all. A binary search that insists on tries will, with a correct trie implementation, behave correctly on every input; a binary search that works with `Data.Sequence` will fail on a substantial portion of the inputs accepted by the type system, regardless of the data structure's correctness. -- _jsn _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
