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

instance Foldable Tree where
  -- foldr :: (a -> b -> b) -> b -> Tree a -> b
  foldr f ini Nil = ini
  foldr f ini (Branch a b c) = foldr f (f b (foldr f ini c)) a

instance Functor Tree where
  fmap _ Nil = Nil
  fmap f (Branch l x r) = Branch (fmap f l) (f x) (fmap f r)

instance Applicative Tree where
  pure f = Branch (pure f) f (pure f)
  (<*>) Nil _ = Nil
  (<*>) _ Nil = Nil
  (<*>) (Branch fl fx fr) (Branch l x r) = Branch (fl <*> l) (fx x) (fr <*> r)

instance Traversable Tree where
  --traverse :: (a -> f b) -> t a -> f (t b)
  traverse _ Nil = pure Nil
  traverse g (Branch a b c) = Branch <$> (traverse g a) <*> g b <*>  (traverse g c)