SHARE
TWEET

Untitled

a guest Feb 26th, 2020 98 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. -- Question 1
  2.  
  3. data Tree a = Node a (Tree a) (Tree a)
  4.  
  5.   | Leaf
  6.  
  7.  
  8.  
  9. instance Eq a => Eq (Tree a) where
  10.  
  11.   Leaf == Leaf = True
  12.  
  13.   (Node val left right) == Leaf = False
  14.  
  15.   Leaf == (Node val left right) = False
  16.  
  17.   (Node val1 left1 right1) == (Node val2 left2 right2) =
  18.  
  19.     case val1 == val2 of
  20.  
  21.       True -> left1 == left2 && right1 == right2
  22.  
  23.       _ -> False
  24.  
  25.  
  26.  
  27. -- Question 2
  28.  
  29. instance Functor Tree where
  30.  
  31.   fmap f Leaf = Leaf
  32.  
  33.   fmap f (Node val left right) =
  34.  
  35.     (Node (f val) (fmap f left) (fmap f right) )
  36.  
  37.  
  38.  
  39. --Question 3
  40.  
  41. bstInsert :: Ord a => Tree (a, Int) ->  a -> Tree (a, Int)
  42.  
  43. bstInsert Leaf n = (Node (n, 1) Leaf Leaf)
  44.  
  45. bstInsert (Node (val, num) left right) n =
  46.  
  47.   case compare n val of
  48.  
  49.     GT -> case right of
  50.  
  51.       Leaf -> (Node (val, num) left (Node (n,1) Leaf Leaf))
  52.  
  53.       _ -> (Node (val,num) left (bstInsert right n))
  54.  
  55.     LT -> case left of
  56.  
  57.       Leaf -> (Node (val, num) (Node (n, 1) Leaf Leaf) right)
  58.  
  59.       _ -> (Node (val,num) (bstInsert left n) right)
  60.  
  61.     _ -> (Node (val, num+1) left right)
  62.  
  63.      
  64.  
  65. --Question 4
  66.  
  67. bstLookup :: Ord a => Tree (a, Int) -> a -> Int
  68.  
  69. bstLookup Leaf n = 0
  70.  
  71. bstLookup (Node (val, num) left right) n =
  72.  
  73.   case compare n val of
  74.  
  75.     GT -> bstLookup right n
  76.  
  77.     LT -> bstLookup left n
  78.  
  79.     _ -> num
  80.  
  81.  
  82.  
  83. --Question 5
  84.  
  85.  
  86.  
  87. bstRemove :: Ord a=> Tree (a, Int) -> a -> Maybe (Tree (a,Int))
  88.  
  89. bstRemove Leaf n = Nothing
  90.  
  91.  
  92.  
  93. bstRemove (Node (val, num) left right) n =
  94.  
  95.   case compare n val of
  96.  
  97.     GT -> case (bstRemove right n) of
  98.  
  99.       Nothing -> Nothing
  100.  
  101.       Just removeR -> Just (Node (val,num) left removeR)
  102.  
  103.     LT -> case (bstRemove left n) of
  104.  
  105.       Nothing -> Nothing
  106.  
  107.       Just removeL -> Just (Node (val,num) removeL right)
  108.  
  109.     _ -> case num > 1 of
  110.  
  111.       True -> Just (Node (val, num-1) left right)
  112.  
  113.       _ -> case (Node (val,num) left right) of
  114.  
  115.         (Node (val,num) Leaf Leaf) -> Just Leaf
  116.  
  117.         (Node (val,num) left Leaf) -> Just left
  118.  
  119.         (Node (val,num) Leaf right) -> Just right
  120.  
  121.         _ -> let mini = bstFindMin right in
  122.  
  123.           case (bstRemove right mini) of
  124.  
  125.           Just removeR ->Just (Node (mini, (bstLookup right mini) ) left removeR)
  126.  
  127.           _ -> Nothing
  128.  
  129.          
  130.  
  131.        
  132.  
  133.  
  134.  
  135.  
  136.  
  137. bstFindMin :: Ord a => Tree(a,Int) -> a
  138.  
  139. bstFindMin (Node (val, num) left right) =
  140.  
  141.   case left of
  142.  
  143.     Leaf -> val
  144.  
  145.     _ -> bstFindMin left
  146.  
  147.  
  148.  
  149. --Question 6
  150.  
  151. instance Show a => Show (Tree a) where
  152.  
  153.   show Leaf = "Leaf"
  154.  
  155.   show myTree =
  156.  
  157.     myShow 0 myTree
  158.  
  159.  
  160.  
  161.  
  162.  
  163. myShow :: Show a => Int -> Tree a -> String
  164.  
  165. myShow n Leaf = ""
  166.  
  167. myShow 0 (Node val left right) =
  168.  
  169.   "Node " ++ show val ++ "\n" ++ (myShow 2 left) ++ (myShow 2 right)
  170.  
  171. myShow n (Node val left right) =
  172.  
  173.   (stringMultiply " " n) ++ "Node " ++ show val ++ "\n" ++ (myShow (n+2) left) ++ (myShow(n+2) right)
  174.  
  175.  
  176.  
  177.  
  178.  
  179. stringMultiply :: String -> Int -> String
  180.  
  181. stringMultiply s 0 = ""
  182.  
  183. stringMultiply s n = s ++ stringMultiply s (n-1)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top