Re: [Haskell-cafe] Pure hashtable library

Jason Dusek wrote:

Jules Bean wrote:

...

...

Jules Bean 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

Jason Dusek wrote: 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