• API
• FAQ
• Tools
• Archive
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.
Top