Pencarian Catatan Rekursif Tipe OCaml

Saya mencoba mencari nilai bidang secara rekursif dalam catatan yang merupakan jenis catatan rekursif.

Jenis catatan saya adalah

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

Pertama, saya mencoba melintasi variabel seperti pohon dengan tipe ini:

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;

Idenya adalah seperti ini:

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

Jadi saya mencari record yang memiliki nilai field node_name = foo_node. Cara saya melintasinya, sekadar untuk membuktikan logika saya adalah:

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

Ini mencetak:

[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

Sekarang, yang sebenarnya saya inginkan hanyalah melihat apakah ada instance di mana node_name adalah yang saya cari, jadi saya hanya ingin mengembalikan boolean.

Yang saya coba adalah (saya membuat fungsi baru hanya untuk tujuan pengujian):

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

Saya mendapatkan Kesalahan berikut pada fungsi saya, saya meneruskan ke 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 

Lalu saya mengubah blok pencocokan pola terakhir menjadi

  | 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;

Sehingga kondisi if memeriksa kembalinya pemanggilan fungsi dan meneruskannya. Sekarang saya memiliki satu kesalahan lebih sedikit tetapi saya masih memiliki kesalahan yang sama.

Pemahaman saya adalah bahwa List.iter akan meneruskan setiap elemen dari daftar yang diteruskan sebagai argumen terakhir ke fungsi yang diteruskan ke List.iter. Jadi ini harus mengulangi elemen daftar saya yang saya teruskan dan satu-satunya jalan keluar adalah jika bidang node_name cocok dengan apa yang saya cari atau jika itu adalah daftar kosong.

Perbedaan utama yang saya lihat antara kedua implementasi saya adalah implementasi pertama terus berjalan hingga semua node dievaluasi dan implementasi kedua berlangsung hingga saya menemukan apa yang saya cari.

Setiap saran akan dihargai dan jika mungkin penjelasan singkat tentang kesalahan saya atau setidaknya soroti kesalahan saya (saya merasa seperti mengambil banyak konsep pemrograman fungsional tetapi masih ada beberapa yang luput dari perhatian saya) ).