More suitable data structure needed

[Andrew J Bromage]

G'day all.

On Thu, Aug 22, 2002 at 05:04:02PM +0930, Dr Mark H Phillips wrote:

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

I'm not sure what you mean by "essential" here.  Types are terms, not
regular trees.  If you want recursion, you need to go through an
explicit constructor.

The built-in list type is recursive, for example, and for that
recursion requires an explicit cons (:) constructor:

	data [a] = [] | (:) a [a]

Maybe I've been working with Haskell too long, but I don't see how
this is any more "essential" than the user-defined Trie type.

Of course If Haskell's type system supported regular trees, lists could
be represented as, say:

	type List a = Maybe (a, List a)

Once again, even if this worked, are the two Maybe constructors and the
pair constructor any more "essential" than the list type?

> 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?

Kind of.  FiniteMap is an association, so it's more like a list of
pairs.  It's usually implemented as a binary search tree.

Cheers,
Andrew Bromage