(Week 10 programming: exercises of week 9)

Question 1

Implement subtraction for Peano numbers. The function needs to be tail-recursive.

type nat = Zero | Suc of nat;;
val sub : nat -> nat -> nat = <fun>
# sub (Suc Zero) Zero ;;
- : nat = Suc Zero
# sub (Suc (Suc Zero)) (Suc Zero);;
- : nat = Suc Zero
# sub Zero (Suc Zero);;
Exception: Failure "sub".

Question 2

Using OCaml’s rational numbers library Num write a general purpose arbitrary precision root-finding function using any algorithm you choose (e.g. bisection or secant).

The function root : (Num.num -> Num.num) -> Num.num -> Num.num -> Num.num -> Num.num should take the following arguments:

f : Num.num -> Num.num is the function expressing the equation a : Num.num is the left endpoint of the interval where the root lies b : Num.num is the right endpoint of the interval err : Num.num is the margin of error we can tolerate

The function root should return a root r : Num.num that lies within the interval (r-err, r+err).

Note: The library Num is not loaded into the OCaml top-level. To load it you need to execute the following top-level commands:

# #use "topfind";;
# #require "num";;
# open Num;;

Here is an example usage of the function root to find solutions to the equation (x-4)*(x-6)=0 with error 1/100 then with error 1/1000:

val root : (Num.num -> Num.num) -> Num.num -> Num.num -> Num.num -> Num.num = <fun>
# let r0 = num_of_int 4;;
val r0 : Num.num = <num 4>
# let r1 = num_of_int 6;;
val r1 : Num.num = <num 6>
# let f x = (x -/ r0) */ (x -/ r1) ;;
val f : Num.num -> Num.num = <fun>
# root f (num_of_int 5) (num_of_int 8) (num_of_int 1 // num_of_int 100);;
- : Num.num = <num 5123/1024>
# root f (num_of_int 5) (num_of_int 8) (num_of_int 1 // num_of_int 1000);;
- : Num.num = <num 40963/8192>

Question 3

Given a list of native int values correctly calculate its sum. If there is an order in which the elements can be added so that there is no overflow, that order is used. For example the sum of the list [max_int, max_int, -max_int] should be Some max_int. In case of unavoidable overflow the function should return None.

Note: You are not allowed to use any arbitrary precision library but, for efficiency, you must operate directly on the native int type of OCaml.

val add : int list -> int option = <fun>
# let m = max_int;;
val m : int = 4611686018427387903
# let _ = add [m; -1; -m; 2; -m; 8; 9; m];;
- : int option = Some 18
# let _ = add [m; 1; m; -5];;
- : int option = None