搜索遞歸記錄類型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應該有相同的類型，所以你的第二次嘗試是錯誤的第一次。 ;-)