Canonical way to write a compare function?

What is the canonical way to write a compare: t -> t -> int function that takes a number of components of t into account? Here is an example but I’m not sure about the most natural way to implement it:

type t =
  { a:  string
  ; b:  int
  ; c:  float
  }

let ts = 
  [ {a="a1"; b=2; c=1.0}
  ; {a="a2"; b=3; c=0.0}
  ]

(** sort by c, b, a *)
let cmp t1 t2 =
  let x = compare t1.c t2.c in
  if x <> 0 then x else
  let x = compare t1.b t2.b in
  if x <> 0 then x else
  compare t1.a t2.a

I realise that the indentation is not correct - I wanted to emphasise that components are compared in a linear order with most significant components first.

2 Likes

There is a module for that in containers ( https://c-cube.github.io/ocaml-containers/last/CCOrd.html ), so that you can write:

let cmp t t' =
  CCOrd.(float t.c t'.c
         <?> (int, t.b, t'.c)
         <?> (string, t.a, t'.a) )
3 Likes
#require "ppx_deriving.ord";;

type t =
  { a:  string
  ; b:  int
  ; c:  float
  }
[@@deriving ord]

That will generate you a suitable compare function automatically.

If you want to write it manually, I suggest writing the function as let compare {a; b; c} other = .... That way, the compiler will warn you if new fields get added later.

The reason not to rely on the generic compare is that I would want to ignore some fields or give some precedence over others. Is this supported by the PPX?

Looks like you could use [@compare skip] on such fields (let skip _ _ = 0), from a look at the ord docs.

It doesn’t say how to control the precedence, but I’d assume it compares the fields in the order of their definition.

Another option is [ppx_compare](https://github.com/janestreet/ppx_compare https://github.com/janestreet/ppx_compare), which will consider the fields in the order they are defined, skipping those annotated with [@compare.ignore].

1 Like

What happens behind there scenes there @zozozo? Is CCOrd ppx based?

@orbifx There is no magic at all. What happens is that past the first comparison, you provide triplets of a compare function and two values to be compared, and the triplet is evaluated (meaning the compare function is actually called on the arguments), if and only if the previous comparison returned 0. You can see the code at : https://github.com/c-cube/ocaml-containers/blob/master/src/core/CCOrd.ml#L42

2 Likes

Taking the clever code from the containers library into account, my code could be written like this:

let (<?>) c (cmp,x,y) =
  if c = 0
  then cmp x y
  else c

let cmp t1 t2 =
  compare t1.c t2.c
  <?> (compare, t1.b, t2.b)
  <?> (compare, t1.a, t2.a)

This seems to me a nice way of doing it. If I wanted to, I could use something else than the generic compare function.

3 Likes

I think the indentation is fine, and this is exactly how I would write it myself (apart from variable names).

It may look strange to someone used to the C-style languages, but note how a C programmer might use a sequence of if (...) return ... in a similar fashion. In pure functional, code return is not a good option as it would count as an effect, at least if you think of it as a continuation rather than syntactic trick. Nevertheless, this eliminate-case-and-proceed style fits very nicely into the OCaml syntax as the an if-then-else is grammatically similar to a let ... in line or a monadic ... >>= fun ... -> line.