Trie implementation

Duncan Coutts duncan.coutts at worc.ox.ac.uk
Fri Feb 11 07:33:20 EST 2005


On Fri, 2005-02-11 at 11:28 +0000, Keith Wansbrough wrote:
> Hi... I was writing some code yesterday to walk over a directory tree, 
> and needed a Trie.  Not seeing one around, I wrote a basic 
> implementation of the functions I needed (attached below).
> 
> Has anyone else done this?  Should I polish it up and offer it for 
> inclusion in Data?

Dr. Ralf Hinze has an implementation of Tries too:

http://www.informatik.uni-bonn.de/~ralf/software/Library/Trie.html

I believe (but cannot now find the reference) that Ralf has licenced
this code under the GPL (at least he allowed me to use it under the
GPL). You'd want to check with him if you want a different license.

I also have a version derived from Ralf's version for "MultiTries" ie
like a bag rather than a set.

http://cvs.sourceforge.net/viewcvs.py/haide/haide/src/utils/MultiTrie.lhs?rev=1.2&view=markup

There's also a few QuickCheck tests for that module.

Duncan



More information about the Libraries mailing list