代数データ型のパターンマッチング

Question

これは未解決の質問ですが、私を満足させる解決策を見つけることは決してできませんでした。

のは、私は、この代数的データ型を持っているとしましょう：

今

type t = A of int | B of float | C of string 

、のは、私はcompare機能を書きたいとしましょう - 私は例えば、Mapで私の値を置きたいので - 私が書きたいです

let compare t1 t2 = 
    match t1, t2 with 
    | A x, A y -> compare x y 
    | A _, _ -> -1 
    | _, A _ -> 1 
    | B x, B y -> compare x y 
    | B _, _ -> -1 
    | _, B _ -> 1 
    | C x, C y (* or _ *) -> compare x y 

それとも私はこのようにそれを書くことができます：それはこれを好き

let compare t1 t2 = 
    match t1, t2 with 
    | A x, A y -> compare x y 
    | B y, B x -> compare x y 
    | C x, C y -> compare x y 
    | A _, _ 
    | B _, C _ -> -1 
    | _ -> 1 

私が間違っていない場合、nがコンストラクタの数であると言うと、最初のcompareは3 * (n - 1) + 1のケースを持ち、2番目のものはn + ((n - 2) * (n - 1))/2 + 2のケースを持ちます。

これは非常に不満足であるので：

• n = 3（我々の場合）：7または6例
• n = 4：10または8例
• n = 5：13または13例

それはかなり速く成長する。

私はそうやっているのですか他の方法を使用していますか？

または、より良い、

let compare t1 t2 = 
    match t1, t2 with 
    | c1 x, c2 y -> 
     let c = compare c1 c2 in 
     if c = 0 then compare x y else c 

など何かをする可能性があるので、

let compare (c1 x) (c2 y) = 
    let c = compare c1 c2 in 
    if c = 0 then compare x y else c 

編集：追加した2つのコンストラクタはセニョールDrup（from Guadalup用等しいかどうかを比較します。 -P）

Answer 1

いくつかの選択肢があります。 （それは明らかに実装依存であるが）まず、あなたは直接の表現を比較するObjモジュールを使用することができます。

type t = A of int | B of float | C of string 

let compare_t a b = 
    match (a, b) with 
    | A x, A y -> compare x y 
    | B x, B y -> compare x y 
    | C x, C y -> compare x y 
    | _ -> compare (Obj.tag (Obj.repr a)) (Obj.tag (Obj.repr b)) 

あなたはそれがよりポータブルになりたい場合は、あなたが書いた（または生成）することができます与える関数をあなたは数字のタグです。その結果、現在のOCamlコンパイラはそれを探しているようで、基になる関数呼び出しを逃すことができるようです。

let tag_of_t = function 
    | A _ -> 0 
    | B _ -> 1 
    | C _ -> 2 

let compare_t a b = 
    match (a, b) with 
    | A x, A y -> compare x y 
    | B x, B y -> compare x y 
    | C x, C y -> compare x y 
    | _ -> compare (tag_of_t a) (tag_of_t b) 

あなたはまだ線形成長に対処しなければならず、二次成長ではありません。

Answer 2

ppx_derivingを使用してこの関数を生成できます。

以下は正しいことをやっ機能compare : t -> t -> int作成されます：あなたが興味がある、またはppx_derivingを使用できない場合

type t = A of int | B of float | C of string [@@deriving ord] 

を、ここライマーのソリューションとして、同様の戦略を使用して生成されたコードは、あります。

% utop -require ppx_deriving.std -dsource 
utop # type t = A of int | B of float | C of string [@@deriving ord];; 
type t = | A of int | B of float | C of string [@@deriving ord] 
let rec (compare : t -> t -> Ppx_deriving_runtime.int) = 
    ((let open! Ppx_deriving_runtime in 
     fun lhs -> 
     fun rhs -> 
      match (lhs, rhs) with 
      | (A lhs0,A rhs0) -> Pervasives.compare lhs0 rhs0 
      | (B lhs0,B rhs0) -> Pervasives.compare lhs0 rhs0 
      | (C lhs0,C rhs0) -> Pervasives.compare lhs0 rhs0 
      | _ -> 
       let to_int = function 
       | A _ -> 0 
       | B _ -> 1 
       | C _ -> 2 
       in 
       Pervasives.compare (to_int lhs) (to_int rhs)) 
    [@ocaml.warning "-A"]) ;; 
type t = A of int | B of float | C of string 
val compare : t -> t -> int = <fun> 

Answer 3

場合、あなただけが比較ビルトインを使用することができ、あなたが特定の順序を気にしない、すなわち、Map.Make数子を使用するために比較する必要があります。いくつかの場合

let compare t1 t2 = compare t1 t2 

、すべてではなく、あなたの例は、組み込みのためのスコープの外にある、あなたは、（例えば、彼らは、関数型である）を比較：特にそれはあなたの例では、指定されたタイプのために働きますO（1）のコードサイズで残りのケースを扱うことができます。例：

type t = A of int -> int | B of float | C of string 

let compare t1 t2 = match t1,t2 with 
| A f1, A f2 -> ... 
| A _, _ -> -1 
| _, A _ -> 1 
| _, _ -> compare t1 t2 

それが失敗したすべては、自動的に比較するそれ以外の場合は長めを作成する（camlp5経由など）のメタプログラミングを行うためのオプションがまだある場合。私はこれを過去に行っています。

type three = Zero | One | Two 

指定されていない（Pervasives.compareのみ一部全順序に指定された）、私は自然の秩序を望んでいました。