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. It's a fingertree not a trie, of course. What advantages would a Trie have over Data.Sequence? Jules

Jason Dusek wrote:

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

Jason Dusek wrote: 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. Insert for Data.Sequence is log(i) where i is the position of the insertion; clearly bounded by log(n). toList is O(n) and index is (at worst) log(i). I think the corresponding operations with tries are log(n), so asymptotically tries are identical for 'uniformly distributed' keys although fingertrees are faster if there is a bias towards elements near the ends of the lists. So, it's all in the constants, isn't it? Jules

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

Hello Don, Thursday, August 28, 2008, 10:32:43 AM, you wrote:

Seems like you can make a pure hashtable by unsafePerformIO on the impure one, and exporting only 'lookup'..

probably yes, but it will lose a bit of performance due to incremental building of hashtable. actually, writing HT module from scratch is very easy - all we need is a prime searching function (in order to establish array size). everything else: data HT a b = HT (a->Int) (Array Int [(a,b)]) create size hash list = HT hashfunc (accumArray (flip (:)) [] (0, arrsize-1) (map (\(a,b) -> (hashfunc a,b)) list) ) where arrsize = head$ filter (>size)$ iterate (\x->3*x+1) 1 hashfunc a = hash a `mod` arrsize lookup a (HT hash arr) = List.lookup a (arr!hash a) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com