haskell - ¿Operación de plegado de árbol?

tree fold

Question

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

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

Parece que no puedo encontrar ninguna información sobre la operación "multiplicar" o realmente lo que se supone que debe hacer. Cualquier ayuda sería muy apreciada.

Answer 1

Siempre pienso en pliegues como una forma de reemplazar sistemáticamente constructores por otras funciones. Entonces, por ejemplo, si tiene un tipo de List hágalo usted mismo" (definido como data List a = Nil | Cons a (List a) ), el doblez correspondiente se puede escribir como:

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

o, quizás más concisamente, 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 un b , otro constructor de reemplazo para el constructor Cons , y explica cómo el primer valor del constructor Cons (de tipo a ) debe combinarse con un valor de tipo b (¿ b qué b ? fold ya ha sido aplicado recursivamente!) para producir 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 (a -> b) -> (b -> b -> b) -> Tree a -> b por un razonamiento análogo; ¡espero que puedas llevarlo desde allí!

Answer 2

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 haciendo operaciones una a una:

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

Un doblez 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 doblez de á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 ti, ya que es tarea. Si estás atascado, primero intenta pensar en qué tipo debe ser.

Answer 3

Un pliegue es una operación que "compacta" una estructura de datos en un solo valor utilizando una operación. Existen variaciones dependiendo de si tiene un valor de inicio 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 tu 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 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 bifurcación con una operación real suministrada que se realizará en los resultados del doblez realizado recursivamente en los constituyentes del tipo de datos (aquí, los dos nodos secundarios del nodo, que son ellos mismos, cada uno, un árbol), por ejemplo con + , produciendo (1+((2+3)+(4+5))) .

Por lo tanto, para hojas solo debe tomar los valores dentro de ellas, y para ramas, aplicar recursivamente el doblez para cada una de las dos, y combinar los dos resultados con la función suministrada, aquella con la que se dobla el árbol. ( Editar:) Al "tomar" valores de las hojas, también puede transformarlos, aplicando una función única. Por lo tanto, en general, su plegado necesitará dos funciones proporcionadas por el usuario, una para las hojas y otra para combinar los resultados de doblar recursivamente los componentes de las ramas .

El tipo de datos de árbol podría haberse definido de manera diferente, por ejemplo, con hojas posiblemente vacías y con nodos internos que también contengan 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 que debemos tener en cuenta aquí es qué doblas y cómo lo retiras. Es decir, podría doblar su árbol de forma lineal (1+(2+(3+(4+5)))) , o podría doblar una lista lineal en forma de árbol . Se trata de cómo se entrelaza la "expresión" resultante. Por supuesto, en la versión clásica del plegado, la estructura de la exsión sigue la de la estructura de datos que se está plegando; pero las variaciones existen Tenga en cuenta también que la operación de combinación podría no ser estricta y podría consumir / producir valores compuestos y atómicos.