-- chapter 8 exercises

-- q1


data Nat = Zero | Succ Nat deriving Show


nat2int Zero     = 0
nat2int (Succ n) = 1 + nat2int n


int2nat 0 = Zero
int2nat n = Succ (int2nat (n-1))

add Zero     n = n
add (Succ m) n = Succ (add m n) 

mult Zero _ = Zero
mult (Succ x) y = add y (mult x y)

num1 = (Succ (Succ (Succ Zero)))
num2 = (Succ (Succ (Succ (Succ Zero))))

test_mult = mult num1 num2


-- q2
data Expr = Val Int
          | Add Expr Expr
          | Mul Expr Expr deriving Show
		  
eval (Val n)   = n
eval (Add x y) = eval x + eval y
eval (Mul x y) = eval x * eval y

-- eval = folde id (+) (*)

folde f1 f2 f3 (Val n) = f1 n
folde f1 f2 f3 (Add x y) = f2 (folde f1 f2 f3 x) (folde f1 f2 f3 y)
folde f1 f2 f3 (Mul x y) = f3 (folde f1 f2 f3 x) (folde f1 f2 f3 y)

eval2 = folde id (+) (*)

expr = (Mul (Val 3) (Add (Val 4) (Val 2)))

test_folde = eval2 expr

-- q3

data Tree a = Leaf a
            | Node (Tree a) a (Tree a) deriving Show
			
t = Node (Node (Leaf 1) 3 (Leaf 4)) 5
         (Node (Leaf 6) 7 (Leaf 9))
		 
t2 = Node (Node (Leaf 1) 3 (Leaf 4)) 5
          (Node (Leaf 6) 7 (Node (Leaf 1) 3 (Leaf 4)))		 


size (Leaf _) = 1
size (Node left value right) = 1 + (size left) + (size right)

balanced (Leaf _) = True
balanced (Node left value right) = (balanced left) &&
                                   (balanced right) &&
                                   (size left) == (size right)

test_balanced = balanced t
test_balanced2 = balanced t2