Propagate значения вверх Data.Tree в Haskell

Question

Использование Data.Tree я могу определить дерево, как это:

mkTree :: T.Tree Double 
mkTree = T.Node 0 [ T.Node 4 [] 
        , T.Node 0 [T.Node 5 [], T.Node 4 []] 
        , T.Node 0 [T.Node 2 [], T.Node 1 []] 
        ] 

Что бы перевести так:

0.0 
| 
+- 4.0 
| 
+- 0.0 
| | 
| +- 5.0 
| | 
| `- 4.0 
| 
`- 0.0 
    | 
    +- 2.0 
    | 
    `- 1.0 

теперь я хочу, чтобы преобразовать дерево так что каждый T.Node теперь содержит сумму (или какой-либо другой функции) своих детей:

16.0 
| 
+- 4.0 
| 
+- 9.0 
| | 
| +- 5.0 
| | 
| `- 4.0 
| 
`- 3.0 
    | 
    +- 2.0 
    | 
    `- 1.0 

проблема в том, что я не могу получить доступ к дочерним узлам узла, используя fmap. То, что я до сих пор их функции:

propagate :: Num a => T.Tree a -> T.Tree a 
propagate (T.Node x []) = T.Node x [] 
propagate (T.Node _ ts) = T.Node (sum $ map gather ts) (map propagate ts) 

gather :: Num a => T.Tree a -> a 
gather (T.Node n []) = n 
gather (T.Node _ ts) = sum $ map gather ts 

Но это кажется слишком сложным, особенно, если я заменить sum с другой функцией. Может быть, есть лучший способ сделать это, используя Foldable или Traversable?

Answer 1

Я не думаю, что Foldable выставляет достаточно структуру, Tree «s, чтобы делать то, что вы хотите. Traversable может, но кажется довольно сложным, чтобы получить право; Я думаю, что я бы предпочел реализации шаблона рекурсии, как это:

foldTree :: (a -> [b] -> b) -> Tree a -> b 
foldTree f = go where 
    go (Node value children) = f value (map go children) 

Тогда можно реализовать операцию суммирования в

sums :: Num a => Tree a -> Tree a 
sums = foldTree (\val children -> Node (sum (val:map rootLabel children)) children) 

или даже обобщать Num к Semigroup с использованием sconcat и (:|) вместо sum и (:).

Answer 2

Вы хотите работать, для каждого узла, со всеми поддерева (метка узла включена), то одна функция полезна может быть

subtrees :: Tree a -> Tree (Tree a) 
subtrees n@(Node _ xs) = Node n (map subtrees xs) 

теперь можно применить любую функцию дерева для любого дерева деревьев

sumSubtree :: Num a => Tree a -> Tree a 
sumSubtree = fmap sum . subtrees 

с желаемым результатом.

Как говорит Даниэль, этот sumSubtree неэффективен, так как сумма от листьев до корня имеет оптимальную субструктуру.

Но тогда, не единственное решение существует, посмотрите на следующую версию кратного

foldTree :: (a → Forest b → b) → Tree a → Tree b 
foldTree f (Node x xs) = Node (f x xs') xs' 
         where xs' = foldTree f ↥ xs 

в настоящее время является оптимальным, только если f не нужен корень и предыдущих Филиалы для вычисления некоторой ветви значения (например проблемы суммы). Но (например), если какой-либо ключ хранится на каждом узле, эта реализация суммы также будет неэффективной.

(Используя предыдущий раз, проблема сумма может быть записана foldTree (λx xs → ∑(x: map rootLabel xs)))