Operación de plegado en árbol?

Question

que estoy tomando una clase en Haskell, y tenemos que definir la operación de plegado para un árbol definido por:

data Tree a = Lf a | Br (Tree a) (Tree a) 

Me parece que no puede encontrar ninguna información sobre la operación "tfold" o realmente lo que supone que hacer. Cualquier ayuda sería muy apreciada.

Answer 1

Un pliegue en una lista es una reducción de una lista en un solo elemento. Toma una función y luego aplica esa función a los elementos, dos a la vez, hasta que solo tenga un elemento. Por ejemplo:

Prelude> foldl1 (+) [3,5,6,7] 
21 

... se encuentra por las operaciones de hacer uno por uno:

3 + 5 == 8 
8 + 6 == 14 
14 + 7 == 21 

A veces se puede escribir

ourFold :: (a -> a -> a) -> [a] -> a 
ourFold _   [a]  = a -- pattern-match for a single-element list. Our work is done. 
ourFold aFunction (x0:x1:xs) = ourFold aFunction ((aFunction x0 x1):xs) 

Un pliegue árbol haría esto, pero sube o baja las ramas del árbol. Para hacer esto, primero necesita emparejar patrones para ver si está operando en una hoja o una rama.

treeFold _ (Lf a) = Lf a -- You can't do much to a one-leaf tree 
treeFold f (Br a b) = -- ... 

El resto depende de usted, ya que es la tarea. Si estás atascado, primero intenta pensar en qué tipo debe ser.

Answer 2

Un doblez es una operación que "compacta" una estructura de datos en un solo valor mediante una operación. Existen variaciones dependiendo de si tiene un valor inicial y un orden de ejecución (por ejemplo, para las listas que tiene foldl, foldr, foldl1 y foldr1), por lo que la implementación correcta depende de su asignación.

Supongo que su tfold debería simplemente reemplazar todas las hojas con sus valores, y todas las ramas con aplicaciones de la operación dada. Dibuja un árbol de ejemplo con algunos números, un "colapso" le da una operación como (+). Después de esto, debería ser fácil escribir una función haciendo lo mismo.

Answer 3

Siempre pienso en pliegues como una forma de reemplazar sistemáticamente constructores por otras funciones. Así, por ejemplo, si usted tiene un do-it-yourself List tipo (definido como data List a = Nil | Cons a (List a)), el pliegue correspondiente se puede escribir como:

listfold nil cons Nil = nil 
listfold nil cons (Cons a b) = cons a (listfold nil cons b) 

o, tal vez de manera más concisa, como:

listfold nil cons = go where 
    go Nil = nil 
    go (Cons a b) = cons a (go b) 

El tipo de listfold es b -> (a -> b -> b) -> List a -> b. Es decir, se necesitan dos 'constructores de reemplazo'; uno que dice cómo un valor Nil debe transformarse en b, otro constructor de reemplazo para el constructor Cons, indicando cómo el primer valor del constructor Cons (de tipo) debe combinarse con un valor de tipo b (porque b? fold ya ha sido aplicado recursivamente!) para obtener un nuevo b, y finalmente un List a para aplicar el total de she-bang a - con un resultado de b.

En su caso, el tipo de tfold debe ser por un razonamiento análogo; ¡espero que puedas llevarlo desde allí!

Answer 4

Imagine que define que un árbol debe mostrarse de la siguiente manera, por ejemplo: "<1#<<2#3>#<4#5>>>". Doblar dicho árbol significa reemplazar cada nodo de rama con una operación real suministrada que se realizará en los resultados del doble recursivo realizado en los constituyentes del tipo de datos (aquí, los dos nodos hijos del nodo, que son ellos mismos, cada uno, un árbol), por ejemplo con +, produciendo (1+((2+3)+(4+5))).

Así, para las hojas que sólo debe tomar los valores dentro de ellos, y por ramas, aplicar de forma recursiva el pliegue para cada uno de los dos, y combinar los dos resultados con la función suministrada, aquella con la que el árbol es doblada. (edit:) Al "tomar" valores de hojas, también puede transformarlos, aplicando una función única. Así pues, en general, su plegamiento necesitará dos funciones proporcionadas por el usuario, uno para hojas, y otro para combinar los resultados de plegado de forma recursiva los consituents de ramas.

Su tipo de datos de árbol podría haberse definido de manera diferente, p. con hojas posiblemente vacías, y con nodos internos que también llevan los valores. Entonces tendría que proporcionar un valor predeterminado para ser utilizado en lugar de nodos hoja vacíos, y una operación de combinación de tres vías.

Otra distinción para darse cuenta de que aquí es, lo doblas, y cómo se pliegue. Es decir. podría doblar su árbol en una lineal moda, (1+(2+(3+(4+5)))), o podría doblar una lista lineal en como un árbol moda. Se trata de cómo se entrelaza la "expresión" resultante. Por supuesto, en la versión clásica de plegable, la estructura de la exsión sigue la de la estructura de datos que se está plegando; pero variations do exist. Tenga en cuenta también que la operación de combinación podría no ser estricta y podría consumir/producir compuesto, así como valores atómicos.