Как представить дерево с общим доступом в Haskell

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

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

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

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

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