On Mon, 31 Oct 2005, Jonathan Bryant wrote:

> Quick (and rather random question) about the standard library.  I
> noticed that, like the STL, many of the modules are very similar and
> implement many of the same functions (iter, map, etc.).  Unlike the STL
> or the Java Standard API, these modules are each completely
> independent.  Why hasn't there been a push to do something like
> functorize these modules?  For example: List, Array, Hashtbl, Set, and
> Map are all collections.  Couldn't you factor out something to make it
> easier to extend the library, sort of like the Java API?  Parametric
> Polymorphism handles the generics of the elements of the set, so
> couldn't the algorithms be factored out leaving three distinct parts
> (Elements, Collections of Elements, Operations on Collections), sort of
> like in the STL?

The question here is: why?  What good would factoring out the common base 
actually do?

In Java and C++, with their style of inheritance, if you don't explicitly 
factor out the common base, then you can't inherit from/manipulate the 
common base functionality.  But Ocaml does structural comparisons for 
matching, not inheritance trees.  So if you wanted to write a bit of code 
that could be used with lists, arrays, maps, etc., you could just write:

module type Collection = sig
     type 'a t
     val map : ('a -> 'b) -> 'a t -> 'b t
end;;

module MyCode(Col: Collection) = struct
     ...
end;;

OK, you have to hack a little bit because list.mli and array.mli don't 
explicitly define the 'a t type.  But they could.  And going:

module MyListCode =
     MyCode(struct type 'a t = 'a list let map = List.map end)
;;

isn't that big a deal.  But the important point is that this still works, 
even if the common functionality you want to depend upon isn't explicitly 
factored out.  A similiar stunt can be done with objects.

The other reason to do this is to factor out the common code.  But there 
isn't that much code to share among the various maps, iters, and folds. 
Well, a little bit of shared code between Map and Set (and see the Pagoda 
Core Foundation code for an example of how they could share code), but 
that's about it.

I suppose you could convert every ordered collection into either an 
iterator of some sort or a lazy list, and then map/fold/iter on that and 
while this sort of functionality is usefull in general (and I'd like to 
see it added to the standard library), there are generally usefull 
optimizations that can be applied.  For example, if I'm mapping a Map to 
another Map, I know the new tree will have the same shape as the old 
tree.  And so on.  This sort of optimization would be lost going through 
iterator or lazy list.

Brian