Re: [Caml-list] Writing the function Set.map using first-class modules and 4.00 inference

[Radu Grigore <radugrigore@gmail.com>]

On Mon, Nov 5, 2012 at 10:12 AM, Gabriel Scherer
<gabriel.scherer@gmail.com> wrote:
> You haven't tested the bad case, where the list is nearly sorted but
> not exactly

It's 3.7% slower, rather than 3.6% for random lists. (But, you
shouldn't be calling it "*the* bad case".)

> Another problem is that you call the
> user-defined comparison more than necessary, [...]

I would note only that the "necessary" number of comparisons is not
really achieved with your optimization, for the simple reason that the
minimum number of comparisons is hard to compute. [1]

> pay costs that a demanding user could request to skip by having
> of_sorted_list and of_list exposed directly, and making the choice
> herself.

I'm not sure what costs you are talking about:
(1) If it's the case of sorted lists, then that user is already paying
a much bigger price now.
(2) It it's the case of non-sorted lists, then the demanding user can
always do what they do now.

> A note on API design: [...] My personal opinion is that we
> should preserve the abstraction of Set and Map, reject all operations
> that rely on a representation assumption of sorted balanced trees
> (unfortunately some of them, such as split, have already crept in),

The (of_list : elt list -> t) function relies on no assumption about
how the set is implemented. With *any* reasonable implementation of a
set, you should be able to build it from a list. The only reason to
*not* put it in the interface would be if the user could write an
implementation that is just as good. But they can't.

[1] http://oeis.org/A036604