RFC: Collection Framework, reprise.

[Jean-Philippe Bernardy]

On 2/27/06, Ross Paterson <ross at soi.city.ac.uk> wrote:
> > We are planning to move to AVL
> > trees for A. Hey, which do not provide a O(1) size function.
>
> What will be gain for this move?  And what will we lose, apart from
> O(1) size?

The gains:
1. Christian Maeder and others report a significant performance improvement.
    This is the main motivating factor.
2. The AVL tree library is very comprehensive and can be very useful by itself.
3. A separate balanced Tree infrastructure provide many benefits:
  * Shared code between Map and Set.
  * Conversion between those should then become more efficient
(requested by John Meacham)
   * Possibility to base more data structures on AVL trees (eg. StringMap)
   * It should be easier to fine-tune algorithms. We will provide
toTree/unsafeFromSortedTree that will allow users to write code that
have access to the tree structure.

   An alternative is to keep the same tree implentation, and separate
the Tree data type from the high-level Set/Map abstract type. This is
yet more work however, and ignores the fact that the trees in set and
map are actually different types.

The loss:
* More code to maintain. AVL trees are also trickier.
* Transitional costs: changes in behaviour may affect user code.
(Despite many efforts to be as compatible as possible)

Cheers,
JP.