Упорядоченные типы вариантов и подтипы в OCaml

Question

В настоящее время я пытаюсь выполнить обработку маджонга в OCaml, и прямо с самого начала я сталкиваюсь с чем-то, что меня задевает.

Я приведу примеры, основанные на карточках, потому что я не хочу путать кого-либо с терминологией маджонга.

Как и в этом part on User-Defined Types from OCaml for the Skeptical, я хочу использовать варианты типов для описания костюмов, карточек и всего прочего.

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 

И было бы очень хорошо, если бы я мог написать умный compare функцию, которая будет понимать упорядоченную вариантные типы.

В идеале я бы написать что-то вроде этого:

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 

Так что, когда я

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

это дает мне

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

Увы, OCaml возвращает верхнего уровня

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

(что уже неплохо!)

В основном я хочу compare функцию, которая будет принимать подсказки от структуры объявления типа.

Я читал это article on polymorphic compare и this similar question, но я не уверен, что хочу зависеть от compare_val.

Должен ли я действительно написать свою собственную функцию сравнения? Если вы рекомендуете мне написать один, у вас есть советы по тому, как это должно быть написано, особенно для уменьшения числа случаев?

P.S .: Я только слышал о deriving(Ord) в Haskell ... Может быть достаточно для меня, чтобы совершить прыжок ...

Answer 1

Да, вы должны. Но вы можете пропустить, где полиморфное сравнение соответствует вашим потребностям. Например, вам не нужно писать свое сравнение для костюма.

Вывод Haskell (Ord) такой же, как полиморфное сравнение: если вы можете заказать конструкторы в упорядочении в своем уме, то вы можете получить функцию сравнения. Но он более мощный, поскольку вы можете создавать автоматические и пользовательские функции сравнения. Полиморфное сравнение OCaml не может этого сделать. Например,

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! *) 

Если полиморфный порядок сравнения конструктора A, B и C совпадают с вашими потребностями, вы не можете использовать его для сравнения t2, поскольку он не может вызвать пользовательское сравнение для т. Поэтому в этом случае, если бы я был вами, я бы написал compare_t2 вручную. Для вашего примера карт тоже, это легко сделать за 3 минуты.

Если ваши типы данных огромны, и вам крайне сложно записать все сравнения вашей рукой, вы можете автоматически генерировать функции сравнения из определения типа с помощью CamlP4 и type_conv, как это делает вывод (Ord). Но я боюсь, что нет модуля type_conv, который покажет Ord. Лично я никогда не чувствовал необходимости иметь его.Это должно быть хорошим упражнением для учеников P4.