Re: [Caml-list] Announce: xsetxmap, unfunctorized, Sexp-lib aware versions of Set and Map

[Jon Harrop <jon@ffconsultancy.com>]

On Monday 21 April 2008 12:19:09 Berke Durak wrote:
> Yes you are right, I should have put a warning.  These modules are for
> peculiar cases.

Actually I would say that your style is more useful than the built-in Set and 
Map modules because you don't have to jump through hoops defining your 
own "Int" module with its own "int" type and its own comparison function over 
ints every time you want a set of integers. I would put the comparison 
function in the set itself though.

Your modules cover 99% of use cases with the lowest syntactic overhead 
possible in OCaml. However, you have inherited a couple of design flaws from 
OCaml's standard library:

. The "height" function has been inlined which has no significant effect on 
performance but makes it harder to refactor the code.

. If you special case Node(Empty, v, Empty) to a new Node1(v) type constructor 
then you can improve performance by 30% by alleviating the GC.

As Jean-Christophe says, it is dangerous. However, the whole language is 
already dangerous in this sense because it is so easy to erroneously apply 
polymorphic comparison or equality to the existing sets and maps and get 
silent data corruption. The only solution is to fix the language itself by 
allowing types to override comparison, equality and hashing.

Another inherent problem is the inefficiency of performing comparisons in this 
way in OCaml. Type specialization (e.g. using a JIT) greatly accelerates this 
kind of code by allowing the comparison function (which is almost always 
trivial) to be inlined and optimized.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e