module Tree where

import Data.Monoid
import Test.QuickCheck
import Test.QuickCheck.Checkers
import Test.QuickCheck.Classes

-- Solution:
-- https://www.reddit.com/r/HaskellBook/comments/7w7bqn/ch_21_is_this_a_sane_instance_of_traversable/

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

instance Functor Tree where
    fmap _ Empty = Empty
    fmap f (Leaf x) = Leaf $ f x
    fmap f (Node x y z) = Node (fmap f x) (f y) (fmap f z)

-- foldMap is a bit easier and looks more natural, but you can do
-- foldr too for extra credit.
instance Foldable Tree where
    foldMap _ Empty = mempty
    foldMap f (Leaf x) = f x
    foldMap f (Node x y z) = (foldMap f x) <> (f y) <> (foldMap f z)

instance Traversable Tree where
    traverse f Empty = pure Empty
    traverse f (Leaf x) = Leaf <$> f x
    traverse f (Node x y z) = Node <$> (traverse f x) <*> (f y) <*> (traverse f z)

instance Arbitrary a => Arbitrary (Tree a) where
    arbitrary = do
        x <- arbitrary
        y <- arbitrary
        z <- arbitrary
        frequency [ (1, return Empty)
                  , (2, return $ Leaf y)
                  , (3, return $ Node x y z)
                  ]

instance Eq a => EqProp (Tree a) where
    (=-=) = eq