[Haskell-cafe] Pure hashtable library
jules at jellybean.co.uk
Thu Aug 28 15:55:36 EDT 2008
Jason Dusek wrote:
> 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,
>>>> 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.
More information about the Haskell-Cafe