Ответ 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
и a 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')