OCaml:在另一个内部匹配表达式？

我目前正在与OCaml合作开展一个小项目; 一个简单的数学表达式简化器.我应该在表达式中找到某些模式,并简化它们,以便表达式中的括号数减少.到目前为止,我已经能够实现大多数规则,除了两个,为此我决定创建一个递归的,模式匹配的"过滤器"函数.我需要实现的两个规则是:

- 将形式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(...)"表达式永远不会被识别.甚至可以在其他匹配表达式中包含匹配表达式吗？什么是结束内部比赛的正确方法,以便我可以继续匹配其他可能性？

忽略逻辑,因为它几乎是我首先提出的,只是因为我必须首先处理这个"匹配"错误,所以我无法尝试它,尽管有关如何处理递归的任何建议或这个逻辑会受到欢迎.

快速解决方案

你只需要在内部匹配周围添加括号或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的模式语法很好,不是吗？

你可以通过明智地使用下划线作为和/或模式来制作这个(我会更清楚).结果代码也更有效,因为它分配更少(在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
;;