RFC: Data.StringMap

[Axel Simon]

On Thu, 2005-08-18 at 12:17 +0100, Adrian Hey wrote:
> On Thursday 18 Aug 2005 8:27 am, Axel Simon wrote:
> > On Thu, 2005-08-18 at 08:25 +0100, Adrian Hey wrote:
> > > Also, I'd be grateful someone could tell me what the
> > > data structure I've used is actually called :-)
> >
> > AFAIK, what you've implemented is called a trie, pronounced "try" from
> > retrieval.
> 
> Thanks, I guessed it is some form of trie but I'm a bit confused about
> the precise definitions of various very similar data structures. I was
> looking at..
>  http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic7/

Ah! I thought it was a benign/naive question, but it really was a trap
and I fell for it...

> 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"?
> 
> The TString type is basically a linked list which may or may not be terminated
> with an N way fork (in the form of an AVL tree, N >=2), but then strings are
> linked lists anyway in Haskell. So is this compact or not I wonder?

I guess in that sense there are no compact tries in Haskell. Unless you
use PackedString.

> It's compact in the sense that it doesn't require an AVL tree at every
> character (most of which would be singletons in practice). I guess you
> could achieve the same thing with this definition..
> 
> data TString v = TString {-# UNPACK #-} !Char String v !(AVL (TString v))
> 
> .. which might look more compact, but isn't really AFAICS (well not while
> Strings are linked lists of boxed Chars).

There is still a difference: If you look up a word, the suffix of the
word will never be evaluated. In particular, the chain of TString nodes
containing a character each will never be built. This could avoid
potential space leaks. Furthermore, a compiler might do some
optimisation magic on lists, which doesn't apply to your data type.

> Replacing the String with a packed string might be better, but I'm not
> sure how efficient those are in reality (and if I was to go that route
> it might be a lot simpler and more efficient to use a completely different
> approach, such as hashing and a pure AVL tree say).

PackedStrings are certainly not the right thing to put into a general-
purpose data structure. The problem is that if you request one character
from a thunk that contains a conversion to PackedString, the whole
packed string will be built before this single character can be
extracted again. Hence the library would have a rather weird evaluation
behaviour. I once fiddled with Olaf Chitil's pretty printing library and
tried to improve it by using PackedStrings. It blew right up into my
face since it forced stuff which was nicely delayed before, rendering
all benefits of the concise representation useless.

My 5p,
Axel.