Homework 4 (Due: 8 November (Sunday))

1. (Date) Complete the definition of the functions that operate on a Date type.

   data Date = Date 
     { month :: Int, 
       day   :: Int,
       year  :: Int
     } 
     deriving (Show, Eq)
   
   -- Note to pattern match a Date value you can use the pattern (Date m d y)
   -- the field names, month, day, and year act like functions; so
   -- month (Date 10 28 1958) = 10
   -- day (Date 10 28 1958) = 28
   -- year (Date 10 28 1958) = 1958
   -- To solve this problem, you may not need these three functions. You can simply use different
   -- variable names in the pattern and access the fields with these variable names.
   
   -- Every year that is exactly divisible by four is a leap year, 
   -- except for years that are exactly divisible by 100, but these 
   -- centurial years are leap years if they are exactly divisible 
   -- by 400. For example, the years 1700, 1800, and 1900 are not 
   -- leap years, but the years 1600 and 2000 are
   
   -- returns True if given date is a leap year; false otherwise
   leapYear :: Date -> Bool
   ???
   
   -- returns date of next day for a given date
   tomorrow :: Date -> Date
   ???
   
   -- returns date of previous day for a given date
   yesterday :: Date -> Date
   ???
   
   -- returns date of 1st of next month for a given date
   firstOfNextMonth :: Date -> Date
   ???
   
   -- returns date of 1st of previous month for a given date
   firstOfPreviousMonth :: Date -> Date
   ???
   
   -- Given a positive integer, n, and a date, d, returns the
   -- date for n days after d
   add :: Int -> Date -> Date
   ???
   
   -- Given a positive integer, n, and a date, d, returns the
   -- date for n days before d
   sub :: Int -> Date -> Date
   ???
   
   -- Given two input dates, d1 and d2, returns True if d1 is after d2; False otherwise
   (>>>) :: Date -> Date -> Bool
   ???
   
   -- Given two input dates, d1 and d2, returns True if d1 is same as d2; False otherwise
   (===) :: Date -> Date -> Bool
   ???
   
   -- Given two input dates, d1 and d2, returns True if d1 is before d2; False otherwise
   (<<<) :: Date -> Date -> Bool
   ???
   
   -- Given two dates, returns number of days between the two dates
   daysBetween :: Date -> Date -> Int
   ???
   

2. (Binary Search Tree) Complete the definition of the functions that operate on a Binary Search Tree type.

   data BST a = Nil | Tree a (BST a) (BST a) deriving Show
   
   -- Returns number of nodes in the input tree
   sizeBST :: BST Int -> Int
   ???
   
   -- Returns height of input tree (height=length of longest path from root to leaf
   heightBST :: BST Int -> Int
   ???
   
   -- Returns smallest element in tree; returns (maxBound::Int) if input tree is empty
   minBST :: BST Int -> Int
   ???
   
   -- Returns largest element in tree; returns (minBound::Int) if input tree is empty
   maxBST :: BST Int -> Int
   ???
   
   -- given a number and a BST returns True if number in BST; False otherwise
   memberBST :: Int -> BST Int -> Bool
   
   -- Given a number and a BST, returns the new tree obtained by inserting number in BST
   -- If number already exists in BST then return same tree
   insertBST :: Int -> BST Int -> BST Int
   
   -- Given a number and a BST, returns the new tree obtained by deleting number from BST
   -- If number does not exist in BST then return same tree
   deleteBST :: Int -> BST Int -> BST Int
   
   toString:: BST Int -> Int -> String
   toString t n = case t of
     Nil                 -> "Nil\n" 
     (Tree x left right) -> replicate n ' ' ++ show x ++ "\n" ++ 
                            toString left  (n+2) ++ 
                            toString right (n+2)
   

What to Submit?

• date.hs
• bst.hs