OCaml遍历嵌套递归记录/字典按字段分类统计键出现次数

DevOps 小满

2026-8-29

解法说明

你的someType是递归定义的树状结构，处理未知深度的嵌套递归结构不需要手动写多层循环，直接编写递归遍历函数即可自动覆盖所有层级的节点。

核心逻辑：

每遍历到一个节点，就根据它的c字段值给对应分类计数加1（每个节点必然对应一个a字段，因此每访问一个节点就完成一次a字段计数）
遍历当前节点d字段存储的所有子节点，递归对每个子节点执行计数，将结果逐层累加
当节点的d字段为空数组时，没有更深的子节点，递归自然终止

实现代码

type other = A | B
type someType = {a:string ; b:string ; c:other ; d:someType array}

let count_c (root: someType) : int * int =
  let rec traverse node =
    (* 统计当前节点的计数 *)
    let base_count = match node.c with
      | A -> (1, 0)
      | B -> (0, 1)
    in
    (* 累加所有子节点的计数结果 *)
    Array.fold_left (fun (a_acc, b_acc) child ->
      let child_a, child_b = traverse child in
      (a_acc + child_a, b_acc + child_b)
    ) base_count node.d
  in
  traverse root

测试验证

使用提供的测试用例运行：

let test = 
  {a = "a"; b = "b"; c = B;
   d =
    [|{a = "aa"; b = "bb"; c = A;
       d =
        [|{a = "aaa"; b = "bbb"; c = A;
           d =
            [|{a = "aaaa"; b = "bbbb"; c = A; d = [||]};
              {a = "aaaaa"; b = "bbbbb"; c = B; d = [||]}|]}|]}|]}

let () =
  let result = count_c test in
  Printf.printf "统计结果: (%d, %d)\n" (fst result) (snd result)

运行后会输出统计结果: (3, 2)，和预期结果完全一致。