表达式和子表达式 Ocaml

Question

我要问一些我不清楚的问题，所以我会尽我所能...

如何检查一个表达式是否是另一个表达式的子表达式？

例如，这里：

type expr =
 Int of int
 | Var of string
 | Sum of expr * expr
 | Diff of expr * expr
 | Mult of expr * expr
 | Div of expr * expr

如果我有一个表达式（在上述表达式之间选择），我如何识别它是否是列表中另一个表达式的子表达式？

你能给我一些真实的代码吗？因为看了网上的一些东西，想写点什么，但是真的不知道该写什么。

Answer 1

正如@jeffreysco 提到的，它是树结构的递归。

具体来说，如果 e1 是您想查看是否可以在其中找到 e2 的“大”表达式：

首先检查 e1 是否等于 e2
否则在 e1 上进行模式匹配并在 Sum Diff Mult Div

let rec is_subexp e1 e2 =
  if e1 = e2 then true
  else match e1 with
  | Int _ | Var _ -> false
  | Sum(e3,e4) -> is_subexp e3 e2 || is_subexp e4 e2
  ...

表达式和子表达式 Ocaml

Expressions and subexpressions Ocaml

ocaml

functional-programming