OCaml：別の表現内の表現に一致しますか？

Question

現在、OCamlを使用した小さなプロジェクトに取り組んでいます。単純な数式の単純化。式の中に特定のパターンを見つけ、それらを単純化して式の中の括弧の数を減らすようにします。これまでのところ、2つのルールを除いてほとんどのルールを実装することができました。関数。実装する必要がある2つのルールは次のとおりです。

-a-（b + c）または同様の形式のすべての式をa-b-cに変換します

-a /（b * c）または同様の形式のすべての式をa / b / cに変換します

...これはかなり単純だと思うので、一度実装したら、もう一方を簡単に実装できます。しかし、再帰的なパターンマッチング機能に問題があります。私の型式はこれです：

type expr =
 | Var of string            (* variable *)
 | Sum of expr * expr       (* sum  *)
 | Diff of expr * expr      (* difference *)
 | Prod of expr * expr      (* product *)
 | Quot of expr * expr      (* quotient *)
;;

そして、私が主に問題を抱えているのは、マッチ式です。たとえば、私は次のようなことを試みています：

let rec filter exp =   
    match exp with       
    | Var v -> Var v                        
    | Sum(e1, e2) -> Sum(e1, e2)          
    | Prod(e1, e2) -> Prod(e1, e2)
    | Diff(e1, e2) ->
        match e2 with
        | Sum(e3, e4) -> filter (diffRule e2)
        | Diff(e3, e4) -> filter (diffRule e2)      
        | _ -> filter e2         
    | Quot(e1, e2) ->                                 ***this line***
        match e2 with  
        | Quot(e3, e4) -> filter (quotRule e2)        
        | Prod(e3, e4) -> filter (quotRule e2)        
        | _ -> filter e2
;;

ただし、マークされた行の一致表現は、以前の「内部一致」の一部として認識されているようです。 ＆quot; principal match＆quot;の代わりに、すべての＆quot; Quot（...）＆quot;式は認識されません。このような他の一致式の中に一致式を持つことさえ可能ですか？そして、他の可能性を照合し続けることができるように、内部一致を終了する正しい方法は何でしょうか？

ロジックは無視します。最初に思いついたものなので、この「一致」に対処する必要があるため、試すことができなかっただけです。最初にエラーが発生しますが、再帰性またはロジックの処理方法に関する推奨事項は歓迎されます。

Answer 1

クイックソリューション

内側の一致の周りに括弧または begin / end を追加するだけです。

let rec filter exp =
    match exp with
    | Var v -> Var v
    | Sum (e1, e2) -> Sum (e1, e2)
    | Prod (e1, e2) -> Prod (e1, e2)
    | Diff (e1, e2) ->
            (match e2 with
             | Sum (e3, e4) -> filter (diffRule e2)
             | Diff (e3, e4) -> filter (diffRule e2)
             | _ -> filter e2)
    | Quot (e1, e2) ->
            (match e2 with
             | Quot (e3, e4) -> filter (quotRule e2)
             | Prod (e3, e4) -> filter (quotRule e2)
             | _ -> filter e2)
;;

簡素化

特定のケースでは、ネストされた一致は必要ありません。 より大きなパターンを使用できます。 ＆quot; | ＆quot;を使用して、ネストされたルールの重複を排除することもできます。 （＆quot; or＆quot;）パターン：

let rec filter exp =
    match exp with
    | Var v -> Var v
    | Sum (e1, e2) -> Sum (e1, e2)
    | Prod (e1, e2) -> Prod (e1, e2)
    | Diff (e1, (Sum (e3, e4) | Diff (e3, e4) as e2)) -> filter (diffRule e2)
    | Diff (e1, e2) -> filter e2
    | Quot (e1, (Quot (e3, e4) | Prod (e3, e4) as e2)) -> filter (quotRule e2)
    | Quot (e1, e2) -> filter e2
;;

未使用のパターン変数を _ （アンダースコア）に置き換えることで、さらに読みやすくすることができます。 これは、（e3、e4）タプルなどのサブパターン全体に対しても機能します：

let rec filter exp =
    match exp with
    | Var v -> Var v
    | Sum (e1, e2) -> Sum (e1, e2)
    | Prod (e1, e2) -> Prod (e1, e2)
    | Diff (_, (Sum _ | Diff _ as e2)) -> filter (diffRule e2)
    | Diff (_, e2) -> filter e2
    | Quot (_, (Quot _ | Prod _ as e2)) -> filter (quotRule e2)
    | Quot (_, e2) -> filter e2
;;

同様に、単純化を進めることができます。たとえば、最初の3つのケース（ Var 、 Sum 、 Prod ）は変更せずに返され、直接表現できます：

let rec filter exp =
    match exp with
    | Var _ | Sum _ | Prod _ as e -> e
    | Diff (_, (Sum _ | Diff _ as e2)) -> filter (diffRule e2)
    | Diff (_, e2) -> filter e2
    | Quot (_, (Quot _ | Prod _ as e2)) -> filter (quotRule e2)
    | Quot (_, e2) -> filter e2
;;

最後に、 e2 を e に置き換え、 match を function ショートカットに置き換えることができます：

let rec filter = function
    | Var _ | Sum _ | Prod _ as e -> e
    | Diff (_, (Sum _ | Diff _ as e)) -> filter (diffRule e)
    | Diff (_, e) -> filter e
    | Quot (_, (Quot _ | Prod _ as e)) -> filter (quotRule e)
    | Quot (_, e) -> filter e
;;

OCamlのパターン構文は素晴らしいですね。

Answer 2

アンダースコア、as、orパターンを賢明に使用することで、この簡潔なものを作成できます（そして、より明確に主張します）。結果のコードは、（Var、Sum、およびProdの場合に）割り当てられる量が少ないため、より効率的です。

let rec filter = function
| Var _ | Sum _ | Prod _ as e -> e
| Diff (_, (Sum _ | Diff _) as e) -> filter (diffRule e)
| Diff (_,e) -> e
| Quot (_, (Quot _| Prod _) as e) -> filter (quoteRule e)
| Quot (_,e) -> filter e
;;