OCaml：匹配另一个表达式中的表达式？

Question

我目前正在使用 OCaml 开发一个小项目； 一个简单的数学表达式简化器。 我应该在表达式中找到某些模式，并简化它们，以便减少表达式中括号的数量。 到目前为止，我已经能够实现除两条规则之外的大多数规则，我决定为此创建一个递归的模式匹配“过滤器”函数。 我需要实现的两个规则是： -

将 a - (b + c) 或类似形式的所有表达式转换为 a - b - c -

将 a / (b * c) 或类似形式的所有表达式转换为 / 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(. ..)" 表达式永远不会被识别。 是否有可能像这样在其他匹配表达式中包含匹配表达式？ 结束内部匹配以便我可以继续匹配其他可能性的正确方法是什么？

忽略逻辑，因为这几乎是我首先想到的，只是我无法尝试它，因为我必须首先处理这个“匹配”错误，尽管有任何关于如何处理递归性的建议或这种逻辑将受到欢迎。

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)
;;

简化

您只需在 特殊情况下不需要嵌套匹配。
您可以使用更大的图案。 您还可以使用“|”（“或”）模式消除嵌套规则中的重复：

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
;;

以同样的方式，您可以继续简化。 例如前三种情况（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
;;