More suitable data structure needed

[Dr Mark H Phillips]

On Wed, 2002-08-21 at 17:50, Dylan Thurston wrote:
> This is the same as one way of representing search trees, called a
> "trie".  Two representations in Haskell are:
> 
> > data Trie a = Trie [(a, Trie a)]

I touched on the following in my response to Hal Daume's email, but it's
probably worth asking properly...

Am I right in thinking there is no way of doing this using an
"essential" type?  What I mean is, 

  data Age = Age Int
  data Names = Names [String]
  data Person = Person (Age,Names)

can be used to represent the details of a person, but the "essential
type" corresponding to Person, is

  (Int,[String])

Having the type Person is useful in that, basically it is a duplicate
of the essential type, to be used for a specialized purpose.  But there
is always the option of converting it to the essential type, thereby
allowing higher order functions to be applied to it.

But for the "Trie" type you have above, I am not aware of any way of
converting this to an "essential type".  What I am thinking, is
something like
    [(a, *)]
where '*' means to recursively refer to yourself.

> or, using the FiniteMap module, if you only care about the set of
> lists,
> 
> > data Trie a = Trie (FiniteMap a (Trie a))

Am I right in thinking that FiniteMap is like a list, but that it is
more efficient with "random access" use than a normal list?

Thanks for your help,

Mark.