[Caml-list] Suggestion about balanced trees in stdlib

[Gerd Stolpmann <info@gerd-stolpmann.de>]

Hello list,

I have always wondered why there are two implementations of balanced trees
in the standard library: Set and Map. The set of operations is different,
but the representation is (almost) identical. Furthermore, neither of the
two modules claims to implement balanced trees in the interface; for example
Set.iter does not specify the order of iteration although the implementation
iterates linearly from the smallest to the largest element.

The idea is to introduce a third module Balanced_tree, defining all of the
operations for the two mentioned modules, but announcing them as balanced
trees. This would have the advantage that the operations could be specified
in a more complete way (Balanced_tree.iter is specified as iterating in an
ascending way), and it would be reasonable to add further operations that
know about the representation.

Of course, Set and Map would recur to that more special module.

Balanced_tree would have the representation of Map, i.e. the elements are
pairs of keys and attached values. To emulate Set, the value () is used.

Balanced_tree would have the following operations:

- all of Set
- all of Map
- operations on intervals: "iter_interval", "fold_interval", and "interval"
  (returning the subset)

The interval operations have an important application: One can program indexes
that can be accessed by coordinates (e.g.: return all objects that are currently
visible in the viewbox).

What do you think about this?

Gerd
-- 
----------------------------------------------------------------------------
Gerd Stolpmann      Telefon: +49 6151 997705 (privat)
Viktoriastr. 45             
64293 Darmstadt     EMail:   gerd@gerd-stolpmann.de
Germany                     
----------------------------------------------------------------------------
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners