如何在 OCaml 中使用 fold 编写 contains_var 函数？

Question

我有以下 fold_expr 函数，它递归地折叠任意表达式，包括浮点数、变量、二元运算符和否定。

let rec fold_expr (e : expression) (f: float -> 'a) (v: 'a) (b: binop -> 'a -> 'a -> 'a)  (n: 'a -> 'a)

现在我正在尝试实现一个名为 contains_var 的函数，如果表达式有变量则 returns 为真，否则为假。我知道 contains_var 可以这样递归实现：

let rec contains_var (e:expression) : bool =
  match e with
  | Num _ -> false
  | Var -> true
  | Neg _ -> false
  | Binop (_, e1, e2) -> contains_var e1 || contains_var e2
;;

我尝试按如下方式实现它：

let contains_var (e:expression) : bool =
        let Num _ = false in
        let Var = true in
        let Binop bin, l, r = l || r in
        let Neg _ = false
                fold_expr e _ Var bin _

显然我在编译时遇到了问题，而且我确信我遗漏了一些东西。任何帮助表示赞赏！ :)

Answer 1

折叠可以看作是一种重新解释构造函数的方式。对于定义为

的列表

type 'a l =
  | Nil
  | Cons of 'a * 'a l

fold(right)函数可以写成

let rec fold ~nil ~cons = function
| Nil -> nil
| Cons (x,l) -> cons x (fold ~cons ~nil l)

从这点来说，写一个深度恒等式函数可以通过重写构造器为函数来完成：

let deep_identity l = fold ~nil:Nil ~cons:(fun x l -> Cons (x,l))

类似地，一个（重言式）函数contains_nil可以写成

let contains_nil = fold ~nil:true ~cons:(fun _ contains_nil -> contains_nil)

fold_expr 函数只是稍微复杂一点的版本，它将 Var、Num、Binop 和 Neg 的函数版本作为一个论点。因此，要编写 contains_var 函数，您需要：

定义正确的 var、num、binop 和 neg 函数
使用上面定义的函数调用 fold_expr。

注意函数名和变量名不能以大写字母开头；并且您不能使用 _ 作为函数应用程序的参数。

Answer 2

从 fold_expr 的外观来看，这个函数似乎做了以下事情：

val fold_expr (e : expression) (f: float -> 'a) (v: 'a) (b: binop -> 'a -> 'a -> 'a)  (n: 'a -> 'a)

fold_expr e f v b n:

如果 e 是 Num n，f 应用到 n，
returns v 如果 e 是 Var,

e

Binop (bop, e1, e2)

将 b 应用于 bop、fold_epxr e1 和 fold_expr e2
如果 e 是 Neg e1

n

e1

你所要做的就是将与你的问题相对应的值提供给fold_expr。在这种情况下，函数 return false 除了 Var 和 Binop

解决方案可能如下所示：

let contains_var e = fold_expr e (fun _ -> false) true what_is_b (fun _ -> false)

我可以给你 what_is_b 但我认为这是你需要自己找到的主要问题所以我会留给你。

如何在 OCaml 中使用 fold 编写 contains_var 函数？

How can I write a contains_var functon using fold on OCaml?

ocaml

expression