ocaml 类型初学者

Question

这可能是一个简单的问题，但我不确定为什么会出现此错误：

我在文件中定义了一个类型

type tree = TreeNode of string * tree list;;

我在另一个文件中有这个函数定义 [编辑添加的 getFt 和 getSt 函数]

let getFt input = match input with
                    | (x, y) -> x;;

let getSt input = match input with
                        | (x, y) -> y;;
let rec traverse input = 
            match (getFt(input)) with
            | "S" -> nodeS (getSt(input))
            | "T" -> nodeT (getSt(input))
    and traverseList input =
            match (getFt(List.hd(input))) with
            | "S" -> nodeS (List.tl(input))
            | "T" -> nodeT (List.tl(input))
    and nodeS input =
            match (getFt(List.hd(input))) with
            | "TRUE" -> (TreeNode("TRUE", []))
            | "FALSE" -> (TreeNode("FALSE", []))
            | "(" -> (traverseList (List.tl(input)))
            | x -> (TreeNode(x, []))
    and nodeT input =
            match (getFt(List.hd(input))) with
            | "not" -> (TreeNode("not", [(nodeS (List.tl(input)))]))
            | "and" -> (TreeNode("and", [(traverseList (List.tl(input)) )]))
            | "or" ->  (TreeNode("or", []));;

let buildAbstractSyntaxTree (input : tree) : tree = traverse input;;

我每次编译都会收到这个错误： [编辑我输入错误的错误]

Error: This expression has type Proj2_types.tree
   but an expression was expected of type string * (string * 'a) list

Answer 1

我像这样重新定义了你的错误函数：

let getFt (TreeNode (x, _)) = x

let getSt (TreeNode (_, x)) = x

此更改后，您的 traverse 函数将为我编译。但是如果树没有你匹配的特定字符串，仍然会出现问题。

换句话说，您的匹配并不详尽。这使得代码有点脆弱。

Answer 2

此答案的目的不是要取代 Jeffrey 的答案，而是为您提供一些有关进一步的 OCaml 代码的提示。

TL; DR：字符串“不好”

如果我没看错你的代码，你的树是一对包裹的Treenode of string * tree list（它看起来不像一棵树，更像是一条路径，因为你没有左分支和右分支，您有一个节点后跟任何内容或另一个节点等。实际上您只是定义了一个列表 ;-))

您从 traverse 开始匹配它。

traverse 看对的第一部分是字符串 "S" 还是字符串 "T" 所以让我们重写它：

let rec traverse = function
  | Treenode ("S", t) -> nodeS t
  | Treenode ("T", t) -> nodeT t

nodeS 是做什么的？它匹配列表头部的第一部分，并检查它是 "TRUE"、"FALSE"、"(" 还是其他任何内容。如果它是前两个它只是创建一个新的 TreeNode，它是它遍历剩余列表的括号，如果是其他任何东西它只是创建一个新的 TreeNode。所以你有 3 个案例，它们做的事情完全相同，但你为每个案例都做了一个案例。让我们重写它：

and nodeS = function
  | [] -> failwith "TODO"
  | ("(", _) :: tl -> traverseList tl
  | (x, _) :: _ -> TreeNode (x, [])

至于 nodeT，我们希望找到 "and"、"or" 或 "not"，这给了我们：

and nodeT = function
  | [] -> failwith "TODO"
  | ("not", _) :: tl -> TreeNode("not", [nodeS tl])
  | ("and", _) :: tl -> TreeNode("and", [traverseList tl])
  | ("or", _) :: tl -> TreeNode("or", [])

最后，遍历列表：

and traverseList = function
  | [] -> failwith "TODO"
  | ("S", _) :: tl -> nodeS tl
  | ("T", _) :: tl -> nodeT tl

问题出现了。首先，您不处理空列表（我的 `failwith "TODO"），但最重要的是，您操作字符串，那么如果您将“A”作为第一个字符串会发生什么？从你构建树的方式来看可能是不可能的，但它没有按类型显示。这就是求和类型来帮助你的地方。尝试像这样重新定义你的树：

type node = S | T | True | False | Par | Not | And | Or 
type tree = TreeNode of node * tree list

看看它会把你引向何方。 OCaml 非常强调由类型引导的风格。字符串对文本很有用，但对类型没有用（想象一下，如果你开始在你的 AST 中添加自定义函数，你会匹配“myfun of int -> int -> string”吗？听起来很乏味，你不同意吗？）

我希望您能阅读我的代码（和 Jeffrey 的代码）并了解 OCaml 中模式匹配的强大功能，这意味着您不必使用 getFt 和 getSt 函数。如果您有任何问题，请随时发表评论，这里的人很乐意提供帮助 ;-)

ocaml 类型初学者

Beginner with ocaml types

ocaml