[Caml-list] Documentation challenges for the application of comparison functions

[Caml-list] Documentation challenges for the application of comparison functions

[Markus Elfring]

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

Re: [Caml-list] Documentation challenges for the application of comparison functions

[Matthew Ryan]

[-- Attachment #1: Type: text/plain, Size: 4984 bytes --]

It's not equivalent per se, since you lose the flexibility to call the
function with e.g.

let find_float_int ~(cmp : float -> int -> int) (index : float) (map :
(int, 'c)) =
  find ~cmp index map;;

where 'a = float and 'b = int. However, it is valid -- and arguably
describes the function's contract better -- to narrow the function's type
by combining the type variables:

let find : cmp:('a -> 'a -> int) -> 'a -> ('a, 'b) t = find;;

> It would have been nice if this information can be shared also by the
mailing list.

Apologies, I misclicked reply instead of reply-all. I have copied the list
on this reply, with the earlier messages quoted below.

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

I'm happy to discuss or comment on any proposals you have. Please feel free
to tag me @mrmr1993 on GitHub if there are relevant conversations there.

Regards,
Matthew

On Sun, 3 Jan 2021, 15:26 Markus Elfring, <Markus.Elfring@web.de> wrote:

> > 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
>
>

[-- Attachment #2: Type: text/html, Size: 8333 bytes --]

Re: [Caml-list] Documentation challenges for the application of comparison functions

[Markus Elfring]

> It's not equivalent per se, since you lose the flexibility to call the function with e.g.
>
> let find_float_int ~(cmp : float -> int -> int) (index : float) (map : (int, 'c)) =
>   find ~cmp index map;;

I guess that there is the detail to reconsider if comparisons should be performed
with different data types (which corresponding to special properties of
such a programming interface).


> where 'a = float and 'b = int. However, it is valid

Thanks for such a view.


> -- and arguably describes the function's contract better -- to narrow the function's type by combining the type variables:

I would interpret involved aspects in further directions.


> let find : cmp:('a -> 'a -> int) -> 'a -> ('a, 'b) t = find;;

The elements of a data container like “Map” should usually refer to the same data type,
shouldn't they?

I am curious then under which circumstances a type like “Comparable” can be applied instead.
Will any “…able” types become more popular?

Regards,
Markus

Re: [Caml-list] Documentation challenges for the application of comparison functions

[Markus Elfring]

> It's not equivalent per se, since you lose the flexibility to call the function with e.g.
>
> let find_float_int ~(cmp : float -> int -> int) (index : float) (map : (int, 'c)) =
>   find ~cmp index map;;

I guess that there is the detail to reconsider if comparisons should be performed
with different data types (which corresponding to special properties of
such a programming interface).


> where 'a = float and 'b = int. However, it is valid

Thanks for such a view.


> -- and arguably describes the function's contract better -- to narrow the function's type by combining the type variables:

I would interpret involved aspects in further directions.


> let find : cmp:('a -> 'a -> int) -> 'a -> ('a, 'b) t = find;;

The elements of a data container like “Map” should usually refer to the same data type,
shouldn't they?

I am curious then under which circumstances a type like “Comparable” can be applied instead.
Will any “…able” types become more popular?

Regards,
Markus