> For backwards-compatibility reasons, this over-general type is unlikely to change, and the compiler has no way otherwise to infer that the ~cmp argument represents a comparison. Modifying the definition to
>
> let rec find ~(cmp : 'a -> 'a -> int) x = ...

Is it really equivalent to replace the automatically determined type “'b”
by the type annotation “'a”?

(I assume that it can occasionally be more important to distinguish
between the specified letters.)


> val find : {C : Comparable} ->C.t -> (C.t, 'a) t -> 'a
>
> I hope this helps, or is at least informative.

Thanks for such constructive feedback.

It would have been nice if this information can be shared also by the mailing list.
https://sympa.inria.fr/sympa/arc/caml-list/2021-01/


Would you get into the mood to add comments for any further evolution according to
affected software libraries?

Example:
https://github.com/elfring/OTCL/

Regards,
Markus

On Sun, 3 Jan 2021, 07:54 Matthew Ryan, <matthew@o1labs.org> wrote:

Hello Markus,

OCaml infers the most general type for an expression. For example,

let rec fold_left acc xs ~f =

  match xs with

  | [] -> acc

  | x :: xs -> f acc x

will infer the type

val fold_left : 'a -> 'b list -> f:('a -> 'b -> 'a) -> 'a

where the distinct types for the accumulator and list elements are inherently more powerful than if they were unified.

For identifying comparison functions, it could be argued that the type of Stdlib.compare is over-general, and perhaps should be

type comparison_result = Lt | Eq | Gt

val compare : 'a -> 'a -> comparison_result

For backwards-compatibility reasons, this over-general type is unlikely to change, and the compiler has no way otherwise to infer that the ~cmp argument represents a comparison. Modifying the definition to

let rec find ~(cmp : 'a -> 'a -> int) x = ...

and using the heuristic that 'a -> 'a -> int is likely a comparison is probably the easiest way to proceed for now.

There is a proposal for modular implicits (and a proposed pull request for modular explicits) which may make it easier to infer this in the distant future. The syntax there is approximately

module type Comparable = sig

  type t

  val compare : t -> t -> int

end

let rec find {C : Comparable} (x : C.t) = ...

val find : {C : Comparable} ->C.t -> (C.t, 'a) t -> 'a

I hope this helps, or is at least informative.

Regards,

Matthew

On Sat, 2 Jan 2021, 15:42 Markus Elfring, <Markus.Elfring@web.de> wrote:

Hello,

I have taken another look at a few functions of a software library
where comparison functions should be passed.

…
let rec find ~cmp x = function
    Empty -> raise Not_found
  | …

let not_found_default_action ~value ?compare:(cmp=Stdlib.compare) =
    raise Not_found
…


Interface descriptions can be generated then in a known format for OCaml 4.11.1.

…
val find : cmp:('a -> 'b -> int) -> 'a -> ('b, 'c) t -> 'c
val not_found_default_action : value:'a -> ?compare:('b -> 'b -> int) -> 'c
…


Now I find two details interesting for further clarification.

1. The first reference for a comparison function seems to express a need for
   different data types “'a” and “'b” while a single type might be sufficient
   for the comparison function according to the second function.

2. The specification of “Stdlib.compare” looks clear according to the semantics
   for a default parameter in a ML source file while the OCaml arrow representation
   can look more challenging.
   How would you recognise that such a function parameter should be applied
   for comparison calls?

Regards,
Markus