Ctrl+K

Exercises

2.9. Exercises#

Solutions to most exercises are available. Fall 2022 is the first public release of these solutions. Though they have been available to Cornell students for a few years, it is inevitable that wider circulation will reveal improvements that could be made. We are happy to add or correct solutions. Please make contributions through GitHub.

Exercise: values [★]

What is the type and value of each of the following OCaml expressions?

  • 7 * (1 + 2 + 3)

  • "CS " ^ string_of_int 3110

Hint: type each expression into the toplevel and it will tell you the answer. Note: ^ is not exponentiation.

Exercise: operators [★★]

Examine the table of all operators in the OCaml manual (you will have to scroll down to find it on that page).

  • Write an expression that multiplies 42 by 10.

  • Write an expression that divides 3.14 by 2.0. Hint: integer and floating-point operators are written differently in OCaml.

  • 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.

Exercise: equality [★]

  • Write an expression that compares 42 to 42 using structural equality.

  • Write an expression that compares "hi" to "hi" using structural equality. What is the result?

  • Write an expression that compares "hi" to "hi" using physical equality. What is the result?

Exercise: assert [★]

  • Enter assert true;; into utop and see what happens.

  • Enter assert false;; into utop and see what happens.

  • Write an expression that asserts 2110 is not (structurally) equal to 3110.

Exercise: if [★]

Write an if expression that evaluates to 42 if 2 is greater than 1 and otherwise evaluates to 7.

Exercise: double fun [★]

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.

Exercise: more fun [★★]

  • Define a function that computes the cube of a floating-point number. Test your function by applying it to a few inputs.

  • 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.

  • Define a function that computes the area of a circle given its radius. Test your function with assert.

For the latter, bear in mind that floating-point arithmetic is not exact. Instead of asserting an exact value, you should assert that the result is “close enough”, e.g., within 1e-5. If that’s unfamiliar to you, it would be worthwhile to read up on floating-point arithmetic.

A function that take multiple inputs can be defined just by providing additional names for those inputs as part of the let definition. For example, the following function computes the average of three arguments:

let avg3 x y z = (x +. y +. z) /. 3.

Exercise: RMS [★★]

Define a function that computes the root mean square of two numbers—i.e., \(\sqrt{(x^2 + y^2) / 2}\). Test your function with assert.

Exercise: date fun [★★★]

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.

Exercise: fib [★★]

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.

Exercise: fib fast [★★★]

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.

Create a function fib_fast that requires only a linear amount of work. Hint: write a recursive helper function h : int -> int -> int -> int, where h n pp p is defined as follows:

  • h 1 pp p = p, and

  • h n pp p = h (n-1) p (pp+p) for any n > 1.

The idea of h is that it assumes the previous two Fibonacci numbers were pp and p, then computes forward n more numbers. Hence, fib n = h n 0 1 for any n > 0.

What is the first value of n for which fib_fast n is negative, indicating that integer overflow occurred?

Exercise: poly types [★★★]

What is the type of each of the functions below? You can ask the toplevel to check your answers.

let f x = if x then x else x
let g x y = if y then x else x
let h x y z = if x then y else z
let i x y z = if x then y else y

Exercise: divide [★★]

Write a function divide : numerator:float -> denominator:float -> float. Apply your function.

Exercise: associativity [★★]

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)

Exercise: average [★★]

Define an infix operator +/. to compute the average of two floating-point numbers. For example,

  • 1.0 +/. 2.0 = 1.5

  • 0. +/. 0. = 0.

Exercise: hello world [★]

Type the following in utop:

  • print_endline "Hello world!";;

  • print_string "Hello world!";;

Notice the difference in output from each.