exercises.md (8862B)
1 1) What is the type and value of each of the following OCaml expressions? 2 3 > 7 * (1 + 2 + 3) 4 5 > "CS " ^ string_of_int 3110 6 7 Answer: 8 9 The type of the first expression, once evaluated, is int. The value is 42. 10 11 The type of the second expression, once evaluated, is string. The value is "CS 3110". 12 13 --- 14 15 16 2) Examine the table of all operators in the OCaml manual (you will have to scroll down to find it on that page). 17 18 a) Write an expression that multiplies 42 by 10. 19 b) Write an expression that divides 3.14 by 2.0. Hint: integer and floating-point operators are written differently in OCaml. 20 c) Write an expression that computes 4.2 raised to the seventh power. Note: there is no built-in integer exponentiation operator in OCaml (nor is there in C, by the way), in part because it is not an operation provided by most CPUs. 21 22 Answer: 23 24 25 a) 42 * 10 26 b) 3.14 /. 2.0 27 c) 28 29 ```ocaml 30 31 let rec exp x pow = 32 if pow = 0 then 1 else x * exp x (pow - 1) 33 in exp 42 7;; 34 35 ``` 36 37 --- 38 39 3) Exercise: equality 40 41 a) Write an expression that compares 42 to 42 using structural equality. 42 b) Write an expression that compares "hi" to "hi" using structural equality. What is the result? 43 c) Write an expression that compares "hi" to "hi" using physical equality. What is the result? 44 45 Answer: 46 47 a) 42 = 42 48 b) "hi" = "hi" 49 - true 50 c) "hi" == "hi" 51 - false, not pointing to the same memory address 52 53 --- 54 55 4) Exercise: assert 56 57 a) Enter assert true;; into utop and see what happens. 58 b) Enter assert false;; into utop and see what happens. 59 c) Write an expression that asserts 2110 is not (structurally) equal to 3110. 60 61 Answer: 62 63 a) Returns a unit (continues execution) 64 b) Raises an assertion failure exception 65 c) assert (2110 != 3110) 66 67 --- 68 69 Exercise: if 70 71 4) Write an if expression that evaluates to 42 if 2 is greater than 1 and otherwise evaluates to 7. 72 73 Answer: 74 75 if 2 > 1 then 42 else 7;; 76 77 --- 78 79 Exercise: double fun 80 81 5) Using the increment function from above as a guide, define a function double that multiplies its input by 2. For example, double 7 would be 14. Test your function by applying it to a few inputs. Turn those test cases into assertions. 82 83 Answer: 84 85 let double x = x *. 2.;; 86 87 assert (double 10. = 20.);; 88 assert (double 20. = 40.);; 89 assert (double 45. = 90.);; 90 assert (double (-20.) = (-40.));; 91 92 --- 93 94 Exercise: more fun 95 96 6) 97 98 a) Define a function that computes the cube of a floating-point number. Test your function by applying it to a few inputs. 99 b) Define a function that computes the sign (1, 0, or -1) of an integer. Use a nested if expression. Test your function by applying it to a few inputs. 100 c) Define a function that computes the area of a circle given its radius. Test your function with assert. 101 102 Answer: 103 104 a) 105 106 ```ocaml 107 let cube x = x *. x *. x;; 108 assert (cube 3. = 27.);; 109 assert (cube 2. = 8.);; 110 ``` 111 112 b) 113 114 115 ```ocaml 116 let sign x = 117 if x < 0 then -1 118 else if x == 0 then 0 119 else 1;; 120 121 let () = assert (sign 0 = 0);; 122 let () = assert (sign (-1) = (-1));; 123 let () = assert (sign (-5) = (-1));; 124 let () = assert (sign 1 = 1);; 125 let () = assert (sign 5 = 1);; 126 127 ``` 128 129 c) 130 131 ```ocaml 132 133 let area_of_circle r = 134 Float.pi *. r ** 2.;; 135 136 assert (area_of_circle 1. = Float.pi);; 137 138 ``` 139 140 --- 141 142 Exercise: RMS 143 144 7) Define a function that computes the root mean square of two numbers. Test your function with assert. 145 146 This is sqrt((x^2 + y^2) / 2). 147 148 (andrew: I'd assume this is asking for a function defined for floating point numbers) 149 150 ```ocaml 151 let rms x y = 152 sqrt (((x ** 2.) +. (y ** 2.)) /. 2.);; 153 154 assert (rms 40. 40. = 40.);; 155 assert ((rms 10. 20. > 15.8) && (rms 10. 20. < 15.9));; 156 157 ``` 158 159 --- 160 161 Exercise: date fun 162 163 8) Define a function that takes an integer d and string m as input and returns true just when d and m form a valid date. Here, a valid date has a month that is one of the following abbreviations: Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sept, Oct, Nov, Dec. And the day must be a number that is between 1 and the minimum number of days in that month, inclusive. For example, if the month is Jan, then the day is between 1 and 31, inclusive, whereas if the month is Feb, then the day is between 1 and 28, inclusive. 164 165 How terse (i.e., few and short lines of code) can you make your function? You can definitely do this in fewer than 12 lines. 166 167 168 Without matching: 169 170 ```ocaml 171 172 let valid_month d m = 173 if d < 0 then false else 174 if m = "Jan" || m = "Mar" || m = "May" || m = "Jul" || m = "Aug" || m = "Oct" || m = "Dec" 175 then d <= 31 176 else if m = "Apr" || m = "Jun" || m = "Sep" || m = "Nov" 177 then d <= 30 178 else if m = "Feb" && d <= 28 then true else false;; 179 180 assert (valid_month 28 "Aug");; 181 assert (valid_month 1 "Aug");; 182 assert (valid_month 31 "May");; 183 assert (not (valid_month (-1) "May"));; 184 assert (not (valid_month 32 "May"));; 185 186 ``` 187 188 With matching: 189 190 ```ocaml 191 192 193 let valid_month d m = 194 match m with 195 | "Jan" | "Mar" | "May" | "Jul" | "Aug" | "Oct" | "Dec" -> d <= 31 && d >= 1 196 | "Apr" | "Jun" | "Sep" | "Nov" -> d <= 30 && d >= 1 197 | "Feb" -> d <= 28 && d >= 1 198 | _ -> false;; 199 200 201 assert (valid_month 28 "Aug");; 202 assert (valid_month 1 "Aug");; 203 assert (valid_month 31 "May");; 204 assert (not (valid_month (-1) "May"));; 205 assert (not (valid_month 32 "May"));; 206 207 ``` 208 209 --- 210 211 212 Exercise: fib 213 214 9) Define a recursive function fib : int -> int, such that fib n is the nth number in the Fibonacci sequence, which is 1, 1, 2, 3, 5, 8, 13, … That is: 215 216 - fib 1 = 1, 217 - fib 2 = 1, and 218 - fib n = fib (n-1) + fib (n-2) for any n > 2. 219 220 Test your function in the toplevel. 221 222 Answer: 223 224 (Without tail call recursion) 225 226 ```ocaml 227 228 let fib x = if x < 1 then x else fib (x - 1) + fib (x - 2);; 229 230 assert (fib 1 = 1);; 231 assert (fib 2 = 1);; 232 assert (fib 3 = 2);; 233 assert (fib 4 = 3);; 234 assert (fib 5 = 5);; 235 assert (fib 6 = 8);; 236 assert (fib 7 = 13);; 237 ``` 238 239 240 (With tail call recursion) 241 242 ```ocaml 243 244 let fib x = 245 let rec go current prior_2 prior_1 = 246 if current >= x then prior_2 + prior_1 247 else go (current + 1) prior_1 (prior_2 + prior_1) 248 in if x = 0 then 0 else go 2 0 1;; 249 250 assert (fib 1 = 1);; 251 assert (fib 2 = 1);; 252 assert (fib 3 = 2);; 253 assert (fib 4 = 3);; 254 assert (fib 5 = 5);; 255 assert (fib 6 = 8);; 256 assert (fib 7 = 13);; 257 ``` 258 259 --- 260 261 Exercise: fib fast 262 263 10) How quickly does your implementation of fib compute the 50th Fibonacci number? If it computes nearly instantaneously, congratulations! But the recursive solution most people come up with at first will seem to hang indefinitely. The problem is that the obvious solution computes subproblems repeatedly. For example, computing fib 5 requires computing both fib 3 and fib 4, and if those are computed separately, a lot of work (an exponential amount, in fact) is being redone. 264 265 What is the first value of n for which fib_fast n is negative, indicating that integer overflow occurred? 266 267 Answer: 268 269 Faster fib is tail call recursion. 270 271 First value where n overflows is 8731 (found via manual binary search) 272 273 --- 274 275 Exercise: poly types 276 277 11) What is the type of each of the functions below? You can ask the toplevel to check your answers. 278 279 a) let f x = if x then x else x 280 b) let g x y = if y then x else x 281 c) let h x y z = if x then y else z 282 d) let i x y z = if x then y else y 283 284 Answer: 285 286 a) let f x = if x then x else x 287 - val f: bool -> bool = <fun> 288 b) let g x y = if y then x else x 289 - val g: a' -> bool -> a' = <fun> 290 c) let h x y z = if x then y else z 291 - val h: bool -> a' -> a' -> a' = <fun> 292 - ocaml requires returns to be the same type 293 d) let i x y z = if x then y else y 294 - val i: bool -> a' -> b' -> a' = <fun> 295 296 --- 297 298 12) Exercise: divide 299 300 Write a function divide : numerator:float -> denominator:float -> float. Apply your function. 301 302 Answer: 303 304 ```ocaml 305 306 let divide ~numerator:x ~denominator:y = x /. y;; 307 assert (divide ~numerator:4. ~denominator:2. = 2.);; 308 assert (divide ~numerator:8. ~denominator:4. = 2.);; 309 ``` 310 311 --- 312 313 Exercise: associativity 314 315 13) Suppose that we have defined let add x y = x + y. Which of the following produces an integer, which produces a function, and which produces an error? Decide on an answer, then check your answer in the toplevel. 316 317 - add 5 1 318 - add 5 319 - (add 5) 1 320 - add (5 1) 321 322 Answer: 323 324 - add 5 1 325 - this produces an integer 326 - add 5 327 - this produces a function int -> int because it's been partially applied 328 - (add 5) 1 329 - this produces an integer 330 - add (5 1) 331 - this produces an error 332 333 --- 334 335 Exercise: average 336 337 14) Define an infix operator +/. to compute the average of two floating-point numbers. For example, 338 339 - 1.0 +/. 2.0 = 1.5 340 - 0. +/. 0. = 0. 341 342 Answer 343 344 345 ```ocaml 346 347 let (+/.) x y = (x +. y) /. 2.;; 348 349 assert(1.0 +/. 2.0 = 1.5);; 350 assert(0. +/. 0. = 0.);; 351 352 ``` 353 354 --- 355 356 357 15) Exercise: hello world 358 359 Type the following in utop: 360 361 - print_endline "Hello world!";; 362 - print_string "Hello world!";; 363 364 Notice the difference in output from each. 365 366 Answer: 367 368 Not a question, but endline includes a new line at the end while print string doesn't.