Fonction bizarre sur les arbres Ocaml

Question

Un noeud est appelé beau si sa valeur est supérieure à la valeur de tout autre noeud, qui peut être trouvé sur le chemin de la racine. Le problème est de compter les beaux nœuds sur un arbre donné.

Voici une solution au problème, mais je ne peux pas comprendre l'idée derrière avoir un accumulateur de fonctions.

Quelqu'un pourrait-il expliquer cette solution?

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

Pour tout entier k, la fonction « fusion fold_tree t k » renvoie le nombre de beaux nœuds en t avec une valeur supérieure à k. Appelons cette hypothèse H (t). (Notez que si vous supposez que toutes les valeurs sont positives, alors "fold_tree merge -1" renvoie le nombre de beaux nœuds (ou "fold_tree merge 0"!)).

A partir des définitions, l'équation pseudo-code suivante est:

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

Maintenant, vous devriez être en mesure de vous convaincre que si H (son1), H (son2), ... détient alors H (Node (x, [son1; son2; ...])) tient aussi bien.

Il y a deux cas:

1. x < k, puis les nœuds beautifuls dans le nœud (x, [son1; son2; ...]) de valeur supérieure à k sont exactement les beaux nœuds de valeur supérieur à k dans son1, son2, ... (parce que la racine n'est pas plus grande que x).

2. x> = k, puis nœuds beautifuls dans le nœud (x, [son1; son2; ...]) de valeur supérieure à k sont:

   • La racine (racine sont toujours belle),
   • Les beaux nœuds de son1, son2, ... de valeur supérieure à x.

Ainsi par induction on the size of trees, il H (t) est vrai pour tout t.

Answer 2

Peut également être utile l'interprétation suivante. Je veux dire la représentation suivante du même code où explicitement est définie la fonction qui est accumulée. Cela m'a aidé à comprendre l'idée derrière la mise en œuvre.

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