data Nat = Zero
         | Succ Nat deriving ( Show, Read )
{- Zero
 - Succ Zero
 - Succ (Succ (Succ (Succ (Succ (Succ Zero)))))
 -}

natToInt :: Nat -> Integer
natToInt Zero     = 0
natToInt (Succ x) = 1 + natToInt x

-- natToInt (Succ (Succ (Succ Zero))) ~> 1 + natToInt (Succ (Succ Zero)) ~> 1 + 1 + natToInt (Succ Zero) ~> 1 + 1 + 1 + natToInt Zero ~> 1 + 1 + 1 + 0

plusNat :: Nat -> Nat -> Nat
plusNat Zero x = x
plusNat x Zero = x
-- plusNat (Succ x) y = Succ (plusNat x y)
plusNat (Succ x) y = plusNat x (Succ y)

-- plusNat (Succ Zero) (Succ Zero) ~> plusNat Zero (Succ (Succ Zero)) ~> Succ (Succ Zero)

nfold :: (a -> a) -> a -> Nat -> a
nfold f x Zero     = x
nfold f x (Succ n) = f (nfold f x n)

natToInt' = nfold (1+) 0

double :: Nat -> Nat
double = nfold (Succ . Succ) Zero


data Expr = Con Double
          | Add Expr Expr
          | Sub Expr Expr 
          | Mul Expr Expr
          | Div Expr Expr
          deriving ( Show, Read, Eq )

{- Con 4
 - Add (Con 5) (Con 3)
 - Add (Mul (Con 2) (Con 3)) (Sub (Con 5) (Con 1))
 -}

eval :: Expr -> Double
eval = undefined

{-
data Maybe a = Nothing
             | Just a
             deriving ( Show, Read, Eq, Ord )
-}

evaluate :: Expr -> Maybe Double
evaluate (Con x) = Just x
evaluate (Add x y) = addHelper (evaluate x) (evaluate y)
  where
    addHelper (Just a) (Just b) = Just (a + b)
    addHelper _        _        = Nothing
evaluate (Sub x y) = subHelper (evaluate x) (evaluate y)
  where
    subHelper (Just a) (Just b) = Just (a - b)
    subHelper _        _        = Nothing
evaluate (Mul x y) = case (evaluate x, evaluate y) of
                      (Just a, Just b) -> Just (a * b)
                      _                -> Nothing
evaluate (Div x y) = divHelper (evaluate x) (evaluate y)
  where
    divHelper (Just a) (Just 0) = Nothing
    divHelper (Just a) (Just b) = Just (a / b)
    divHelper _        _        = Nothing

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

{-
Empty
Node 1 Empty Empty
Node 1 (Node 2 Empty Empty) (Node 3 Empty (Node 4 Empty Empty))
-}

size :: BinTree a -> Integer
size Empty = 0
size (Node _ l r) = 1 + size l + size r


-- height Empty ~> 0
-- height (Node () Empty (Node () Empty Empty)) ~> 2
height :: BinTree a -> Integer
height Empty = 0
height (Node _ l r) = 1 + max (height l) (height r)

-- fulltree 0 () ~> Empty
-- fulltree 2 () ~> (Node () (Node () Empty Empty) (Node () Empty Empty)
fulltree :: Integer -> a -> BinTree a
fulltree 0 _ = Empty
fulltree n x = Node x (fulltree (n - 1) x) (fulltree (n - 1) x)

treetake :: Integer -> BinTree a -> BinTree a
treetake _ Empty = Empty
treetake 0 _     = Empty
treetake n (Node x l r) = Node x (treetake (n-1) l) (treetake (n-1) r)

treerepeat :: a -> BinTree a
treerepeat x = Node x (treerepeat x) (treerepeat x)

treeiterate :: (a -> a) -> (a -> a) -> a -> BinTree a
treeiterate = undefined

treezip :: BinTree a -> BinTree b -> BinTree (a, b)
treezip = undefined