How to sum tree elements using folds?

Question

I'm trying to learn the 'folds' (only 'foldr' and 'foldl') functionality of Haskell through doing some sample coding. I have defined a Tree (not binary) like so:

data NTree a = Nil | Tree a [NTree a] deriving Show

I want to sum all the elements of the tree using a function. I have outlined the type signature and the base case of the function, but I'm not sure how to implement the logic itself using folds. This is what I have so far:

sumElements :: NTree Int -> Int
sumElements Nil = 0
sumElements tree = foldr (???) 0 tree

I really can't think of how to get started. Any help filling in the folds function would be appreciated.

Answer 1

You pretty much have it.

sumElements tree = foldr (+) 0 tree