[Ocaml-lib-devel] Sets, ordered and unordered

[Brian H. <bh...@sp...>]

Actually, what I'd like to see is the stdlib Set to give up pretending to 
maybe be unordered, and declare itself ordered.  And to implement a true 
unordered set built on hash tables (sometimes, checking for membership in 
O(1) instead of O(log n) is usefull).  With both modules inheriting from a 
common Set module.

Which opens up a whole new can of worms.  To what extent do we want to go
down this path?  At the end, we have a whole family of datastructures,
with all the obvious relationships, both derived from (an array is a form
of a list) and built on top of (a hash table can be build on top of an
array or a tree).  And most of the implementations.  Hash tables on top of
expandable arrays, hash tables on top of trees, etc.

Done correctly, it could be an incredible advantage to defining new
algorithms and data structures.  It's be easy to "Ok, this new data
structure builds on top of a balanced tree- so I just use the standard
balanced tree and build ontop of it...".  Rather like BLAS is used for the
introduction of numerical libraries.  Plus you would never get caught
going "Gee, I wish they had built X ontop of Y instead of Z".

The cost for this generalicity is, of course, performance.  And memory.  
Take one example- my implementation of priority search queues.  I have
tree information (children references, key), balancing
information (color), tournament information (domination), and priority 
queue information (element references, from which I get priority) all in 
the same structure.  In the 'degenerate' case of the ADT library, they 
would be in four different structures, referencing each other in some sort 
of list.  

Also, dependencies would be fun in a bad way- to use the equivilent to
PSQueue, you'd need to pull in at least four different modules (tree,
balancedTree, tournament, psqueue) if not more (set, priority queue,
queue, etc).  This basically forces you to the monolithic library 
approach.

Brian