Catamorphism y el árbol-desplazamiento en Haskell

Question

Estoy impaciente, mirando hacia adelante a la comprensión catamorphism relacionado con esta cuestión de forma :)

Sólo he practicado el comienzo de Real World Haskell tutorial. Así, tal vez voy a pedir demasiado en este momento, si era el caso, sólo dime los conceptos que debería aprender.

A continuación, cito el Wikipedia ejemplo de código para catamorphism .

Me gustaría saber su opinión sobre foldTree a continuación, una forma de recorrer un árbol, frente a esta otra pregunta SO y respuestas, también se trata de recorrer un árbol n-aria árbol transversal . (Forma independiente de ser binaria o no, creo que el catamorphism a continuación se puede escribir con el fin de gestionar árbol n-ario)

Me puso en el comentario lo que entiendo, y con mucho gusto si me pueden corregir y aclarar algunas cosas.

{-this is a binary tree definition-}
data Tree a = Leaf a
            | Branch (Tree a) (Tree a)

{-I dont understand the structure between{} 
however it defines two morphisms, leaf and branch 
leaf take an a and returns an r, branch takes two r and returns an r-} 
data TreeAlgebra a r = TreeAlgebra { leaf   :: a      -> r
                                   , branch :: r -> r -> r }

{- foldTree is a morphism that takes: a TreeAlgebra for Tree a with result r, a Tree a
and returns an r -} 
foldTree :: TreeAlgebra a r -> Tree a -> r
foldTree a@(TreeAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldTree a@(TreeAlgebra {branch = g}) (Branch l r) = g (foldTree a l) (foldTree a r)

En este punto estoy teniendo muchas dificultades, me parece adivinar que la hoja morfismo se puede aplicar a cualquier hoja Sin embargo, con el fin de utilizar el código de verdad, foldTree necesita ser alimentado un TreeAlgebra definido, un TreeAlgebra que tiene una hoja morfismo definido con el fin de hacer algo?
pero en este caso en el código foldTree yo esperaría {f =} hoja y no al contrario

Cualquier aclaración de que sería muy bienvenido.

Answer 1

No exactamente seguro de lo que estás pidiendo. Pero sí, se envía una TreeAlgebra a foldTree correspondiente al cálculo que desea realizar en el árbol. Por ejemplo, para sumar todos los elementos en un árbol de Ints 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 niños.

El hecho de que podemos decir (+) para la rama en lugar de, digamos, \x y -> sumTree x + sumTree y es la propiedad esencial de la catamorphism. Se dice que para calcular alguna función f en alguna estructura de datos recursiva es suficiente con tener los valores de f por sus hijos inmediatos.

Haskell es un lenguaje bastante único en que podemos formalizar la idea de catamorphism manera abstracta. Vamos a hacer un tipo de datos para un solo nodo en el árbol, parametrizado sobre sus hijos:

data TreeNode a child
    = Leaf a
    | Branch child child

Ver lo que hicimos allí? Nos acaba de reemplazar a los niños recursivos con un tipo de nuestra elección. Esto es para que podamos poner sumas los subárboles allí cuando estamos plegable.

Ahora, para lo realmente mágico. Voy a escribir esto en pseudohaskell - escribirlo en bienes Haskell es posible, pero hay que añadir algunas anotaciones para ayudar al typechecker que puede ser un poco confuso. Tomamos el "punto fijo" de un tipo de datos con parámetros - es decir, la construcción de un tipo de datos de tal manera que T T = TreeNode a T. A esto le llaman Mu operador.

type Mu f = f (Mu f)

Mire cuidadosamente aquí. El argumento para Mu no es un tipo, como Int o Foo -> Bar. Es un tipo constructor como Maybe o TreeNode Int - el argumento de Mu sí toma un argumento. (La posibilidad de extraer más de constructores de tipos es una de las cosas que hace el sistema de tipos de Haskell realmente se destacan en su poder expresivo).

Así que la Mu f tipo se define como teniendo f y llenado en su parámetro de tipo con Mu f sí mismo. Voy a definir un sinónimo para reducir algunos de los ruidos:

type IntNode = TreeNode Int

La expansió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 desgarrado la estructura recursiva aparte y luego se usa Mu para poner de nuevo juntos de nuevo. Esto nos da la ventaja de que se puede hablar de todo tipo Mu a la vez. Esto nos da lo que necesitamos para definir un catamorphism.

Vamos a definir:

type IntTree = Mu IntNode

dije 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 a la clase de lo que estamos tratando de r de cómputo, y la node estructura de datos (IntNode sería una posible instancia de esto). Así que para r de computación en un nodo particular, necesitamos el nodo con sus hijos reemplazados por sus rs. Este cálculo tiene node r -> r tipo. Por lo que un catamorphism dice que si tenemos uno de estos cálculos, entonces podemos calcular r para la totalidad de 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 rs 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 - eso 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 puede hacerse 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, fin , que puede dar una definición para cata (la restricción Functor node sólo dice que tiene una node fmap adecuado):

cata :: (Functor node) => (node r -> r) -> Mu node -> r
cata f t = f (fmap (cata f) t)

utiliza el nombre del parámetro t para el valor mnemotécnico de "árbol". Esta es una definición abstracta densa, pero en realidad es muy simple. Dice: recursiva realizar cata f - el cálculo que estamos haciendo sobre el árbol - en cada uno de los hijos de t (que son a su vez Mu nodes) para obtener una node r, y luego pasar ese resultado para calcular el resultado para f t sí

La vinculación de nuevo a este principio, el álgebra se 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 puso muy abstracta muy rápido, pero espero que al menos le dio un nuevo punto de vista para ayudar a su aprendizaje. Buena suerte!

Answer 2

Creo que estabas estabas pidiendo una pregunta acerca de las '} {s. Hay una pregunta anterior con una buena discusión de {} 's. Se llaman de Haskell sintaxis de registro . La otra pregunta es ¿por qué construir el álgebra. Esta es una función típica de paradigma en el que generalizar los datos como funciones.

El ejemplo más famoso es la construcción de la iglesia de los Naturals , donde f = + 1 y z = 0 , 0 = z, 1 = f z, 2 = f (f z), 3 = f (f (f z)), etc ...

Lo que está viendo es esencialmente la misma idea se aplica a un árbol. Trabajar el ejemplo de la iglesia y el árbol se haga clic.