RFC: Data.StringMap

[Jesper Louis Andersen]

Adrian Hey wrote:
> 
> I'm not entirly clear about the difference between "tries", "compact tries"
> (depends what you call compact AFAICS) and "PATRICIA tries", and is a PATRICIA
> trie the same thing as a "PATRICIA tree"?

A trie and a PATRICIA tree is not the same thing. A PATRICIA tree is 
also known as a Radix tree, which discloses the way it works a lot more 
since it basicly stores bitstrings but skips over places where the 
strings are common. Knuth, ''The art of computer programming'' Volume 3 
has a little 1.5 page treatise on PATRICIA trees and does also refer to 
further information.

I guess the trie/tree confusion can be neglected and taken as being 
''the same''.

A good way of looking at tries is due to Chris Okasaki, I think. He 
views them as a (SML-) functor from finite maps to finite maps turning a 
FiniteMap Char a into FiniteMap [Char] a. ''Purely functional data 
structures'' is the book.