import Prelude hiding (sequenceA, traverse)

class Functor t => Traversable_v2 t where
    sequenceA :: Applicative f => t (f a) -> f (t a)
    sequenceA = traverse id

    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    traverse func = sequenceA . fmap func


--------------------------------------------------------------------------------

instance Traversable_v2 [] where
 -- traverse :: Applicative f => (a -> f b) -> [a] -> f [b]
    traverse func []     = pure []
    traverse func (a:as) = pure (:) <*> func a <*> traverse func as


--------------------------------------------------------------------------------

data Tree a = Empty | Node (Tree a) a (Tree a)

instance Traversable_v2 Tree where
 -- traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
    traverse func Empty        = pure Empty
    traverse func (Node l a r) =
      pure Node <*> traverse func l <*> func a <*> traverse func r

instance Functor Tree where
 -- fmap :: (a -> b) -> Tree a -> Tree b
    fmap f Empty        = Empty
    fmap f (Node l a r) = Node (fmap f l) (f a) (fmap f r)