如何在 OCaml 的 n 叉树中对从叶子到每个分支的根的所有元素求和？

Question

我正在尝试在 OCaml 中创建一个函数，给定一个 n 树，它 returns 是所有分支从叶到根的所有总和的列表。这就是我所做的：

exception NotFound

type 'a ntree = Tr of 'a * 'a ntree list

let leaf x = Tr (x, [])

let alb = 
  Tr (1, [Tr (2, [leaf 3; leaf 4; leaf 2]); 
          Tr (5, [leaf 11; leaf 10]); 
          Tr (3, [leaf 9; leaf 7; leaf 10])])

let rec peso (Tr (x, tlist)) =
  match tlist with
    [] -> [x]
  | _ -> [x + peso_l tlist]
and peso_l = function 
    [] -> raise NotFound
  | [t] -> peso t
  | t::rest -> peso t :: peso_l rest

但这行不通，因为，我认为，

| _ ->[x + peso_l tlist]

returns 类似于 [x+ [t]]（我说得对吗？）。我该如何解决？

Answer 1

当您编写 [x + peso_l tlist] 时，您要做的是将 x 添加到 peso_l tlist 返回的列表的每个元素中。这可以通过 List.map:

来实现

exception NotFound

type 'a ntree = Tr of 'a * 'a ntree list

let leaf x = Tr (x, [])

let alb =
  Tr
    ( 1,
      [
        Tr (2, [ leaf 3; leaf 4; leaf 2 ]);
        Tr (5, [ leaf 11; leaf 10 ]);
        Tr (3, [ leaf 9; leaf 7; leaf 10 ]);
      ] )

let rec peso (Tr (x, tlist)) =
  match tlist with [] -> [ x ] | _ -> List.map (( + ) x) (peso_l tlist)
and peso_l = function
  | [] -> raise NotFound
  | [ t ] -> peso t
  | t :: rest -> peso t @ peso_l rest

let () =
  Format.printf "@[<v 0>%a@."
    Format.(
      pp_print_list ~pp_sep:pp_print_cut (fun ppf d ->
          Format.fprintf ppf "%d" d))
    (peso alb)

如何在 OCaml 的 n 叉树中对从叶子到每个分支的根的所有元素求和？

How do I sum all the elements from the leaf to the root of each branch in a n-ary tree in OCaml?

tree

ocaml

n-ary-tree