Description
There are 4 questions to be solved on the LearnOCaml system. The assignment is due at 3pm.
Extensions are not possible for any reason.
[Question 1:20 points] In this question we work with polymorphic trees
type ’a tree = Empty  Node of ’a tree * ’a * ’a tree;;
Write a function mapTree that takes a function and a tree and applies the function to every node of the tree. Here is the type

let rec mapTree f (t: ’a tree) = ….
val mapTree : (’a > ’b) > ’a tree > ’b tree = <fun>
Here is an example

let t1 = Node(Empty, 0, (Node(Empty, 1, Empty)));; let t2 = Node(Node(Empty,5,Empty),6,Empty);;
let t3 = Node(Node(t2,2,Node(Empty,3,Empty)),4,t1);;

t3;;

: int tree = Node
(Node (Node (Node (Empty, 5, Empty), 6, Empty), 2, Node (Empty, 3, Empty)), 4, Node (Empty, 0, Node (Empty, 1, Empty)))
# mapTree (fun x > x + 1) t3;;

: int tree =
Node
(Node (Node (Node (Empty, 6, Empty), 7, Empty), 3, Node (Empty, 4, Empty)), 5, Node (Empty, 1, Node (Empty, 2, Empty)))
[Question 2:40 points] Suppose that f : R ! R is a continuous function from the real numbers to the real numbers. Suppose further that there is an interval [a; b] in which the function is known to have exactly one root^{1}. We will assume that^{2} f(a) < 0 and f(b) > 0 and the root r is
^{1}The root of a function f is a value r such that f(r) = 0.
^{2}When I am writing mathematical statements I do not bother to write 0:0; when I am writing code I am careful
to distinguish between 0 and 0:0.
1
somewhere in between. There is an algorithm that is reminiscent of binary search that nds (a good approximation of) the root. The halfinterval method for nding the root of a realvalued function works as follows. The idea is to search for the root by rst guessing that the root is the midpoint of the interval. If the midpoint is the root we are done. If not, we check whether the value of f at the midpoint is positive or negative. If it is positive then the root must be between a and the midpoint; if it is negative, the root must be between the midpoint and b. In either case we recursively call the search algorithm. Code this algorithm in OCaml. The following shows the names and types that we expect.

let rec halfint((f: float > float),(epsilon:float)) ((posValue:float),(negValue:float)) = ….
val halfint : (float > float) * float * float * float > float = <fun>
The parameter epsilon is used to determine the accuracy with which you are making comparisons. Recall that you cannot reliably test oatingpoint numbers for equality. You may use the function abs float as a helper. It is the oating point version of absolute value.
[Question 3:30 points] This is a classic example of a higherorder function in action. Newton’s method can be used to generate approximate solutions to the equation f(x) = 0 where f is a di erentiable realvalued function of the real variable x. The idea can be summarized as follows:
Suppose that x_{0} is some point which we suspect is near a solution. We can form the linear approximation l at x_{0} and solve the linear equation for a new approximate solution. Let x_{1} be the solution to the linear approximation l(x) = f(x_{0}) + f^{0} (x_{0})(x x_{0}) = 0. In other words,

f(x_{0}) + f^{0} (x_{0})(x_{1}
x_{0}) = 0
x_{1}
x_{0}
=
f(x_{0})
f^{0} (x_{0})
x_{1}
= x_{0}
f(x_{0})
f^{0} (x_{0})
If our rst guess x_{0} was a good one, then the approximate solution x_{1} should be an even better approximation to the solution of f(x) = 0. Once we have x_{1}, we can repeat the process to obtain x_{2}, etc. In fact, we can repeat this process inde nitely: if, after n steps, we have an approximate solution x_{n}, then the next step is
f(x_{n})
^{x}^{n+1} ^{= }^{x}^{n} _{f}0 _{(x}_{n}_{)}^{:}
This will produce approximate solutions to any degree of accuracy provided we have started with a good guess x_{0}. If we have reached a value x_{n} such that jf(x_{n})j < “, where ” is some real number representing the tolerance, we will stop.
Implement a function called newton with the type shown below. The code outline is for your guidance.

let rec newton(f, (epsilon:float), (dx:float)) (guess:float) =
let close((x:float), (y:float), (epsilon:float)) = absFl(x.y) < epsilon in let improve((guess:float),f,(dx:float)) = …. in
if close((f guess), 0.0, epsilon)
2
then
guess
else
….
val newton : (float > float) * float * float * float > float = <fun>
which when given a function f, a guess x_{0}, a tolerance ” and an interval dx, will compute a value x^{0} such that jf(x^{0} )j < “. You can test this on builtin realvalued functions like sin or other functions in the mathematics library. Please note that this method does not always work: one needs stronger conditions on f to guarantee convergence of the approximation scheme. Never test it on tan! Here are two examples:
let make_cubic((a:float),(b:float),(c:float)) = fun x > (x*.x*.x +. a *. x*.x +. b*.x +. c)
let test1 = newton(make_cubic(2.0,3.0,1.0),0.0,0.0001,0.0001)
(* Should get 3.079599812; don’t worry if your last couple of digits are off. *)
let test2 = newton(sin,5.0,0.0001,0.0001)
(* Should get 9.42477…. *)
[Question 4:10 points] In class we say how to de ne a higherorder function that computes de nite integrals of the form

a

(x)dx:
b
To remind you
let integral((f: float > float),(lo:float),(hi:float),(dx:float)) = let delta (x:float) = x +. dx in
dx *. iterSum(f,(lo +. (dx/.2.0)), hi, delta);;
where iterSum was also de ned in class. In this question I want you to de ne a function that computes the inde nite integral:
^{Z} x
indIntegral(f) = f(y)dy:
0
This means that it returns a function not a number. Here is the type that I expect
# let indIntegral(f,(dx:float)) = …
val indIntegral : (float > float) * float > float > float = <fun>
Use any of the functions de ned in class. We will preload iterSum and integral so you won’t have to recode them.
3