[Haskell-cafe] Pure hashtable library
jason.dusek at gmail.com
Thu Aug 28 13:18:04 EDT 2008
Jules Bean <jules at jellybean.co.uk> wrote:
> 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.
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.
More information about the Haskell-Cafe