COMP1100 excercises

-- Lab 8 Binary Tree
data Binary_Tree a = Null | Node {element :: a, left_tree, right_tree :: Binary_Tree a}
   deriving(Show, Eq)

size_of_tree :: Integral b => Binary_Tree a -> b
size_of_tree tree = case tree of
   Null                          -> 0
   (Node _ tree_left tree_right) -> 1 + size_of_tree tree_left + size_of_tree tree_right

depth_of_tree :: Integral b => Binary_Tree a -> b
depth_of_tree tree = case tree of
   Null                          -> 0
   (Node _ tree_left tree_right) -> 1 + max (depth_of_tree tree_left) (depth_of_tree tree_right)

flatten_tree :: Binary_Tree a -> [a]
flatten_tree tree = case tree of
   Null                                -> []
   (Node element tree_left tree_right) -> flatten_tree tree_left ++ [element] ++ flatten_tree tree_right

leaves_of_tree :: Binary_Tree a -> [a]
leaves_of_tree tree = case tree of
   Null                                -> []
   (Node element Null      Null)       -> [element]
   (Node element tree_left tree_right) -> leaves_of_tree tree_left ++ leaves_of_tree tree_right


-- Lab 8 Binary Tree higher
data Binary_Tree a = Null | Node {element :: a, left_tree, right_tree :: Binary_Tree a}
   deriving(Show, Eq)

size_of_tree :: Integral b => Binary_Tree a -> b
size_of_tree tree = case tree of
   Null                          -> 0
   (Node _ tree_left tree_right) -> 1 + size_of_tree tree_left + size_of_tree tree_right

depth_of_tree :: Integral b => Binary_Tree a -> b
depth_of_tree tree = case tree of
   Null                          -> 0
   (Node _ tree_left tree_right) -> 1 + max (depth_of_tree tree_left) (depth_of_tree tree_right)

flatten_tree :: Binary_Tree a -> [a]
flatten_tree tree = case tree of
   Null                                -> []
   (Node element tree_left tree_right) -> flatten_tree tree_left ++ [element] ++ flatten_tree tree_right

leaves_of_tree :: Binary_Tree a -> [a]
leaves_of_tree tree = case tree of
   Null                                -> []
   (Node element Null      Null)       -> [element]
   (Node element tree_left tree_right) -> leaves_of_tree tree_left ++ leaves_of_tree tree_right

map_function_over_binary_tree :: (a -> b) -> Binary_Tree a -> Binary_Tree b
map_function_over_binary_tree f tree = case tree of
   Null -> Null
   (Node elem l r) -> Node (f elem) (map_function_over_binary_tree f l) (map_function_over_binary_tree f r)

-- Lab 8 Binary Search Tree
import Data.List

data Binary_Tree a = Null | Node {element :: a, left_tree, right_tree :: Binary_Tree a}
   deriving(Show, Eq)
type BS_Tree a = Binary_Tree a


is_valid_binary_search_tree :: Ord a => BS_Tree a -> Bool
is_valid_binary_search_tree tree = flattened_tree == sort  flattened_tree
   where
      flattened_tree = flatten_in_order tree

flatten_in_order :: Ord a => BS_Tree a -> [a]
flatten_in_order tree = case tree of
   Null -> []
   (Node e l r) -> flatten_in_order l ++ [e] ++ flatten_in_order r

minimum_element :: Ord a => BS_Tree a -> a
minimum_element tree@(Node e _ _) = minimum_element_sub tree e
   where
      minimum_element_sub :: Ord a => BS_Tree a -> a -> a
      minimum_element_sub tree' min_elem = case tree' of
         Null -> min_elem
         (Node e' l _)
            | e' < min_elem   -> minimum_element_sub l e'
            | otherwise       -> minimum_element_sub l min_elem

maximum_element :: Ord a => BS_Tree a -> a
maximum_element tree@(Node e _ _) = maximum_element_sub tree e
   where
      maximum_element_sub :: Ord a => BS_Tree a -> a -> a
      maximum_element_sub tree' max_elem = case tree' of
         Null -> max_elem
         (Node e' _ r)
            | e' > max_elem   -> maximum_element_sub r e'
            | otherwise       -> maximum_element_sub r max_elem

contains_element :: Ord a => a -> BS_Tree a -> Bool
contains_element elem tree = case tree of
   Null -> False
   (Node e l r) -> case compare elem e of
      EQ -> True
      LT -> contains_element elem l
      GT -> contains_element elem r

insert_element_to_tree :: Ord a => a -> BS_Tree a -> BS_Tree a
insert_element_to_tree element tree = case tree of
   Null           -> Node element Null Null
   (Node e l r)   -> case compare element e of
      EQ -> Node e l r
      LT -> Node e (insert_element_to_tree element l) r
      GT -> Node e l (insert_element_to_tree element r)


-- Lab 8 Rose Tree
data Rose_Tree a = Rose_Node a [Rose_Tree a]
   deriving (Show, Eq)

size_of_tree :: Integral b => Rose_Tree a -> b
size_of_tree (Rose_Node _ nodes) = 1 + sum (map size_of_tree nodes)

depth_of_tree :: Integral b => Rose_Tree a -> b
depth_of_tree (Rose_Node _ nodes) = 1 + maximum (0 : (map depth_of_tree nodes))

leaves_of_tree :: Rose_Tree a -> [a]
leaves_of_tree (Rose_Node e nodes) = case nodes of
   [] -> [e]
   _  -> concatMap leaves_of_tree nodes

map_function_over_rose_tree :: (a -> b) -> Rose_Tree a -> Rose_Tree b
map_function_over_rose_tree f (Rose_Node e nodes) = Rose_Node (f e) (map (\x -> map_function_over_rose_tree f x) nodes)


-- Lab 8 Arithmetic Tree Expressions
data Expression a = Number a | Node (Expression a) Operand (Expression a)
   deriving (Show, Eq)
data Operand = Plus | Minus | Times | Divided_By | Power
   deriving (Show, Eq)


eval :: (Floating a, Eq a) => Expression a -> Expression a
eval expr = Number (eval_sub expr)
   where
      eval_sub :: (Floating a, Eq a) => Expression a -> a
      eval_sub expr = case expr of
         Number x -> x
         (Node expr_l op expr_r) -> case op of
            Plus        -> (eval_sub expr_l) + (eval_sub expr_r)
            Minus       -> (eval_sub expr_l) - (eval_sub expr_r)
            Times       -> (eval_sub expr_l) * (eval_sub expr_r)
            Divided_By
               | d == 0    -> error "Zero division!"
               | otherwise -> eval_sub expr_l / d
               where
                  d = eval_sub expr_r
            Power       -> (eval_sub expr_l) ** (eval_sub expr_r)


-- Lab 9 Higher order prime test
is_prime :: Integer -> Bool
is_prime num = num > 1 && (num == 2 || null (filter (\x -> num `mod` x == 0) [2 .. num - 1]))

prime_factors :: Integer -> [Integer]
prime_factors num
   | null factor || num < 2   = []
   | otherwise                = factor ++ prime_factors (num `div` (head factor))
   where
      factor = take 1 (filter (\x -> is_prime x && num `mod` x == 0) [2 .. num])


-- Lab 9 Higher order functions in use
import Data.Char

convert_to_lower :: String -> String
convert_to_lower str = map toLower str

remove_non_alphanum :: String -> String
remove_non_alphanum str = filter (`elem` (['a'..'z'] ++ ['A'..'Z'] ++ ['0' .. '9'])) str

dot_product :: [Integer] -> [Integer] -> Integer
dot_product l1 l2 = sum (zipWith (*) l1 l2)

is_Square :: Integral a => a -> Bool
is_Square i = floor ((sqrt (fromIntegral i) :: Float)) ^ (2 :: Integer) == i

sum_of_squares_up_to :: Integer -> Integer
sum_of_squares_up_to limit = sum (filter is_Square [1 .. limit])

largest_square_smaller_than :: Integer -> Integer
largest_square_smaller_than limit = last (filter (\x -> is_Square x && x < limit) [1 .. limit - 1])


-- Lab 9 Higher order functions polymorphic
apply_function_over_list' :: (a -> b) -> [a] -> [b]
apply_function_over_list' f list = case list of
   []       -> []
   x : xs   -> f x : apply_function_over_list' f xs

select_where_true' :: (a -> Bool) -> [a] -> [a]
select_where_true' f list = case list of
   [] -> []
   x : xs
      | f x       -> x : select_where_true' f xs
      | otherwise -> select_where_true' f xs

combine_lists_with_binary_operation :: (a -> b -> c) -> [a] -> [b] -> [c]
combine_lists_with_binary_operation f l1 l2 = case (l1, l2) of
   (x : xs, y : ys)  -> f x y : combine_lists_with_binary_operation f xs ys
   _                 -> []

combine_elements_into_tuples :: [a] -> [b] -> [(a, b)]
combine_elements_into_tuples l1 l2 = case (l1, l2) of
   (x : xs, y : ys)  -> (x, y) : combine_elements_into_tuples xs ys
   _                 -> []

combine_elements_into_tuples' :: [a] -> [b] -> [(a, b)]
combine_elements_into_tuples' l1 l2 = combine_lists_with_binary_operation (,) l1 l2


-- Lab 9 Higher order functions
apply_function :: (Integer -> Integer) -> Integer -> Integer
apply_function f num = f num

apply_function_over_list :: (Integer -> Integer) -> [Integer] -> [Integer]
apply_function_over_list f list = case list of
   []       -> []
   x : xs   -> f x : apply_function_over_list f xs

select_where_true :: (Double -> Bool) -> [Double] -> [Double]
select_where_true f list = case list of
   [] -> []
   x : xs
      | f x       -> x : select_where_true f xs
      | otherwise -> select_where_true f xs