[Haskell-cafe] Pure hashtable library

[Jason Dusek]

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.

--
_jsn