Heirarchical name space allocation /Trees

[Adrian Hey]

On Friday 02 Apr 2004 10:18 am, Christian Maeder wrote:
> Adrian Hey wrote:
> > If I've understood you, I have to say I'm sceptical about this. IMO the
> > API exported by Data.Trees.AVL should be the raw AVL tree (only) API,
> > designed exclusively for the convenience of AVL tree users and should
> > not be constrained by other considerations.
> >
> > I can see no good reason why the the API of Data.Trees.AVL should bear
> > any resemblance to that of Data.Trees.RedBlack or any other kind of
> > tree or container. It's perfectly reasonable that thay should be
> > different because they facilitate different operations with varying
> > degrees of efficiency (or maybe not at all). If folk have chosen AVL
> > trees in preference to RedBlack trees or vice-versa they have presumably
> > done so for a good reason.
>
> I thought, the common denominator (i.e. interface) are binary search trees.

I think we should be careful about making unwarranted assumptions about
what people are going to be doing with these trees. You could use AVL trees
to implement a purely functional queues for instance, in which case the tree
elements are not ordered by value. I don't know how this would compare
with other queue implementations, but I think the possiblity of things like
this should at least be considered when designing "the" AVL tree library.

Even in those cases where the elements are ordered, assuming that element
types will all be instances of "Ord" is an unwarranted assumption and can
be rather inconvenient. For many types there is no obvious unique ordering
and in in such cases it is IMO far simpler to allow the appropriate
comparison function to be passed as an explicit argument.

By all means write high level "classyfied" wrappers around the AVL primitives,
but the primitives should still be exposed for those that want them, and
Data.Trees.AVL seems like the place to do it.

Higher level libraries that try to provide a simpler unified view of all sorts
of different trees or containers should be somewhere else I think.

P.S. I find this data type very useful for writing sorting, searching
and set related stuff that's as general purpose as (I think) it could
possibly be..

  -- Result of a combining comparison.
  data COrdering a = Lt | Eq a | Gt

So set (list, tree or whatever) union looks like this

  -- Combines "equal" values
  union :: (a -> a -> COrdering a) -> Set a -> Set a -> Set a

and intersection looks like this..

  -- Combines "equal" values
  intersect :: (a -> b -> COrdering c) -> Set a -> Set b -> Set c

Which I find more useful than..

  intersect :: Ord a => Set a -> Set a -> Set a

(taken from Data.Set)

Regards
--
Adrian Hey