cómo representar árbol con el intercambio en Haskell

Question

quisiera representar un "árbol" de la siguiente forma en Haskell:

/\        
    /\/\ 
/\/\/\ 
/\/\/\/\ 
` ` ` ` ` 

/y \ son las ramas y las hojas `. Puede ver que a partir de cualquier nodo, siguiendo la ruta de la izquierda, la derecha lo lleva al mismo nodo que sigue el camino correcto y luego a la izquierda. Debería poder etiquetar las hojas, aplicar una función de las dos descendencias en cada nodo y propagar esta información a la raíz en O (n^2) tiempo. Mis esfuerzos ingenuos me están dando un tiempo de ejecución exponencial. ¿Algún consejo?

Answer 1

Sin duda, es posible construir una árbol con nodos compartidos. Por ejemplo, podríamos definir:

data Tree a = Leaf a | Node (Tree a) (Tree a) 

y luego cuidadosamente construir un valor de este tipo como en

tree :: Tree Int 
tree = Node t1 t2 
    where 
    t1 = Node t3 t4 
    t2 = Node t4 t5 
    t3 = Leaf 2 
    t4 = Leaf 3 
    t5 = Leaf 5 

para lograr el intercambio de subárboles (en este caso t4).

Sin embargo, ya que esta forma de compartir no es observable en Haskell, es muy difícil de mantener: por ejemplo, si se recorre un árbol de volver a etiquetar sus hojas

relabel :: (a -> b) -> Tree a -> Tree b 
relabel f (Leaf x) = Leaf (f x) 
relabel f (Node l r) = Node (relabel f l) (relabel f r) 

que compartir suelto. Además, cuando se hace un cálculo de abajo hacia arriba, como

sum :: Num a => Tree a -> a 
sum (Leaf n) = n 
sum (Node l r) = sum l + sum r 

al final no tomar ventaja de compartir y posiblemente duplicar el trabajo.

Para superar estos problemas, puede hacer que compartir explícito (y por lo tanto observable) mediante la codificación de los árboles de una manera gráfica como:

type Ptr = Int 
data Tree' a = Leaf a | Node Ptr Ptr 
data Tree a = Tree {root :: Ptr, env :: Map Ptr (Tree' a)} 

El árbol del ejemplo anterior ahora se puede escribir como

tree :: Tree Int 
tree = Tree {root = 0, env = fromList ts} 
    where 
    ts = [(0, Node 1 2), (1, Node 3 4), (2, Node 4 5), 
      (3, Leaf 2), (4, Leaf 3), (5, Leaf 5)] 

El precio a pagar es que las funciones que atraviesan estas estructuras son algo engorroso para escribir, pero ahora se puede definir, por ejemplo, una función que conserva el reetiquetado compartir

relabel :: (a -> b) -> Tree a -> Tree b 
relabel f (Tree root env) = Tree root (fmap g env) 
    where 
    g (Leaf x) = Leaf (f x) 
    g (Node l r) = Node l r 

y una función sum que no duplique el trabajo cuando el árbol ha compartido nodos:

sum :: Num a => Tree a -> a 
sum (Tree root env) = fromJust (lookup root env') 
    where 
    env' = fmap f env 
    f (Leaf n) = n 
    f (Node l r) = fromJust (lookup l env') + fromJust (lookup r env') 

Answer 2

Tal vez puede representar simplemente como una lista de hojas y aplicar el nivel de funciones de nivel hasta que esté abajo a un valor, es decir algo como esto:

type Tree a = [a] 

propagate :: (a -> a -> a) -> Tree a -> a 
propagate f xs = 
    case zipWith f xs (tail xs) of 
    [x] -> x 
    xs' -> propagate f xs'