52

私は現在、OCaml を使用した小さなプロジェクトに取り組んでいます。単純な数式の簡略化。式の中に特定のパターンを見つけて、それらを単純化して、式内の括弧の数を減らすことになっています。これまでのところ、再帰的なパターン マッチングの「フィルター」関数を作成することにした 2 つのルールを除いて、ほとんどのルールを実装できました。実装する必要がある 2 つのルールは次のとおりです。

- a - (b + c) または類似の形式のすべての表現を a - b - c に変換します。

- a / (b * c) または類似の形式のすべての式を a / b / c に変換します。

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

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(...)」式が認識されることはありません。このような他の一致式の中に一致式を含めることさえ可能ですか? そして、他の可能性とのマッチングを続けることができるように、内側のマッチングを終了する正しい方法は何でしょうか?

ロジックは無視してください。これはほとんど私が最初に思いついたものです。再帰性またはロジックは大歓迎です。

4

2 に答える 2

84

クイックソリューション

内側の一致の前後に括弧または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)
;;

簡略化

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

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て置き換えることができます。ematchfunction

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のパターン構文はいいですね。

于 2008-11-03T00:14:55.530 に答える
9

アンダースコア、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
;;
于 2008-11-05T00:58:58.980 に答える