import Prelude hiding (sequenceA, traverse)


class Traversable_v1 t where
    sequenceA :: Applicative f => t (f a) -> f (t a)
    traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)


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

instance Traversable_v1 [] where
 -- sequenceA :: Applicative f => [f a] -> f [a]
    sequenceA []     = pure []
    sequenceA (x:xs) = pure (:) <*> x <*> sequenceA xs

 -- 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_v1 Tree where
 -- sequenceA :: Applicative f => Tree (f a) -> f (Tree a)
    sequenceA Empty        = pure Empty
    sequenceA (Node l a r) = pure Node <*> sequenceA l <*> a <*> sequenceA r

 -- 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