Ordered variant types 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...

Kall

I love Haskell, but I wouldn't jump ship on OCaml just for deriving sugar. Especially for a type this small. – Remunerate

also it would be nice if Num could be constrained from 1..10 – Lawlor

@Lawlor yep, someday we'll get dependent types in a mainstream language. – Kall

In Haskell you could derive Ord or write it yourself. With some constructor reordering the derived Ord would do what you want. – Murine

@Murine thank you! Will probably do that if there isn't a sensible way to do it in OCaml. – Kall

@paob: I wrote a cute little Haskell library that lets you define a type like Integer `Mod` 10 to get numbers modulo 10: hackage.haskell.org/packages/archive/modular-arithmetic/1.0.1.0/…. Another reason to use Haskell :P. – Crumpton

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.

Hailstorm

Thank you for the answer! I think I'll try writing compares for each type then. And if the code is really too bloated, I'll take a look at CamlP4. – Kall

If you are not familiar with P4 already, I warn you, you should expect a month for this :-) – Hailstorm

well, this is just a toy project without any deadline so why not = ) – Kall

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.

Forwarding

Answer 3

For the sake of completeness, there is a hacky solution for that situation.

Fortunately, while it differs from OCaml’s generic ordering, your intended ordering is still structural (lexicographic). The only difference is that you want Card (_, _) < Joker, whereas OCaml orders these two constructors the other way round. This is because constant constructors are ordered before constructors that bear a payload (indeed, the former are represented as immediate values while the latter are boxed values, i.e. pointers). OCaml otherwise preserves the declared ordering among constant constructors, and among non-constant constructors.

So a workaround is to turn Joker into a non-constant constructor, like this:

type card = Card of suit * value | Joker of unit

Then, OCaml’s generic ordering is such that Card (_, _) < Joker ().

Caveats:

• Joker becomes Joker (), you have a boxed value instead of an immediate value.
• The way OCaml orders constructors is likey not specified: although it works with current versions of OCaml (I think), it might break with future optimizations to the representation of datatypes… but such optimizations would probably require explicit code annotations.

Doykos