Homework 5 (Due: 22 November (Sunday))

1. (Binary Search Tree) Update Homework 4 Solution to use the "Maybe" monad to catch runtime exceptions in some of the functions. Here are the updated function signatures (only minBST, maxBST, and deleteBST have changed). I also updated the toString function.

   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 Nothing if input tree is empty
   minBST :: BST Int -> Maybe Int
   ???
   
   -- Returns largest element in tree; returns Nothing if input tree is empty
   maxBST :: BST Int -> Maybe 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 Nothing
   deleteBST :: Int -> BST Int -> Maybe (BST Int)
   ???
   
   toStringM :: Maybe (BST Int) -> String
   toStringM Nothing  = "Something strange has taken place!"
   toStringM (Just t) = toString t 0
   
   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)
   

2. Using the functions from Homework 3 problem of Bulls and Cows, build an interactive game in Haskell that runs as follows:

   $ ghci bulls.hs
   ghci> main
   Welcome to the game of BULLS and COWS.
   The objective in this game is for you to guess a 4-digit number
   The computer responds with how close your guess is to the target
   BULLS = # common digits with exact matches and
   COWS  = # common digits in wrong position.
   
   Enter guess number 1: 1876
   Bulls =  1   Cows =  1
   Enter guess number 2: 1183
   Your guess should not contain repeating digits
   Enter guess number 2: 1596
   Bulls =  1   Cows =  2
   Enter guess number 3: 1956
   Bulls =  3   Cows =  0
   Enter guess number 4: 1954
   Bulls =  3   Cows =  0
   Enter guess number 5: 1958
   Bulls =  4   Cows =  0
   Congratulations You Won!!
   
   $ ghci bulls.hs
   ghci> main
   
   Welcome to the game of BULLS and COWS.
   The objective in this game is for you to guess a 4-digit number
   The computer responds with how close your guess is to the target
   BULLS = # common digits with exact matches and
   COWS  = # common digits in wrong position.
   
   Enter guess number 1: 1234
   Bulls =  0   Cows =  1
   Enter guess number 2: 2345
   Bulls =  0   Cows =  0
   Enter guess number 3: 1678
   Bulls =  0   Cows =  3
   Enter guess number 4: 1679
   Bulls =  0   Cows =  3
   Enter guess number 5: 1670
   Bulls =  0   Cows =  4
   Enter guess number 6: 6170
   Bulls =  0   Cows =  4
   Enter guess number 7: 6710
   Bulls =  1   Cows =  3
   Enter guess number 8: 7610
   Bulls =  2   Cows =  2
   Enter guess number 9: 7601
   Bulls =  1   Cows =  3
   Enter guess number 10: 6701
   Bulls =  0   Cows =  4
   Sorry You ran out of guesses!!
   The correct number was:  7016
   

   You will have to use the IO monad to do input/output from console. Also, since getting the Random Number library is a bit tricky in Haskell, you may simply read the 4-digit target from keyboard (do not echo it similar to hangman example we discussed in class). I have not shown that part of the interaction in the above runs.

What to Submit?

• bst.hs
• bulls.hs