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.