搜索递归记录类型OCaml

Question

我想在递归记录类型的记录中递归搜索字段值。

我的记录类型是

type node = {node_name:string; node_branch:node list} 

首先，我想只是遍历树像这种类型的变量：

let tree = {node_name="trunk"; node_branch=[{node_name="branch1L:1"; node_branch=[{node_name="branch2L:1"; node_branch=[]}; 
                        {node_name="foo_node"; node_branch=[]};];}; 
              {node_name="branch1L:2"; node_branch=[]}];} 
    in 
    let target = "foo_node" in 
    print_newline(); 
    search_tree_for_name target tree; 

的想法是，它是一种像这样：

    trunk 
      __________|_________ 
      |     | 
     branch1L:1   branch1L:2 
    ______|_______ 
    |    | 
branch2:1  foo_node 

所以我正在寻找一个字段值为node_name = foo_node的记录。我走过的方式，只是为了证明我的逻辑是：

let rec search_tree_for_name target_name in_tree = 
    if in_tree.node_name = target_name then 
    (* First check the node_name *) 
     Format.printf "[%s] Target node_name found\n" in_tree.node_name 
    else 
    (* Then evaluate the branches *) 
    begin 
     match in_tree.node_branch with 
     | [] -> 
     Format.printf "[%s] Branches: 0; End of branch\n" in_tree.node_name 
     | head :: tail -> 
     Format.printf "[%s] Branches: %i\n" in_tree.node_name (List.length in_tree.node_branch); 
     search_tree_for_name target_name head; 
     List.iter (search_tree_for_name target_name) tail; 
    end 

这会打印出：

[trunk] Branches: 2 
[branch1L:1] Branches: 2 
[branch2L:1] Branches: 0; End of branch 
[foo_node] Target node_name found 
[branch1L:2] Branches: 0; End of branch 

现在，我真正想要的是只是看一个实例存在，其中node_name是我在找什么，所以我只想返回一个布尔值。

我试过了（我创建只是用于测试的新功能）：

let rec check_tree_for_name target_name in_tree = 
    if in_tree.node_name = target_name then 
    begin 
    (* First check the node_name *) 
     Format.printf "[%s] Target node_name found\n" in_tree.node_name; 
     true 
    end 
    else 
    (* Then evaluate the branches *) 
    begin 
     match in_tree.node_branch with 
     | [] -> 
     Format.printf "[%s] Branches: 0; End of branch\n" in_tree.node_name; 
     false 
     | head :: tail -> 
     Format.printf "[%s] Branches: %i\n" in_tree.node_name (List.length in_tree.node_branch); 
     check_tree_for_name target_name head; 
     List.iter (check_tree_for_name target_name) tail; 
    end 

我让我的函数如下错误我传递给List.iter：

Error: This expression has type node -> bool 
     but an expression was expected of type node -> unit 
     Type bool is not compatible with type unit 

然后我将最后一个模式匹配块更改为

| head :: tail -> 
    Format.printf "[%s] Branches: %i\n" in_tree.node_name (List.length in_tree.node_branch); 
    if check_tree_for_name target_name head then true 
    else List.iter (check_tree_for_name target_name) tail; 

因此if条件检查函数调用的返回值以及传递它的种类。现在我有一个更少的错误，但我仍然有同样的错误。

我的理解是，List.iter会传递传递列表的每个元素作为传递给List.iter的函数的最后一个参数。所以这应该遍历我传递给它的列表中的元素，并且唯一的出路是如果node_name字段与我正在查找的字段匹配，或者它是空列表。

我在两个实现之间看到的主要区别是第一个继续进行，直到所有节点都被评估，第二个实现继续下去，直到找到我要找的东西。

任何建议，将不胜感激，如果可能的话，一个简短的解释，我哪里出错或至少强调我要去哪里错了（我觉得我拿起很多功能编程概念，但仍然有一些这是逃避我）。

Answer 1

那么，在最后一个分支中，如果我理解的很好，您想知道tail中的其中一个节点是否具有良好的名称。在这种情况下，只要使用List.exists：

| head :: tail -> 
     Format.printf "[%s] Branches: %i\n" in_tree.node_name 
      (List.length in_tree.node_branch); 
     check_tree_for_name target_name head || 
     List.exists (check_tree_for_name target_name) tail 

正如预期的（注意和List.exists ...的||之间check_tree...它会工作如果check_tree ...回报true，你并不需要检查列表的其余部分。

---

小的解释：

在OCaml中，模式匹配的所有分支必须具有相同的类型。在这里，你的第一个分支有一个boolean类型，因为你用false结束了它，第二个分支有unit类型，因为你用List.iter ...结束了它。 List.iter的类型为('a -> unit) -> 'a list -> unit，并将其第一个参数应用于作为第二个参数给出的列表中的所有元素。 List.exists类型为('a -> bool) -> 'a list -> bool，如果列表中的某个元素作为第二个参数满足作为第一个参数给出的谓词，并且返回true，并且如果不存在这样的元素，则返回false。

等效地，if cond then e1 else e2就像一个模式匹配，所以e1和e2应该有相同的类型，所以你的第二次尝试是错误的第一次。 ;-)