ocaml 的二进制参考树查找

Question

type exp = V of var
           | P of var * exp
and var = string

我正在构建一个二叉引用树，其中右叶节点查找左叶节点上的叶节点，并且 returns 如果所有右叶节点都与一些左叶节点匹配则为真。

let rec ctree : exp * exp -> bool
=fun (e1,e2) -> match e2 with
  | P (x,y) -> match y with
    | P (a,b) -> if (ctree(a,b)) then true else ctree(x,b)
    | V a -> if a=x then true else ctree(e1,y)
  | V x -> e1=x

但在这里，我在第 5 行不断收到错误消息：

| V a -> if a=x then true else ctree(e1,y)

这里的e1是exp类型，应该是这样的，但是编译器一直告诉我应该是var=string类型。另外，对于第 6 行，

V x -> e1=x

它告诉我应该再次输入 var=string 而不是 e1。

谁能告诉我为什么会出现错误？

Answer 1

当您有两个嵌套的 match 表达式时，不清楚嵌套的结束位置。您需要在内部匹配项周围使用括号。这样的事情可能会奏效：

let rec ctree : exp * exp -> bool =
    fun (e1,e2) -> match e2 with
    | P (x,y) ->
        (match y with
        | P (a,b) -> if (ctree(a,b)) then true else ctree(x,b)
        | V a -> if a=x then true else ctree(e1,y)
        )
    | V x -> e1=x

其次，您的函数类型是 exp * exp -> bool，表示 e1 的类型是 exp。在函数的末尾你有这个：

| V x -> e1 = x

由于 x 是 V 构造函数的值，因此它必须是一个字符串。但是 e1 = x 仅当 e1 也是一个字符串时才有意义。

因此，您对 e1 的使用存在类型冲突。

ocaml 的二进制参考树查找

binary reference tree lookup for ocaml

binary-tree

ocaml