Attempt to code a parameterized compare

Learning
3

Modular imlicits are indeed not in the compiler trunk, tho there are these old compiler variants available from opam:

$ opam switch list-available | rg implicit
ocaml-variants      4.02.1+modular-implicits               OCaml 4.02, with support for modular implicits.
ocaml-variants      4.02.1+modular-implicits-ber           OCaml 4.02, with support for modular implicits and staging.

You may be interested in the Modular Implicits thread to see the state of development and read about related stuff.

This defines equality on two lists based on whether the elements in the middle of each list are physically equal. This is because

  1. List.nth : 'a list -> int -> 'a, and just returns the single element located at the nth position in the index.
  2. The == operator " tests the identity of its arguments, by testing the physical equality of memory representations" (source)

Unless you’re after a very peculiar sort of equality, I don’t think this is what you want :slight_smile:

Using the OCaml standard library, a minimal definition of polymorphic equality lists is just

let equal_lists = (=)

this is because the equality operator is already polymorphic. Try it in the top level!

utop # [1;2;3;4] = [1;2;3;4];;
- : bool = true
utop # ["a"; "b"; "c"] = ["x"; "y"; "z"];;
- : bool = false

In OCaml parlance, compare functions usually express inequalities rather than equality. E.g., Int.compare : int -> int -> int where the Int.compare m n is -1 if m < n, 0 if m = n, and 1 if m > n. The standard OCaml library also provides a polymorphic compare function, and that too will work on lists out of the box.

See the section in RWO on polymorphic compare for caveats and good reasons to avoid using it when performance is a concern.

If you want to define your own polymorphic comparison function, over lists is to take an argument providing a comparison of each element. Here’s one possible implementation:

utop # let rec mycompare compare xs ys = 
match xs, ys with
| [], [] -> 0  (* two empty lists are equal *)
| _, []  -> 1  (* xs is greater than ys if xs is longer *)
| [], _  -> -1 (* xs is less than ys if xs is sorter *)
| x::xs, y::ys -> 
  let c = compare x y in 
  if c <> 0 then 
    c                        (* The first inequality between elements is our result *)
  else 
    mycompare compare xs ys  (* or keep comparing the elements *)
;;
val mycompare : ('a -> 'b -> int) -> 'a list -> 'b list -> int = <fun>

You use it like

utop # mycompare Int.compare [1;2;3] [9;10;11];;
- : int = -1
utop # mycompare String.compare ["foo"] ["baz"];;
- : int = 1

If you use a standard standard library replacment such as base or containers you’ll get the properly parameterized functions for all generally useful data structures.