Tutorial 12: Working with unknown functions (November 28-30, 2007)
Today's tutorial (the last one!) covers accumulative recursion (lecture module 12). We'll be using accumulators to achieve tail recursion, which allows us to write some functions more naturally and more efficiently. You might want to think about what the invariant is for each of the accumulative functions we ask for below, and how you could use it to justify the correctness of the function.
foldr-nat: (num num -> num) num nat -> num (foldr-nat f base n) => (f n (f (- n 1) (f (- n 2) ... (f 1 base))))
So, for example, we could compute the factorial of a number n by calling
(define (foldr-nat1 f base n) (cond [(= n 1) (f 1 base)] [else (f n (foldr-nat1 f base (sub1 n)))]))
Now write a version of
These questions deal with functions which are strictly increasing for all x > 0 and which diverge (i.e. grow to infinity). Some examples of functions like these are certain polynomials, exponential and logarithmic functions, square root, cube root, etc., and any combination of these.
If f(x) is monotone increasing and divergent on the positive real numbers, then for any real number v, there must exist a positive integer u such that f(u) > v. The inverse floor function computes the greatest integer u such that f(u) ≤ v (assuming that f(0) ≤ v), given f and v. Intuitively, we could just accomplish this by testing each of f(1), f(2), ..., until we find f(u) > v, and then returning u-1. Write a function
By simply adding 1 to the result of
We saw a few weeks ago how to use the binary search algorithm to quickly search for a number in a binary search tree. This same idea can be used to search over a finite interval of the natural numbers. The idea is, given a lower and an upper bound on the result, to test some value in the middle (roughly), and use this to reduce the size of the search interval by one half (roughly).
Use this notion of a binary search on the natural numbers, along with your function