Ocaml 树上的奇怪函数

Question

如果一个节点的值大于可以在通往根的路上找到的任何其他节点的值，则该节点被称为美丽的。问题是计算给定树上的漂亮节点。

这是问题的解决方案，但我无法理解函数累加器背后的想法。

有人能解释一下这个解决方案吗？

open List;;

type 'a tree = Node of 'a * 'a tree list

let rec fold_tree f (Node (x, l)) =
  f x (map (fold_tree f) l);;

let beautiful_nodes t  =
  let merge x l k =
    if x < k then 
      fold_left (fun a h ->a + h k) 0 l
    else
      fold_left (fun a h ->a + h x) 0 l + 1
  in
  fold_tree merge t (-1);;

Answer 1

对于所有整数k，函数“fold_tree merge t k”返回t中值大于k的漂亮节点的数量。我们称这个假设为 H(t)。

（请注意，如果您假设所有值都是正数，则“fold_tree merge -1”返回美丽节点的数量（或“fold_tree merge 0”！））。

根据定义，以下伪代码方程成立：

fold_tree merge (Node (x, [son1; son2; ...])) k = 
  if x < k then 
    sum ([fold_tree merge son1 k; fold_tree merge son2 k; ...]))
  else
    1 + sum ([fold_tree merge son1 x; fold_tree merge son2 x; ...]))

现在你应该能够说服自己，如果 H(son1), H(son2), ... 成立，那么 H(Node(x, [son1; son2; ...])) 也成立。

有两种情况：

1. ×< k, then the beautifuls nodes in Node(x, [son1; son2; ...]) of value greater than k are exactly the beautiful nodes of value greater than k in son1, son2, ... (because the root is not greater than x).

2. x >= k，则 Node(x, [son1; son2; ...]) 中值大于 k 的美丽节点为：

   • 根（根总是美丽的），
   • son1,son2,...中值大于x的美丽节点。

因此，通过对树的大小进行归纳，H(t) 对于所有 t 都成立。

Answer 2

以下解释可能也有用。我的意思是相同代码的以下表示，其中显式定义了累积的函数。 它帮助我理解了实施背后的想法。

let beautiful_nodes tree = 
   let merge x l = (fun k ->
    if (x>k) then
        1+ fold_left (fun acc h -> acc+ h x) 0 l
    else
        fold_left (fun acc h  -> acc + h k) 0 l
                    ) 
    in  fold_tree merge tree (-1);;