Как суммировать элементы n-арного дерева Haskell?

Question

Я новичок в Haskell программировании, и я попытался код и манипулировать Haskell н-кратное дерево определяется как

data Tree = Empty | Node Integer [Tree] 

Я хочу написать sum функции для этой структуры дерева, но я не понять это , Функция Я закодирован здесь:

sumall Empty = 0 

sumall (Node a (x:xy)) = a + (sumall x) 

Вход: (Node 5 [Node 2 [Node 1 [Empty]],Node 8 [Node 7 [Node 6 [Empty]],Node 12 [Node 10 [Node 9 [Empty]],Node 13 [Node 15 [Empty]]]]])

Результат = 8.

Как развивать эту функцию, чтобы просуммировать все элементы в этом дереве? Заранее спасибо.

Answer 1

import qualified Data.Foldable as F 

instance F.Foldable Tree where 
    foldMap f Empty = mempty 
    foldMap f (Node a ts) = mconcat $ f a : map (F.foldMap f) ts 

sumall = F.sum 

без Складная вы могли бы сделать что-то вроде

sumall Empty = 0 
sumall (Node a ts) = a + foldr (+) 0 (map sumall ts)