module Lab09 where

{- EXERCISES -}

data BinTree a = Leaf a | Node (BinTree a) (BinTree a)

tree = Node (Node (Leaf 'a') (Node (Leaf 'b') (Leaf 'c'))) (Leaf 'd')

instance (Show a) => Show (BinTree a) where
  show (Leaf a) = "<Leaf " ++ show a ++ "/>"
  show (Node l r) = "<Node>" ++ show l ++ show r ++ "</Node>"

-- >>> tree
-- <Node><Node><Leaf 'a'/><Node><Leaf 'b'/><Leaf 'c'/></Node></Node><Leaf 'd'/></Node>

treeDepth :: BinTree a -> Int
treeDepth (Leaf _) = 1
treeDepth (Node l r) = 1 + max (treeDepth l) (treeDepth r)

-- >>> treeDepth tree
-- 4

labelTree :: BinTree a -> BinTree (a, Int)
labelTree t = fst (go 0 t)
  where go :: Int -> BinTree a -> (BinTree (a, Int), Int)
        go n (Leaf a) = (Leaf (a, n), n + 1)
        go n (Node l r) = let (newLeft, n') = go n l
                              (newRight, n'') = go n' r
                          in (Node newLeft newRight, n'')

-- >>> labelTree tree
-- <Node><Node><Leaf ('a',0)/><Node><Leaf ('b',1)/><Leaf ('c',2)/></Node></Node><Leaf ('d',3)/></Node>

{- TASKS -}

type Monomial a = (a, Int)

data Polynomial a = Null | Pol (Monomial a) (Polynomial a)

format :: (Show a, Ord a, Num a) => Monomial a -> String
format (a, deg) = let coeff
                        | a < 0 = "(" ++ show a ++ ")"
                        | otherwise = show a
                  in if deg == 0
                     then coeff
                     else coeff ++ "*x^" ++ show deg

instance (Show a, Ord a, Num a) => Show (Polynomial a) where
  show Null = "0"
  show (Pol m Null) = format m
  show (Pol m p) = format m ++ " + " ++ show p

pol = Pol (-1, 0) (Pol (-2, 1) (Pol (1, 3) Null))

-- >>> pol
-- (-1) + (-2)*x^1 + 1*x^3

getDegree :: Polynomial a -> Int
getDegree Null = -1
getDegree (Pol (_, deg) p) = max deg (getDegree p)

-- >>> getDegree pol
-- 3