树上的奇怪函数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 tk "返回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)，…hold then H(Node(x， [son1;son2;…))也成立。

有两种情况:

1. x & lt;k，那么Node(x， [son1;son2;[])的值大于k的恰好是son1, son2，…中值大于k的漂亮节点(因为根目录不大于x)。

2. x>= k，然后在Node(x， [son1;son2;[…])值大于k的是:

   • 根(根总是美丽的)，
   • son1, son2，…中的beautifulnodes

通过归纳树的大小，如果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);;