fold_tree en OCaml

Question

Comme vous le savez, il y a des fonctions d'ordre supérieur dans OCaml, comme fold_left, fold_right, filtrer, etc.

Sur mon cours de programmation fonctionnelle avait été fonction introduite le nom fold_tree, ce qui est quelque chose comme fold_left/right, pas sur les listes, mais sur les arbres (binaires). Il ressemble à ceci:

let rec fold_tree f a t = 
    match t with 
    Leaf -> a | 
    Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);; 

Où arbre est défini comme:

type 'a tree = 
    Node of 'a tree * 'a * 'a tree | 
    Leaf;; 

OK, voici ma question: comment fonctionne la fonction fold_tree? Pourriez-vous me donner quelques exemples et expliquer en langage humain?

Answer 1

Voici une suggestion de style, placez les barres au début de la ligne. Cela rend plus clair le cas où une affaire commence. Par souci de cohérence, la première barre est facultative mais recommandée.

type 'a tree = 
    | Node of 'a tree * 'a * 'a tree 
    | Leaf;; 

let rec fold_tree f a t = 
    match t with 
     | Leaf -> a 
     | Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);; 

---

En ce qui concerne la façon dont cela fonctionne, tenez compte de l'arbre suivant:

let t = Node(Leaf, 5, Node(Leaf, 2, Leaf));; 

Avec le type int tree.

Visuellement, t ressemble à ceci:

 
    5 
/\ 
() 2 
    /\ 
    ()() 

Et appeler fold_tree, nous avions besoin d'une fonction pour combiner les valeurs. Basé sur l'utilisation dans le cas Node, f prend 3 arguments, tout le même type de l'arbre et retourne la même chose. Nous ferons ceci:

let f x l r = x + l + r;; (* add all together *) 
fold_tree f 1 t;; 

Il serait utile de comprendre ce qui se passe dans chaque cas.Pour tout Leaf, un est retourné. Pour tout Node, il combine la valeur stockée et le résultat du pliage des sous-arbres gauche et droit. Dans ce cas, nous ajoutons simplement les nombres où chaque feuille compte comme un. Le résultat sur le pliage de cet arbre est 10.

Answer 2

Il semble que f est une fonction de réduction de trois paramètres, a est l'élément neutre de notre réduction et t est la racine, donc:

donné un binaire comme (je ne me souviens pas très bien la syntaxe des types de variantes, donc s'il vous plaît être condescendent ici)

let r = Node(Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf)),1,Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf))) 

si vous voulez résumer tous les nœuds, la fonction sera appelée comme:

let add x y z = x + y + z 
fold_tree add 0 r 

et nous vous t apparié comme un nœud, nous avons donc:

(add 1 (fold_tree add 0 Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf))) (fold_tree add 0 Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf)))) 

si nous élargissons un peu plus, nous obtenons:

(add 1 (add 2 (fold_tree add 0 Node(Leaf,3,Leaf)) (fold_tree add 0 Node(Leaf,4,Leaf))) (add 5 (fold_tree add 0 Node(Leaf,6,Leaf)) (fold_tree add 0 Node(Leaf,7,Leaf)))) 

et une fois de plus, nous CORRESPONDANCE les feuilles:

(add 1 (add 2 (add 3 0 0) (add 4 0 0)) (add 5 (add 6 0 0) (add 7 0 0)) 
(add 1 (add 2 3 4) (add 5 6 7)) 
(add 1 9 18) 

pour obtenir enfin:

28 

J'espère que ça aide.

Answer 3

Voici une façon de penser à fold_right sur les listes: une liste est par exemple

(1 :: (2 :: (3 :: []))) 

et vous réinterprètent la liste avec une nouvelle opération binaire en place de :: (et une nouvelle place constante de []).

fold_right (+) l 0 = (1 + (2 + (3 + 0))) 

Si vous vouliez faire absolument rien à votre liste, vous pouvez passer la fonction cons que la fonction et la liste vide comme élément neutre. Donc, dans un sens, fold_right est très général: il vous permet même de ne perdre aucune information. Le fold_tree dans votre question est la même idée pour le type de données des arbres. Si vous voulez réinterpréter votre arbre, vous lui passez une nouvelle fonction pour les noeuds qui seront appliqués à la place du constructeur Node. Si vous souhaitez obtenir un arbre identique, vous pouvez l'appliquer avec Leaf comme neutre et (fun x l r -> Node (l, x, r)) comme fonction. De même pour fold_left pour les listes, cet exemple d'application n'est pas très intéressant, mais cela signifie que fold_left est une transformation très générale (le terme technique est morphism).

Vous pouvez également additionner les éléments de l'arborescence avec la fonction (fun x l r -> x + l + r), par exemple.

Answer 4

Prenons un exemple d'arborescence.

let t = Node (Node (Leaf, 10, Leaf), 1, Node (Node (Leaf, 20, Leaf), 11, Leaf)) 

La définition générale d'une fold opération est que vous remplacez les constructeurs par des fonctions, partout dans l'arbre.

general_fold_tree node leaf t = 
    node (node leaf 10 leaf) 1 (node (node leaf 20 leaf) 11 leaf) 

node est une fonction qui construit un quelque chose d'un gauche quelque chose, un élément et un droit quelque chose, tout comme Node est un constructeur qui construit un arbre à partir d'un sous-arbre gauche, un noeud contenu et un sous-arbre droit. leaf est une constante, correspondant au constructeur de constantes Leaf.

let rec general_fold_tree (node : 'b -> 'a -> 'b -> 'b) (leaf : 'a) (t : 'a tree) : 'b = 
    let recurse t = general_fold_tree node leaf t in 
    match t with 
    | Node (l, x, r) -> node (recurse l) x (recurse r) 
    | Leaf -> leaf 

Notez que les types de fonctions correspondent à celles de la définition de type, sauf que si la définition du type décrit la construction d'un 'a tree, la fonction fois décrit la construction d'une 'b.

Les opérations qui ressemblent beaucoup au pli général sont toujours appelées pli. Par exemple, sur les listes, List.fold_right est le pli général selon la définition ci-dessus; List.fold_left est une variante qui applique la fonction dans l'autre sens (fold_left équivaut à inverser + fold_right + reverse, bien que ce soit plus clair et plus efficace).

Votre propre fold_tree est une simple variation de ce pli général où la fonction de nœud prend ses arguments dans un ordre différent du constructeur:

let equrts_fold_tree f a t = 
    let node l x r = f x l r in 
    general_fold_tree node a t 

Answer 5

Vous pourriez profiter de la lecture

http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/

http://lorgonblog.wordpress.com/2008/04/09/catamorphisms-part-three/

qui sont en F #, mais F # est très similaire à OCaml.