AVL Trees available

[Adrian Hey]

On Wednesday 19 May 2004 10:47 am, Simon Marlow wrote:

> I'm happy for this to be "the" Data.Trees.AVL library.  I'm sure others
> will want to comment on the details.  I wonder whether it would make
> sense to have a specialised AVLMap type, which would let you optimise
> the representation of AVL-based finite maps?

Do you mean a newtype wrapper for the current AVL type or distinct
algebraic type which contains both the key and the associated value
as separate fields (like the Map type folks were talking about
recently)?

If you mean the former, one thing I was thinking about doing was creating
an AVL based clone of the current Data.FiniteMap library so folk could
experiment with the effect of using both on real programs just by
changing their imports.

If you mean the latter, I'm not keen on this because it would mean
duplication of a lot of code for the new type, and I'm not sure that
it would be an optimisation at all. I considered this but decided
against it on the grounds that I suspect a major contributor to
the true cost of tree operations is heap burn rate. The AVL tree
type has only 3 fields in each constructor (not 5 as with the Map
type for example), and the code was carefully written to avoid
unnecessary heap construction wherever possible. Doing this would
result in 4 fields in each constructor.

But I may be wrong about this, and I guess it wouldn't be to hard
to find out for sure by doing a cut and paste job once the current
AVL code is a bit more stable. Keeping pairs separately has it's
own overheads, like an additional level of indirection during
searches and more heap records (so possibly slower gc). But if
the tree is so stable that lookup times dominate costs it may
be better to convert the entire thing into an array (or maybe
an unboxed array of Ints and a corresponding array of values)
and do binary searches on that instead.

> > I'd also like to book "Data.COrdering" too, if that's OK.
>
> Data.COrdering is less obviously the right thing.  Can you give some
> motivation for the design here?

Because you you generally do end up combining values which turn out
to be "equal", in some manner. If you don't use a function which
returns a COrdering, then you have to either..

 Pass the comparison and combining function separately down your
 recursive search or whatever. But this will have extra runtime
 overhead, which is often unnecessary since the only time the
 combining function is ever used is when the comparison returns EQ.

or..

 Use some default combining function (like pairing) and apply the
 real combining function later. But pairing is the only reasonable
 default combining function I can think of, and this not always
 the right type (e.g. for pushing elements in a tree or set union),
 and even when it's OK type wise you've still got the overhead of an
 additional map operation (e.g for set intersection). You could get
 around the type problem using lists I suppose, and use (++) as the
 default combining function, but this doesn't seem very attractive
 to me.

Anyway, if that doesn't persuade you I can give a more pragmatic
reason :-)

The AVL library depends on COrdering, so if it's going to exist
then COrdering has to exist too. I could make it part of the AVL
library, but since COrdering is not in any way dependent on
the AVL library (and potentially useful in it's own right elsewhere)
then I think it should exist independently of the AVL library.
This will stop people having to reinvent their own (incompatible)
COrdering equivalents.

Of course, I'm open to persuasion regarding the type name and the
support functions provided in the module, if anybody has strong
objections to what I've chosen.

Regards
--
Adrian Hey