commit ea73dfba73121876a33af1917fea85a2a149405e
parent e5197c60ea61983cce2cd379f6c82ffc0563d366
Author: Andrew Laack <andrew@laack.co>
Date: Thu, 20 Aug 2026 21:50:48 -0500
Finished end of section exercises
Diffstat:
| A | ch2/exercises.md | | | 368 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 368 insertions(+), 0 deletions(-)
diff --git a/ch2/exercises.md b/ch2/exercises.md
@@ -0,0 +1,368 @@
+1) What is the type and value of each of the following OCaml expressions?
+
+> 7 * (1 + 2 + 3)
+
+> "CS " ^ string_of_int 3110
+
+Answer:
+
+The type of the first expression, once evaluated, is int. The value is 42.
+
+The type of the second expression, once evaluated, is string. The value is "CS 3110".
+
+---
+
+
+2) Examine the table of all operators in the OCaml manual (you will have to scroll down to find it on that page).
+
+a) Write an expression that multiplies 42 by 10.
+b) Write an expression that divides 3.14 by 2.0. Hint: integer and floating-point operators are written differently in OCaml.
+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.
+
+Answer:
+
+
+a) 42 * 10
+b) 3.14 /. 2.0
+c)
+
+```ocaml
+
+let rec exp x pow =
+ if pow = 0 then 1 else x * exp x (pow - 1)
+in exp 42 7;;
+
+```
+
+---
+
+3) Exercise: equality
+
+a) Write an expression that compares 42 to 42 using structural equality.
+b) Write an expression that compares "hi" to "hi" using structural equality. What is the result?
+c) Write an expression that compares "hi" to "hi" using physical equality. What is the result?
+
+Answer:
+
+a) 42 = 42
+b) "hi" = "hi"
+ - true
+c) "hi" == "hi"
+ - false, not pointing to the same memory address
+
+---
+
+4) Exercise: assert
+
+a) Enter assert true;; into utop and see what happens.
+b) Enter assert false;; into utop and see what happens.
+c) Write an expression that asserts 2110 is not (structurally) equal to 3110.
+
+Answer:
+
+a) Returns a unit (continues execution)
+b) Raises an assertion failure exception
+c) assert (2110 != 3110)
+
+---
+
+Exercise: if
+
+4) Write an if expression that evaluates to 42 if 2 is greater than 1 and otherwise evaluates to 7.
+
+Answer:
+
+if 2 > 1 then 42 else 7;;
+
+---
+
+Exercise: double fun
+
+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.
+
+Answer:
+
+let double x = x *. 2.;;
+
+assert (double 10. = 20.);;
+assert (double 20. = 40.);;
+assert (double 45. = 90.);;
+assert (double (-20.) = (-40.));;
+
+---
+
+Exercise: more fun
+
+6)
+
+a) Define a function that computes the cube of a floating-point number. Test your function by applying it to a few inputs.
+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.
+c) Define a function that computes the area of a circle given its radius. Test your function with assert.
+
+Answer:
+
+a)
+
+```ocaml
+let cube x = x *. x *. x;;
+assert (cube 3. = 27.);;
+assert (cube 2. = 8.);;
+```
+
+b)
+
+
+```ocaml
+let sign x =
+ if x < 0 then -1
+ else if x == 0 then 0
+ else 1;;
+
+let () = assert (sign 0 = 0);;
+let () = assert (sign (-1) = (-1));;
+let () = assert (sign (-5) = (-1));;
+let () = assert (sign 1 = 1);;
+let () = assert (sign 5 = 1);;
+
+```
+
+c)
+
+```ocaml
+
+let area_of_circle r =
+ Float.pi *. r ** 2.;;
+
+assert (area_of_circle 1. = Float.pi);;
+
+```
+
+---
+
+Exercise: RMS
+
+7) Define a function that computes the root mean square of two numbers. Test your function with assert.
+
+This is sqrt((x^2 + y^2) / 2).
+
+(andrew: I'd assume this is asking for a function defined for floating point numbers)
+
+```ocaml
+let rms x y =
+ sqrt (((x ** 2.) +. (y ** 2.)) /. 2.);;
+
+assert (rms 40. 40. = 40.);;
+assert ((rms 10. 20. > 15.8) && (rms 10. 20. < 15.9));;
+
+```
+
+---
+
+Exercise: date fun
+
+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.
+
+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.
+
+
+Without matching:
+
+```ocaml
+
+let valid_month d m =
+ if d < 0 then false else
+ if m = "Jan" || m = "Mar" || m = "May" || m = "Jul" || m = "Aug" || m = "Oct" || m = "Dec"
+ then d <= 31
+ else if m = "Apr" || m = "Jun" || m = "Sep" || m = "Nov"
+ then d <= 30
+ else if m = "Feb" && d <= 28 then true else false;;
+
+assert (valid_month 28 "Aug");;
+assert (valid_month 1 "Aug");;
+assert (valid_month 31 "May");;
+assert (not (valid_month (-1) "May"));;
+assert (not (valid_month 32 "May"));;
+
+```
+
+With matching:
+
+```ocaml
+
+
+let valid_month d m =
+ match m with
+ | "Jan" | "Mar" | "May" | "Jul" | "Aug" | "Oct" | "Dec" -> d <= 31 && d >= 1
+ | "Apr" | "Jun" | "Sep" | "Nov" -> d <= 30 && d >= 1
+ | "Feb" -> d <= 28 && d >= 1
+ | _ -> false;;
+
+
+assert (valid_month 28 "Aug");;
+assert (valid_month 1 "Aug");;
+assert (valid_month 31 "May");;
+assert (not (valid_month (-1) "May"));;
+assert (not (valid_month 32 "May"));;
+
+```
+
+---
+
+
+Exercise: fib
+
+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:
+
+- fib 1 = 1,
+- fib 2 = 1, and
+- fib n = fib (n-1) + fib (n-2) for any n > 2.
+
+Test your function in the toplevel.
+
+Answer:
+
+(Without tail call recursion)
+
+```ocaml
+
+let fib x = if x < 1 then x else fib (x - 1) + fib (x - 2);;
+
+assert (fib 1 = 1);;
+assert (fib 2 = 1);;
+assert (fib 3 = 2);;
+assert (fib 4 = 3);;
+assert (fib 5 = 5);;
+assert (fib 6 = 8);;
+assert (fib 7 = 13);;
+```
+
+
+(With tail call recursion)
+
+```ocaml
+
+let fib x =
+ let rec go current prior_2 prior_1 =
+ if current >= x then prior_2 + prior_1
+ else go (current + 1) prior_1 (prior_2 + prior_1)
+ in if x = 0 then 0 else go 2 0 1;;
+
+assert (fib 1 = 1);;
+assert (fib 2 = 1);;
+assert (fib 3 = 2);;
+assert (fib 4 = 3);;
+assert (fib 5 = 5);;
+assert (fib 6 = 8);;
+assert (fib 7 = 13);;
+```
+
+---
+
+Exercise: fib fast
+
+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.
+
+What is the first value of n for which fib_fast n is negative, indicating that integer overflow occurred?
+
+Answer:
+
+Faster fib is tail call recursion.
+
+First value where n overflows is 8731 (found via manual binary search)
+
+---
+
+Exercise: poly types
+
+11) What is the type of each of the functions below? You can ask the toplevel to check your answers.
+
+a) let f x = if x then x else x
+b) let g x y = if y then x else x
+c) let h x y z = if x then y else z
+d) let i x y z = if x then y else y
+
+Answer:
+
+a) let f x = if x then x else x
+ - val f: bool -> bool = <fun>
+b) let g x y = if y then x else x
+ - val g: a' -> bool -> a' = <fun>
+c) let h x y z = if x then y else z
+ - val h: bool -> a' -> a' -> a' = <fun>
+ - ocaml requires returns to be the same type
+d) let i x y z = if x then y else y
+ - val i: bool -> a' -> b' -> a' = <fun>
+
+---
+
+12) Exercise: divide
+
+Write a function divide : numerator:float -> denominator:float -> float. Apply your function.
+
+Answer:
+
+```ocaml
+
+let divide ~numerator:x ~denominator:y = x /. y;;
+assert (divide ~numerator:4. ~denominator:2. = 2.);;
+assert (divide ~numerator:8. ~denominator:4. = 2.);;
+```
+
+---
+
+Exercise: associativity
+
+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.
+
+- add 5 1
+- add 5
+- (add 5) 1
+- add (5 1)
+
+Answer:
+
+- add 5 1
+ - this produces an integer
+- add 5
+ - this produces a function int -> int because it's been partially applied
+- (add 5) 1
+ - this produces an integer
+- add (5 1)
+ - this produces an error
+
+---
+
+Exercise: average
+
+14) Define an infix operator +/. to compute the average of two floating-point numbers. For example,
+
+- 1.0 +/. 2.0 = 1.5
+- 0. +/. 0. = 0.
+
+Answer
+
+
+```ocaml
+
+let (+/.) x y = (x +. y) /. 2.;;
+
+assert(1.0 +/. 2.0 = 1.5);;
+assert(0. +/. 0. = 0.);;
+
+```
+
+---
+
+
+15) Exercise: hello world
+
+Type the following in utop:
+
+- print_endline "Hello world!";;
+- print_string "Hello world!";;
+
+Notice the difference in output from each.
+
+Answer:
+
+Not a question, but endline includes a new line at the end while print string doesn't.
