Странная функция на деревьях 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

Для всех целых к, функция «fold_tree слияние т к» возвращает количество красивых узлов в т со значением больше, чем к. Назовем эту гипотезу 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 (Узел (x, [son1; son2; ...])).

Есть два случая:

1. х < к, то beautifuls узлы в узле (х, [son1; son2; ...]) на значение больше, чем к точно такие красивые узлы стоимости больше k в son1, son2, ... (потому что корень не больше x).

2. х> = К, то beautifuls узлы в узле (х, [son1; son2; ...]) значения большего, чем к являются:

   • Корень (корень всегда красивые),
   • Красивые узлы в son1, son2, ... значения больше x.

Итак, induction on the size of trees, то Н (т) справедливо для всех т.

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);;