fold_tree en OCaml

Question

Como usted sabe, hay funciones de orden superior en OCaml, como fold_left, fold_right, etc. filtrar

En mi curso en la programación funcional se había introducido función llamada fold_tree, que es algo así como fold_left/right, no en listas, sino en árboles (binarios). Se ve así:

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

Cuando el árbol se define como:

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

OK, aquí está mi pregunta: ¿cómo funciona la función fold_tree? ¿Podría darme algunos ejemplos y explicar en lenguaje humano?

Answer 1

Aquí hay una sugerencia de estilo, coloque las barras al principio de la línea. Lo hace más claro donde comienza un caso. Para mayor coherencia, la primera barra es opcional pero recomendada.

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 cuanto a cómo funciona, considere el siguiente árbol:

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

Con el tipo int tree.

Visualmente, t se parece a esto:

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

Y fold_tree llamando, necesitaríamos una función para combinar los valores. Según el uso en el caso Node, f toma 3 argumentos, todos del mismo tipo del árbol y devuelve el mismo. Haremos esto:

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

Ayudaría a entender lo que sucede en cada caso.Para cualquier Leaf, se devuelve a. Para cualquier Node, combina el valor almacenado y el resultado de plegar los subárboles izquierdo y derecho. En este caso, solo estamos agregando los números donde cada hoja cuenta como una. El resultado en el plegamiento de este árbol es 10.

Answer 2

Parece que f es una función de reducción de tres parámetros, a es el elemento neutro de nuestra reducción y t es la raíz, por lo que:

dado un binario similar (que no recuerdo muy bien la sintaxis de tipos de variantes, por favor condescendent aquí)

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 desea sumar todos los nodos, la función será llamada como:

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

y nos pondremos t igualados como un nodo, por lo que tenemos:

(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 ampliamos un poco más, obtenemos:

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

y una vez más, estamos igualando las hojas:

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

para finalmente llegar:

28 

Espero que ayude.

Answer 3

Aquí es una manera de pensar acerca de fold_right en las listas: una lista es por ejemplo

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

y re-interpretar la lista con una nueva operación binaria en lugar de :: (y una nueva constante en lugar de []).

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

Si quería hacer absolutamente nada a su lista, usted podría pasar a la función cons como la función y la lista vacía como el elemento neutro. Entonces, en cierto sentido, fold_right es muy general: incluso le permite no perder ninguna información.

El fold_tree en su pregunta es la misma idea para el tipo de datos de los árboles. Si quiere volver a interpretar su árbol, le pasa una nueva función para los nodos que se aplicarán en lugar del constructor Node. Si desea obtener un árbol idéntico, puede aplicarlo con Leaf como neutral y (fun x l r -> Node (l, x, r)) como función. Similar a fold_left para listas, esta aplicación de ejemplo no es muy interesante, pero significa que fold_left es una transformación muy general (el término técnico es morphism).

También puede sumar los elementos del árbol con la función (fun x l r -> x + l + r), por ejemplo.

Answer 4

Tomemos un árbol de ejemplo.

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

La definición general de una operación fold es que reemplace constructores por funciones, en todas partes del árbol.

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

node es una función que construye un algo de una izquierda algo, un elemento y un derecho algo, al igual que Node es un constructor que construye un árbol de un subárbol izquierdo, un nodo contenido y un subárbol derecho. leaf es una constante que coincide con el constructor de constante 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 

en cuenta que los tipos de las funciones coinciden con los de la definición del tipo, excepto que en la definición de tipo describe la construcción de un 'a tree, la función de plegado se describe la construcción de cualquier 'b.

Las operaciones que se parecen mucho al pliegue general todavía se denominan pliegue. Por ejemplo, en las listas, List.fold_right es el doblez general según la definición anterior; List.fold_left es una variación que aplica la función al revés (fold_left es equivalente a invertir + fold_right + marcha atrás, aunque es más claro y más eficiente).

su propia fold_tree es una simple variación de este redil general donde la función del nodo toma sus argumentos en un orden diferente del constructor:

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

Usted puede disfrutar de la lectura

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

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

que están en F #, pero F # es muy similar a OCaml.