data Tree a    = Leaf | Branch (Tree a) a ( Tree a )
  deriving (Eq, Show)

tdoubles :: Tree Int -> Tree Int 
tdoubles t = case t of
  Leaf         -> Leaf
  Branch l k r -> Branch (tdoubles l) (k*2) (tdoubles r)

preorder :: Tree a -> [a]
preorder t = case t of
  Leaf -> []
  Branch l k r -> [ k ] ++ ( preorder l ) ++ ( preorder r )

tsum :: Tree Int -> Int
tsum t = case t of
  Leaf -> 0
  Branch l k r -> ( tsum l ) + k + ( tsum r )

t1, t2, t3 :: Tree Int
t1 = Branch Leaf 3 Leaf
t2 = Branch Leaf 2 (Branch Leaf 1 Leaf)
t3 = Branch t1 4 t2
------------------------------

tfold :: b -> (b -> a -> b -> b) -> (Tree a) -> b
tfold leaf  branch t = case t of
  Leaf         -> leaf
  Branch l k r -> branch (tfold leaf branch l) k (tfold leaf branch r)

tsum' :: Tree Int -> Int
tsum' = tfold 0 ( \ l k r -> l + k + r )

preorder' :: Tree a -> [a]
preorder' = tfold [] ( \ l k r -> [k] ++ l ++ r ) 

tdoubles' :: Tree Int -> Tree Int
tdoubles' = tfold Leaf ( \ l k r -> Branch l (2*k) r )

tmap :: (a -> b ) -> ( Tree a ) -> ( Tree b )
tmap g = tfold Leaf ( \ l k r -> Branch l (g k) r )
-- tmap f t = case t of
--   Leaf -> Leaf
--   Branch l k r -> Branch (tmap f l) (f k) (tmap f r)

tdoubles'' :: Tree Int -> Tree Int
tdoubles'' = tmap ( 2* )