Ordered variant types and subtypes in OCaml

Question

I'm currently trying to do some mahjong hand processing in OCaml and straight from the beginning I'm confronted with something that bugs me.

I'll give you examples based on cards because I don't want to confuse anyone with mahjong terminology.

Just like in this part on User-Defined Types from OCaml for the Skeptical, I want to use variant types to describe suits, cards, and everything.

type suit = Club | Diamond |  Heart | Spade
type value = Jack | Queen | King | Ace | Num of int
type card = Card of suit * value | Joker
type hand = card list

And it would be really nice if I could write a smart compare function that would understand ordered variant types.

Ideally I'd write something like that:

type suit = Club < Diamond <  Heart < Spade
type value = Num of int < Jack < Queen < King < Ace
type card = Card of suit * value < Joker
type hand = card list

So that when I do

List.sort Pervasives.compare [Card(Diamond, Num 3); Joker; Card(Spade, Ace); Card(Diamond, Num 2)]

it gives me

[Card(Diamond, Num 2); Card(Diamond, Num 3); Card(Spade, Ace); Joker]

Alas, the ocaml toplevel returns

[Joker; Card(Spade, Ace); Card(Diamond, Num 2); Card(Diamond, Num 3)]

(which is already quite good!)

Basically I want a compare function that would take hints from the type declaration structure.

I've read this article on polymorphic compare and this similar question but I'm not sure I want to depend on compare_val.

Do I really have to write my own compare function? If you recommend me to write one, do you have tips on the way it should be written, especially to reduce the number of cases?

P.S.: I just heard about deriving(Ord) in Haskell... Might be enough for me to take the leap...

Answer 1

Yes you have to. But you can skip where the polymorphic comparison matches with your need. For example, you do not need write your comparison for suit.

Haskell's deriving(Ord) is as same as the polymorphic comparison: if you can order constructors in the ordering in your mind, then you can derive the comparison function. But it is more powerful since you can compose automatic and custom comparison functions. OCaml's polymorphic comparison cannot do this. For example,

type t = ...
let compare_t = .... (* custom comparison for t *)
type t2 = A of t | B of t | C of t (* I want to write a comparion for t2 now! *)

If the polymorphic comparison order of the constructor A, B and C matches with your need, you cannot use it for comparison of t2, since it cannot call the custom comparison for t. So in this case, if I were you I would write compare_t2 by hand. For your example of cards too, it is easily done in 3 mins.

If your data types are huge and it is extreme pain to write down all the comparison by your hand, you can auto-generate the comparison functions from the type definition using CamlP4 and type_conv, just like deriving(Ord) does. But I am afraid there is no type_conv module which provides Ord like thing yet. Personally I have never felt a need to have it. It should be a nice exercise for P4 learners.

Answer 2

I'm 7 years late, but you can achieve this using ppx_deriving:

type value = Num of int | Jack | Queen | King | Ace [@@deriving ord]
type suit = Club | Diamond | Heart | Spade [@@deriving ord]
type card = Card of suit * value | Joker [@@deriving ord]
type hand = card list

Use ocamlfind ocamlopt -o executable.out -linkpkg -package ppx_deriving.ord file.ml to link the package.