题
我目前正在与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
;;
最后,您可以用 e
替换 e2
,并将 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
;;