RFC: Data.StringMap

[Adrian Hey]

On Friday 19 Aug 2005 9:49 am, Jesper Louis Andersen wrote:
> 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.

Thanks for that reminder (I've got a copy but it never occured to me
to look:-) 

I've just had a quick look, I'll have to look some more to grok
why this is significant (Knuth seems to have explained the solution
in some detail without first explaining the problem :-). Maybe I
have to read the whole chapter to find that out.

At..

 http://www.nist.gov/dads/HTML/patriciatree.html

I find the definition..

 "A compact representation of a trie where any node which is an only
  child is merged with its parent"

So put another way, every node must have at least 2 (or 0) children.
Now if for "node" you read "TString terminated with Fork (or Term)",
then it seems like what I've used could be called a PATRICIA tree,
albeit one where the nodes are represented as linked lists.

But I dunno, maybe some would say that a linked list representation
means they don't qualify as being nodes at all. Or maybe the
above definition is just wrong or over simplified (but it would
seem to be consistent with the trees(tries) used in Data.IntMap,
which are PATRICIA apparently).

Anyway, this is probably all getting a little OT for this mailing
list so I apologise for this.

Regards
--
Adrian Hey