module B4FoldTraverse where

import Data.Monoid
  (
  (<>),
  )

import B2Functor

instance Foldable Tree where
  foldMap f Empty        = mempty
  foldMap f (Node l x r) = foldMap f l <> f x <> foldMap f r

sumFold :: Foldable f => f Int -> Int
sumFold = foldr (+) 0

lengthFold :: Foldable f => f a -> Int
lengthFold = foldr (const (1 +)) 0

treeToList :: Tree a -> [a]
treeToList Empty        = []
treeToList (Node l x r) = treeToList l <> [x] <> treeToList r

foldableToList :: Foldable f => f a -> [a]
foldableToList = foldr (:) []

instance Traversable Tree where
  traverse g Empty        = pure Empty
  traverse g (Node l x r) = Node <$> traverse g l
                                 <*> g x
                                 <*> traverse g r
