Re: [Caml-list] stl?

[Brian Hurt <bhurt@spnz.org>]

On Wed, 4 Mar 2009, Yoann Padioleau wrote:

> My goal is not being backward compatible. Of course you can
> keep your old function and define new functions ...
> My goal is to evolve code, so I want to change the behavior of 'foo',
> and I want to benefit from this new behavior,
> but I want this evolution to have the less collateral effects on
> the structure of the rest of the program.
>
> For instance I got a set of functions that were working on some 'a
> stuff, and I was using somewhere a naive list as a first draft. Later
> I want to optimize things, and put those 'a in a more efficient
> data-structure, but if use the Map data-structure, then I will be
> forced to change lots of things. Argh, damned. Well, wait, I will just
> use the defunctorized interface of Hashbtl :)

Especially in the realm of data structure libraries (like the STL), I 
really question the utility of this.  Data structures vary wildly in the 
performance characteristics of their various operations.  For example, 
accessing a arbitrary element of a map is O(log N), doing so in a list is 
O(N).  But accessing the first element of a map is O(log N) in a map, but 
O(1) in a list.  So if I write my algorithm to always only need the first 
element of the sequence, but never need an arbitrary element, then 
replacing a list with a map is a real bad idea- and I don't need to 
perform actual comparisons to tell this.

Where this does come up is when what you're really doing is refactoring 
code.  Say I originally thought that I was only going to need the first 
element, but it turns out that I'm doing a lot more arbitrary accesses 
than original thought.  In this case, however, you're not just swapping 
this data structure out for that one, you're also changing more or less 
large chunks of the code to reflect the new assumptions.

Ocaml's huge advantage here then is not functors, or objects, or even type 
variables- it's just strong static typing.  This allows you to change 
things and just see where things break.

>
> Again, just imagine one second that 'a list were not present in OCaml,
> and that the only way you had to make a list would be to use
> a functorized interface of a List module. Would you like that ?
> (that's what we are forced to do when using Map and that's why
> I always use Hashtbl instead).

Humorously enough, I'm doing exactly this.  In a bunch of code I'm playing 
with, I've implemented an NeList module- nothing fancy, just a few dozen 
lines of code and the basic list operations, only the lists can not be 
empty.  They always have to contain at least one element.

But seriously, you hate functors that much?  The overhead of doing:

module StringMap = Map.Make(String);;

is so high to you, that you simply don't do it?

Mind if I ask why?

Brian