树 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" returns t中值大于k的美丽节点的数量。我们称这个假设为 H(t).

（请注意，如果您假设所有值为正，则 "fold_tree merge -1" returns 美丽节点的数量（或 "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; ...])) 也成立.

有两种情况：

x < k，则Node(x, [son1; son2; ...])中大于k的美丽节点恰好是son1, son2, ..中大于k的美丽节点.（因为根不大于 x）。
x >= k，则Node(x, [son1; son2; ...])中值大于k的节点为：
- 根（根总是美丽的），
- son1、son2、...中值大于x的beautifuls节点。

所以根据induction on the size of trees，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);;

树 Ocaml 上的奇怪函数

Weird function on trees Ocaml

algorithm

tree

functional-programming

ocaml

fold