Jason Dusek wrote:
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.
No. I meant a newtype with a non-exported constructor and exporting only
methods which preserve sortedness.
Jules
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
