Heirarchical name space allocation /Trees

Adrian Hey ahey at iee.org
Fri Apr 2 08:08:09 EST 2004

On Wednesday 31 Mar 2004 2:15 pm, Christian Maeder wrote:
> Adrian Hey wrote:
> > Does the Data.Trees.AVL code exist yet? If not I could donate my
> > implementation. I put quite a bit of effort into producing what
> > I believe should be a fairly fast implemenation.
> The Tree, Seq, Set, Bag and Map stuff should be designed uniformly and
> therefore be laid into a single hand, i.e. JP Bernardy?, at least
> initially.
> Rather than enforcing uniformity by a collection class (as proposed
> elsewhere), I would like uniformity at the module level wrt. exported
> functions and types. The hierarchy should allow for several different
> implemenations of one type with (almost) the same module interface.
> The current problem is agreeing on interfaces, while there exist quite a
> few implementations (from which we can pick all the good ones).
> We should consider your code and (let you) adapt it to an (yet unknown)
> interface in order to easy performance measures.

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.

If folk also want find some common ground for all container types and
make generic container classes or whatever, and want to make instances
of those classes from AVL trees, that's fine too. But this should be
done elsewhere in the hierarchy I think, or maybe included as a supplement
to (but not a substitute for) the raw API.

Adrian Hey

More information about the Libraries mailing list