Instructions: This problem set has three parts. You will submit a total of four separate files: part1.sml , part2.sml , part3.sml, and part4.sml, Modify the .sml template files from ps3files.zip. As always, don't change function names, and remember: non-compiling code will receive an automatic zero. All your files should have your name, netID, and your section in a comment at the top. Do NOT compress the files into a zip file. You must submit each file individually using CMS.
Consider a function f:real->real. A value x:real is said to be a fixpont of f if f(x) = x. From a geometric point of view, the fixpoints of f are the points where the graph of f intersects the line y = x.
a) Write an ML function, nofix:real->real, that has zero fixpoints. Write a second function, inffix, that has an infinite number of fixpoints.
b) Consider the function
fun func1(x:real):real = (x+2.0/x)/2.0
How many fixpoints does func1 have? What value(s) do these fixpoint(s) correspond to? Write your answers in comments.
c) Now consider the curried function
fun func2(a:real) (x:real):real = (x+a/x)/2.0
How many fixpoints does (func2 a) have for an arbitrary a? What values do these fixpoints correspond to? Write your answers in comments.
d) For many functions, we can compute fixpoints iteratively: starting with an approximation x0 to the fixpoint, we compute the series f(x0), f(f(x0)), f(f(f(x0)))... if this series converges, it converges to a fixpoint of f. For functions with multiple fixpoints, the fixpoint we find may depend on the approximation we start with.
Write a function fix1:(real->real)->real->real that takes in a (real->real) function f and a guess x0 and iteratively computes the fixpoint. Your function should terminate when it finds an x such that the magnitude of abs(f(x)-x) is less than .00001. Test your function on func1 above, with a guess of 1. Do you get the answer you expected?
e) Now write a function, iterSqrt (fix:(real->real)->real->real) (a:real) (guess:real):real that uses these ideas to compute the square root of its input a. Use this function to compute the 4th root of 72.
f) One problem with the fix1 function defined above is that an arbitrary convergence criterion is built into the function. To be useful, the function should permit the user to write a convergence criterion that is appropriate to the problem. For example, the user might declare convergence if three successive approximations xi-2, xi-1, xi are close to each other. In general, the user might want to look at all the approximations computed thus far to determine whether to declare convergence.
Write a function, fix2: (f:(real -> real))->(converge:(real list)->bool)->(x0:real)->real which finds the fixpoint of a function f, starting from the approximation x0, using the function converge to determine whether convergence has happened. The function converge should get a list of all approximations computed thus far, and it should return true or false.
Write a function cvrg:(real list)->bool that declares convergence if 0.5(abs(xi-1-xi)+abs(xi-2-xi-1)) is less than 0.0001.
Using the function fix2 with the convergence function cvrg, compute the 4th root of 72 again.
g) In calculus, you learnt Newton's method for finding a zero of a differentiable function g. This method can be expressed as a fixpoint computation of the function f(x) = (x - g(x)/g'(x)). We can perform numerical differentiation of a function g(x) at a point p by computing the value of (g(p+delta) - g(p) )/delta for a suitably small value of delta. To find the square root of a number a, we can find a zero of the function s(x) = x*x - a. Use these ideas to write a square root function that uses the fix2 function you defined earlier. The type of your function should be: newtonroot:(a:real)->(delta:real)->(guess:real)->real. You may use fix2 instead of passing a fix function in as an argument.
h) Generalize your last function; write newtonNthRoot:(a:real)->(delta:real)->(n:real)->(guess:real)->real.
b) Now write a function union:''a list list->''a list that takes a list of lists and returns a list that contains every element in any of the original lists, but contains no element more than once. You may only fold over the ''a list list once. Note that, because we are using ''a instead of 'a, you may assume that the equality operator operates over the type ''a.
c) In operating systems, you will learn about caching. The general idea is that every time we want information and we have it stored in local memory, we spend very little time retrieving it. Every time we don't have it in local memory, we have to spend a fair deal of time retrieving it. So, based on what data we've had to retrieve so far, we try to predict what pieces of data we will want in the future and thus should keep around. Formally: we have type cacheProtocol=(int list*int list*int)->int list. This takes in the current state of the cache, the list of requests already handled (with the most recent at the head), and the current request. It outputs the resulting cache after this request. The system works like this: at every new timestep, the new address is retrieved. If it was not in the existing cache, it was a miss, and we retrieve it from storage and give it to the cache protocol to possibly store in place of one of its existing stored entries.
Your task is this: write a function scoreCache:(int list*cacheProtocol)->real that takes in a cache protocol and a list of address reads and outputs the protocol's success rate, which is calculated: (reads - misses)/reads. You may assume that, at the beginning of the list of reads, the cache is empty.
(((double (double double)) inc) 22)?Why is this value returned? Explain your answer briefly.
b) Imagine a new procedure mysteryfunc that takes in integers x and y and returns
double double double .... double inc ysuch that double is applied x times. Write the value that mysteryfunc returns for an arbitrary x and y as a mathematical formula. You may write your formula inductively.
c)Consider the following two functions:
fun B x y z = x (y z); fun C x y z = x z y;
Note that both these functions are polymorphic.
Function C's signature is ('a -> 'b -> 'c) -> 'b -> 'a -> 'c;
it indicates that argument x must be a curried function of two arguments.
All function C does is that it reverses the order in which it applies the
second and third argument to the first one.
Function B's signature is ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b;
it indicates that both the first and the second argument are functions of one
variable. You will encounter function B under a different name in class -
can you express in general terms what it does?
Consider the following code:
- (B (B C) C) (fn x => fn y => fn z => Int.toString(x) = ^ " " = ^ Int.toString(y) = ^ " " = ^ Int.toString(z)) 1 2 3; val it = "3 1 2" : string
From the result shown above we can infer that the effect of (B (B C) C)
is that it circularly permutes its second, third, and fourth argument before applying them
to the first argument. By circular permutation of a list of arguments we mean
that the first argument becomes second, the second becomes third, and so on until
the last argument, which becomes the first.
To understand what expression (B (B C) C) does, you should compare the
effect of (B C) to that of C. Finally, you should understand how
B combines (B C) and C.
Now, to the task: write a polymorphic function rotateArg that has a curried function of
four variables as its first argument, and then four more arguments. RotateArg
will circularly permute its last four arguments before applying them to the first one.
d) Write a function rotateArg2 that has the same arguments and effect
as rotateArg, so that its definition uses some combination of functions
B and C and the original arguments, but no other functions.
Both B and C must appear in your solution.
Define a string to be a 3-palindrome if it is of the form "S concatenated with reverse(S) concatenated with S" where S is any string. For example, "abccbaabc" is a 3-palindrome.
Write a function that determines whether a string is a 3-palindrome, making only one pass down the string. Note that you are not given the length of the string, and computing the length counts as one pass.