Description
[Question 1:20 points] This is a classic example of a higher-order function in action. Newton’s method can be used to generate approximate solutions to the equation f(x) = 0 where
f is a differentiable real-valued function of the real variable x. The idea can be summarized
as follows:
Suppose that x0 is some point which we suspect is near a solution. We can form the linear
approximation l at x0 and solve the linear equation for a new approximate solution. Let
x1 be the solution to the linear approximation l(x) = f(x0) + f
0
(x0)(x − x0) = 0. In other
words,
f(x0) + f
0
(x0)(x1 − x0) = 0
x1 − x0 = −
f(x0)
f
0
(x0)
x1 = x0 −
f(x0)
f
0
(x0)
If our first guess x0 was a good one, then the approximate solution x1 should be an even
better approximation to the solution of f(x) = 0. Once we have x1, we can repeat the
process to obtain x2, etc. In fact, we can repeat this process indefinitely: if, after n steps,
we have an approximate solution xn, then the next step is
xn+1 = xn −
f(xn)
f
0
(xn)
.
1
This will produce approximate solutions to any degree of accuracy provided we have started
with a good guess x0. If we have reached a xn such that |f(xn)| < t, where t is some real
number representing the tolerance, we will stop.
Implement a function newton: (real -> real) * real * real -> real, which when
given a function f, a guess x0 and a tolerance t, will compute a value x
0
such that |f(x
0
)| < t.
You can test this on built in real valued functions like Real.Math.sin or other functions
in the Real.Math package. Please note that this method does not always work: one needs
stronger conditions on f to guarantee convergence of the approximation scheme.
[Question 2: 10 points] Explain what is wrong with the following attempt to define the
function repeated.
fun bad_repeated f n =
fn x => if (n=0) then x
else f(bad_repeated f (n-1))
The above definition gives the type:
val bad_repeated = fn : ((’a -> ’a) -> ’a) -> int -> ’a -> ’a
[Question 3: 15 points] Suppose we have defined a binary tree using the following datatype.
datatype ’a tree = Empty | Node of ’a tree * ’a * ’a tree
Implement a function flatten:’a tree -> ’a list which given a binary tree, will return
a list of all the elements in the tree in preorder.
[Question 4: 20 points] Prove the following: An element x is in the binary tree T iff x is in
flatten(T). Use induction on the structure of the tree.
[Question 5: 35 points] Suppose that we define a data type for expression trees containing
variables and for lists of bindings as follows:
datatype Exptree =
Const of int |
Var of string |
Add of Exptree * Exptree |
Mul of Exptree * Exptree;
type Bindings = (string * int) list
Define a function lookup, to lookup values in the binding list. If the name occurs more
than once it must find the latest value inserted. We never remove values from the binding
list. The binding list must be kept sorted by the name of the variable. You can use the <
operator on strings but you need to give a type annotation to tell the system that you are
2
using it on strings. Your lookup function should use options to deal with values that are not
present.
Define a function insert to insert a new binding in the right place in the binding list.
Define a function eval3 which evaluates expressions and returns options.
[Question 6: 0 points] Can you come up with an example of a differentiable function for
which Newton’s method does not work?
3