No estoy seguro de lo que está preguntando. Pero sí, alimenta un TreeAlgebra a foldTree correspondiente al cálculo que desea realizar en el árbol. Por ejemplo, para sumar todos los elementos en un árbol de Int s que usaría esta álgebra:
sumAlgebra :: TreeAlgebra Int Int
sumAlgebra = TreeAlgebra { leaf = id
, branch = (+) }
Lo que significa que, para obtener la suma de una hoja, aplique id (no hacer nada) con el valor de la hoja . Para obtener la suma de una rama, sume las sumas de cada uno de los hijos.
El hecho de que podemos decir (+) para la rama en lugar de, digamos, \x y -> sumTree x + sumTree y es la propiedad esencial del catamorfismo. Dice que para calcular alguna función f en alguna estructura de datos recursiva basta con tener los valores de f para sus hijos inmediatos.
Haskell es un lenguaje bastante único ya que podemos formalizar la idea de catamorfismo de manera abstracta. Vamos a hacer un tipo de datos para un solo nodo en su árbol, parametrizado sobre sus hijos:
data TreeNode a child
= Leaf a
| Branch child child
¿Vea qué hicimos allí? Acabamos de reemplazar a los niños recursivos con un tipo de nuestra elección. Esto es para que podamos poner las sumas de los subárboles allí cuando estamos plegando.
Ahora para lo realmente mágico. Voy a escribir esto en pseudohaskell, escribirlo en Haskell real es posible, pero tenemos que agregar algunas anotaciones para ayudar al contador de tipos, lo que puede ser algo confuso. Tomamos el "punto fijo" de un tipo de datos parametrizado, es decir, construimos un tipo de datos T tal que T = TreeNode a T. Llaman a este operador Mu.
type Mu f = f (Mu f)
Mire con cuidado aquí. El argumento a Mu no es un tipo, como Int o Foo -> Bar. Es un constructor tipo como Maybe o TreeNode Int - el argumento a Mu toma un argumento. (La posibilidad de abstraer sobre constructores de tipo es una de las cosas que hace que el sistema de tipos de Haskell realmente se destaque en su poder expresivo).
Por lo tanto, el tipo Mu f se define como tomar f y completar su parámetro de tipo con Mu f. Voy a definir un sinónimo para reducir algunos de los ruidos:
type IntNode = TreeNode Int
Ampliación Mu IntNode, obtenemos:
Mu IntNode = IntNode (Mu IntNode)
= Leaf Int | Branch (Mu IntNode) (Mu IntNode)
¿Ves cómo Mu IntNode es equivalente a su Tree Int? Acabamos de dividir la estructura recursiva y luego usamos Mu para volver a armarla. Esto nos da la ventaja de que podemos hablar de todos los tipos Mu a la vez. Esto nos da lo que necesitamos para definir un catamorfismo.
Definamos:
type IntTree = Mu IntNode
me dijeron que la propiedad esencial de la catamorphism es que para calcular alguna función f, basta con tener los valores de f por sus hijos inmediatos. Vamos a llamar al tipo de lo que estamos tratando de calcular r, y la estructura de datos node (IntNode sería una posible instanciación de esto). Entonces para calcular r en un nodo particular, necesitamos que el nodo con sus hijos sea reemplazado por sus r s. Este cálculo tiene el tipo node r -> r. Por lo que un catamorphism dice que si tenemos uno de estos cálculos, entonces podemos calcular r para la totalidad recursiva estructura (recuerde la recursividad se denota explícitamente aquí con Mu):
cata :: (node r -> r) -> Mu node -> r
Hacer este concreto para nuestro ejemplo, esto se parece a:
cata :: (IntNode r -> r) -> IntTree -> r
reiterando, si podemos tomar un nodo con r s para sus hijos y calcular una r, entonces podemos calcular una r para todo un árbol.
Con el fin de calcular hecho esto, necesitamos node ser un Functor - que es lo que necesitamos para ser capaz de asignar una función arbitraria de los hijos de un nodo.
fmap :: (a -> b) -> node a -> node b
Esto se puede hacer sin rodeos para IntNode.
fmap f (Leaf x) = Leaf x -- has no children, so stays the same
fmap f (Branch l r) = Branch (f l) (f r) -- apply function to each child
Ahora, finalmente, podemos dar una definición para cata (la restricción Functor node simplemente dice que node tiene una adecuada fmap):
cata :: (Functor node) => (node r -> r) -> Mu node -> r
cata f t = f (fmap (cata f) t)
que utiliza el nombre del parámetro t para la mnemotécnica valor de "árbol". Esta es una definición abstracta y densa, pero en realidad es muy simple. Dice: realizar recursivamente cata f - el cálculo que estamos haciendo sobre el árbol - en cada uno de los hijos t (que son ellos mismos Mu node s) para obtener un node r, y luego pasar ese resultado a f calcular el resultado para t .
Viéndolo de nuevo al principio, el álgebra que está definiendo es esencialmente una forma de definir esa función node r -> r. De hecho, dado un TreeAlgebra, podemos obtener fácilmente la función doble:
foldFunction :: TreeAlgebra a r -> (TreeNode a r -> r)
foldFunction alg (Leaf a) = leaf alg a
foldFunction alg (Branch l r) = branch alg l r
Así, el catamorphism árbol puede ser definida en términos de nuestra genérico de la siguiente manera:
type Tree a = Mu (TreeNode a)
treeCata :: TreeAlgebra a r -> (Tree a -> r)
treeCata alg = cata (foldFunction alg)
estoy fuera de tiempo . Sé que se volvió realmente abstracto muy rápido, pero espero que al menos te haya dado un nuevo punto de vista para ayudarte a aprender. ¡Buena suerte!
Nota no relacionada: la etiqueta "catamporphisms" está mal escrita; tiene una 'p' extra. Aparentemente no soy lo suficientemente bueno para editar eso, ya que eso constituiría crear una nueva etiqueta. (Jesús lloró) –
@Derrick Turk: Solo hay tres preguntas con esta etiqueta. No sería muy difícil volver a etiquetarlos a todos. – fuz
@FUZxxl: Aparentemente necesitas 1500 reputación para crear nuevas etiquetas, y en ese momento "catamorfismo" aún no existía. – ephemient