[m-dev.] Hm, yes, re: obsolete bintree(_set)

Julien Fischer juliensf at cs.mu.OZ.AU
Mon Feb 20 15:52:34 AEDT 2006


On Wed, 15 Feb 2006 doug.auclair at logicaltypes.com wrote:

> >For the benefit of all of involved in this discussion I draw your attention
> >to the following comment at the top of bintree.m:
> >        % Stability: medium (obsolete).
> >        %
> >        % This module exists primarily for historical reasons. It is unlikely
> >        % to be useful, and may not be supported in future releases.
> >        % You should use `map' instead.
> >Similarly for bintree_set.m.  AFAIK this is still the case and while it is
> >we won't be adding anything to these modules.
>
> Yes, but 1. it /is/ useful for those of us user who wish to use a balance
> binary (not N-ary) tree (so, from a practical standpoint, the comment is
> wrong) and 2.

The intent of the bintree module (despite its name) is *not* to provide binary
trees, it is to provide an implementation of the map ADT using binary trees
(in that sense it may have been better if it were named bintree_map or
something).  If you wish to directly to manipulate binary trees it would
better to have a module that exports a binary tree type for that purpose;
subverting the interface to the bintree module is not the way to do it.

If the Mercury standard library had a binary_tree module it could of course be
used to implement both bintree and bintree_set without upsetting the
abstraction barriers in place in those modules.  There hasn't been sufficient
demand for such functionality which is why it isn't in the standard library.

> I've seen this message since circa 0.10.1 or so?  This makes
> it hard for me to give the obsolete marking in the comment block (not, as
> you see, as any pragma to any item in the modules' protocols) any credit ...

See below.

> And bintree(_set) is still in the ROTD, meaning, given the release lag, that
> it will be with us for AT LEAST another year.  Perhaps, then, it should be a
> productive (AT LEAST) year?  That was the thrust of my posts: if I need to
> do other than left-to-right traversal of the set, perhaps other users needed
> the same functionality.

What do you mean by a left-to-right traversal of a set?  Sets are *unordered*
collections - there is no left and right as such.  I think what you are
talking about here is a left-to-right traversal of a tree.

> Or, perhaps these modules should be removed immediately from the ROTD and
> next release, preventing pesky gadflies, such as myself, from raising
> feasible usage issues with published protocols?  This same comment applies
> to the (more than one) modules that state at their head "this module is
> exactly the same as module X, use that module instead".

Our (somewhat feeble) excuse for not having removed them, is basically that
we haven't eliminated all uses of them from the compiler yet.  Yes, it's
something that ought to be done but it's not a very high priority task and I
guess the right rainy day hasn't come along ...

> Of course, removing bintree(_set) means that anyone needing to use an AVL
> tree would be required to implement this code, for themselves, each time a
> need occurred.

Since neither of the modules you are referring to provide generic tree
operations, you would need to code it yourself anyway - or make a case that
such functionality would be sufficently useful that it should be included
in the standard library.

Cheers,
Julien.

--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------



More information about the developers mailing list