Trie implementation

[Duncan Coutts]

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