Polymorphic compare on variant types

#1

Hey folks.

I’m trying to write compare functions for a bunch of variant types, and pattern matching all the variants looks kind of tedious, so I was wondering if it’s OK to use pervasives.compare for that task, e.g.:

type t = {
  id: int,
  dueDate: option(Js.Date.t),
  priority: option(priority),
  status,
  stickers: list(Sticker.t),
  title: string,
}
and status =
  | Todo
  | BlockedBy(t)
  | InProgress(Employee.t)
  | UnderReview(Employee.t)
  | Done;

let compareStatuses = (x, y) => compare(x.status, y.status);

It works in BuckleScript, but I wonder if it just happens to work for now or if there’s a guarantee.

#2

To make sure it’s safe, you’d need to check out the generated code and verify caml_compare function in BuckleScript’s caml_obj.js does what you expect it to do. I’d avoid it especially for variants with payloads, and go with something like https://github.com/ELLIOTTCABLE/ppx-deriving instead.

With ppx-deriving, you can add an annotation such as [@deriving (eq, compare) ] to your type declaration, and have equal and compare functions generated for you.

#3

As far as I know OCaml’s polymorphic compare traverses the structure of the data and for variant types it works out an ordering in terms of the declaration order of the data constructors. So e.g. Todo < Blocked(t) < InProgress(Employee.t) < ....

#4

To be honest, I wouldn’t feel safe just looking at the implementation, because implementation is not specs. Then again, given how many code out there relies on observable behavior, the implementation is not likely to change.

I’ll look at ppx-deriving, thanks!

#5

So, polymorphic compare should work e.g. for sorting in a pinch?

An by the by, is there any othere way to limit a filed to certain values (i.e., make it some kind of a sum type) and still be able to sort by it?

#6

Right, polymorphic compare can work in a pinch but beware of changing the ordering of the data constructions in a definition:

type t = A | B | C;
Js.log(compare(A, B)); // -1

vs

type t = B | A | C;
Js.log(compare(A, B)); // 1

The safest thing to do is still to manually write the compare.

#7

This was one of my concerns.

Also, I’ve tried some comparisons in rtop, and it seems like the variants with payload are always greater than the variants without it, no matter in which order they are declared.

So yeah, I’ve ended up with some manual comparisons like this one:

let compareStatuses = (x, y) =>
  switch (x.status, y.status) {
  // all the equal cases
  | (Todo, Todo)
  | (BlockedBy(_), BlockedBy(_))
  | (InProgress(_), InProgress(_))
  | (UnderReview(_), UnderReview(_))
  | (Done, Done) => 0
  // inequal cases looks somewhat error-prone,
  // but listing all the possible pairs is even more code, so...
  | (Todo, _) => (-1)
  | (_, Todo) => 1
  | (BlockedBy(_), _) => (-1)
  | (_, BlockedBy(_)) => 1
  | (InProgress(_), _) => (-1)
  | (_, InProgress(_)) => 1
  | (UnderReview(_), Done) => (-1)
  | (Done, UnderReview(_)) => 1
  };
#8

One other option is to write a rank function that turns values of your variant type into an int or float, then use that for the comparison.

This gives you less code than switching on the pair, the comparison is under your control instead of depending on the order in which you define the constructors, and you still have exhaustive checking if you add a new constructor.

let rank =
  fun
  | Todo => 0
  | BlockedBy(_) => 1
  | InProgress(_) => 2
  | UnderReview(_) => 3
  | Done => 4;

let compareStatuses = (x, y) =>
  compare(rank(x.status), rank(y.status));
#9

Hey, great trick, haven’t thought about that!