Re: [Ocaml-lib-devel] Proposal : BinTree

[Amit D. <adubey@CoLi.Uni-SB.DE>]

> >     is there any advantage of
> >
> > > t : ('a ,'b) tree ref;

> > over:
> >
> >     mutable t : ('a, 'b) tree;

> It's for recursion, since are left and right trees are both ('a , 'b ) tree
> ref. The problem is that you cannot pass a mutable field to a function
> like a ref.

I'm a bit confused...  unless you want to make a change to a subtree from
two places, this shouldn't be necessary.  Taking a quick peek at the code,
it doesn't seem like this happens (but maybe I missed something).  If
this isn't the case, you could just as easily pass around the unmutable
structure, and assign it where you need.

> 
> > Also, what are the relative advantages of having this vs.
> > putting a mutable wrapper around Map?  Map, if I'm not mistaken,
> > makes some guarantees of the trees being balanced (both add
> > and remove in Map call the balancing function).
> 
> Map does not allow to have several items with the same key in it.
> Calling add is replacing the current binded item if any.
> I think it's more convenient to have a structure that can "shadow" items
> just like Hashtbl do.

Ok, makes sense!  However, the main thrust behind my suggestion was more
about the worst-case performance of insertion and removal...  Map already
has the balancing code written, even if a wrapper isn't appropriate,
perhaps you could steal'n'hack the bal, add and remove functions from there?

    -Amit