Как изобразить дерево с совместным использованием в Haskell

Question

Я бы хотел представить «дерево» следующей формы в Haskell:

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

/ и \ - ветви и `листья. Вы можете видеть, что начиная с любого узла, следуя по левому пути, затем по правому пути вы попадете в тот же узел, что и по правому пути, затем по левому. Вы должны иметь возможность пометить листья, применить функцию двух потомков в каждом узле и распространить эту информацию в корень за O (n ^ 2) времени. Мои наивные усилия дают мне экспоненциальное время выполнения. Есть намеки?

Answer 1

Конечно, возможно построить дерево с общими узлами.Например, мы могли бы просто определить:

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

и затем тщательно построить значение этого типа, как в

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

, чтобы добиться разделения поддеревьев (в данном случае t4).

Однако, поскольку эта форма совместного использования не наблюдаема в Haskell, ее очень трудно поддерживать: например, если вы пересекаете дерево, чтобы пометить его листья

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)

вы теряете совместное использование.,Кроме того, при выполнении восходящих вычислений, таких как

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

, вы в конечном итоге не используете преимущества совместного использования и, возможно, дублируете работу.

Чтобы преодолеть эти проблемы, вы можете сделать общий доступ явным (и, следовательно, наблюдаемый) путем кодирования ваших деревьев в виде графа:

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

Дерево из приведенного выше примера теперь можно записать как

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)]

Цена, которую нужно заплатить, состоит в том, чтофункции, которые пересекают эти структуры, несколько трудоемки для написания, но теперь мы можем определить, например, функцию перемаркировки, которая сохраняет совместное использование

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

и функцию sum, которая не дублирует работу, когда дерево имеет общий доступузлы:

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

Возможно, вы можете представить его просто как список листьев и применять уровень функции за уровнем, пока не достигнете одного значения, то есть что-то вроде этого:

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'