我正在尝试递归搜索递归记录类型的记录中的字段值。
我的记录类型是
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 foundn" in_tree.node_name
else
(* Then evaluate the branches *)
begin
match in_tree.node_branch with
| [] ->
Format.printf "[%s] Branches: 0; End of branchn" in_tree.node_name
| head :: tail ->
Format.printf "[%s] Branches: %in" 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 foundn" 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 branchn" in_tree.node_name;
false
| head :: tail ->
Format.printf "[%s] Branches: %in" 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: %in" 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字段是否与我正在寻找的内容匹配，或者它是一个空列表。
我看到我的两个实现之间的主要区别是，第一个实现一直持续到所有节点都被评估，第二个实现一直持续到我找到我想要的东西。
任何建议将不胜感激，如果可能的话，简要解释我哪里出错了，或者至少强调我哪里出错了(我觉得我正在学习很多函数式编程概念，但仍然有一些让我无法理解)。
好吧，在最后一个分支中，如果我理解得很好，你想知道tail中的一个节点是否有好名字。在这种情况下，只需使用List.exists：
| head :: tail ->
Format.printf "[%s] Branches: %in" 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
它将按预期工作(请注意check_tree...和List.exists ...之间的||.如果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应该具有相同的类型，所以你的第二次尝试和第一次一样错误。