Trie implementation
John Meacham
john at repetae.net
Mon Feb 14 19:29:26 EST 2005
On Mon, Feb 14, 2005 at 04:03:59PM +0000, Duncan Coutts wrote:
> On Mon, 2005-02-14 at 14:10 +0000, Keith Wansbrough wrote:
> > > > Has anyone else done this? Should I polish it up and offer it for
> > > > inclusion in Data?
> > >
> > > Lots of people have. :-)
> > >
> > > Here's mine, for the record:
> >
> > OK, thanks all... I will see if I can pull them all together into
> > something sensible for a Data.Trie proposal. Watch this space!
>
> Great!
>
> Now that we've got Data.IntMap which provides the Data.Map interface but
> specialised for Int keys (and with a fast implementation based on a
> different data structure), might it also be a good idea to do
> Data.StringMap and implement it in terms of Data.Trie Char?
>
> Am I right in thinking that Tries would usually be a faster finite map
> data structure than ordinary Data.Map balanced binary trees?
What we really need is for someone to implement this :)
http://research.microsoft.com/Users/simonpj/papers/assoc-types/index.htm
Then we can have a single Data.Map which uses Tries for list keys,
IntMap for integral types, and so forth.
John
--
John Meacham - ⑆repetae.net⑆john⑈
More information about the Libraries
mailing list