module Prova where

import Data.Tree

annotate :: b -> (b -> a -> b) -> Tree a -> Tree b
annotate k f (Node a sub) =
        let k' = f k a
        in Node k' (map (annotate k' f) sub)

treeIn :: Tree Integer
treeIn = Node 7 [Node 3 [], Node 1 [Node 2 [], Node 18 []]]

treeOut :: Tree (Integer, Integer)
treeOut = annotate (0,0) (\(a, k) b -> (b, k+b)) treeIn

-- treeOut is now a Tree with a “running sum” annotation
-- Node (7,7) [Node (3,10) [], Node (1,8) [Node (2,10) [], Node (18,26) []]]

-- Original Q: is it possible to do this with some typeclass (Foldable?
-- Traversable?)