Homework 2 Solution

Please answer all questions: there are 5 in all plus one for spiritual growth. The solution to Q2 and Q4 can be typed up and submitted through myCourses as with the others solutions. Please put the non-programming questions in a separate file from the Sml programs. It is never too early to learn L ATEX! but I am not requiring it. Question 6 is for your spiritual growth only. Please do not submit an answer.
[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) + f0(x0)(x−x0) = 0. In other words, f(x0) + f0(x0)(x1 −x0) = 0 x1 −x0 = − f(x0) f0(x0) x1 = x0 − f(x0) f0(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) f0(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 x0 such that|f(x0)| < 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?