Description
Objectives
• Work with functions that take functions as parameters
• Work with functions that evaluate to functions
• Work with higher order functions
Activities
1. In Problem Set 3 you wrote a function (harmonic n) that calculates the n
th harmonic number,
Hn =
1
1 +
1
2 +
1
3 + · · · +
1
n
. It probably looked something like this:
( define ( harmonic n)
( if (= n 1)
1.0
(+ (/ 1 n) ( harmonic (- n 1)))))
This is a “recursive” process, as it has a pending operation (the addition) that is deferred until
the recursive call is finished.
Write an iterative version of this function (harmonic-iter n) that calculates the n
th harmonic
number.
As it is iterative, it should not have pending operations, rather it should carry along
the necessary information so you can report the result when you hit the base case. (You saw
an example of an iterative function in Problem Set 3, fast-lucas-help.
2. Recall the example code from the lecture slides which introduced higher-order functions (functions that take other functions as parameters). You may notice that the base case in the code
below has been changed to n = 1.
( define ( sum f n )
( if (= n 1)
(f 1)
(+ (f n) ( sum f (- n 1)))))
This code computes f(1) + f(2) + … + f(n) with f and n passed as parameters.
Use sum to write a new function (harm-sum n) that calculates the n
th harmonic number, using
sum to define harm-sum by passing it a function (harm-term k) that can calculate the kth term
in the harmonic series. Use your new function to compute a few harmonic numbers, and use
your old function to verify that your answers are correct.
3. As you noticed, the sum function in the course lecture slides sums from 0 to n and the function
in question 2 sums from 1 to n.
1
(a) Write a new, more general, summation function named g-sum, which takes three parameters, f – the function, a – the starting index of the summation and b the ending index of
the summation. For a given function f, and integers a and b,
g-sum(f, a, b) = X
b
i=a
f(i)
In the above, the sum should be 0 if a > b.
(b) Test your generalized version of sum with the harmonic numbers in question 2. You should
be able to reuse harm-term.
(c) We can define a geometric series of the negative powers of 2:
X∞
i=0
1
2
i
=
1
1
+
1
2
+
1
4
+ · · ·
Use g-sum to define a function (geom-series-np2 n) to calculate the sum of the first
n + 1 elements of this series. As part of this, define a function (geometric-term k) that
calculates the (k + 1)th term in this series, that is, 1
2
k
. Do not make (geometric-term k)
internal to (geom-series-np2).
(d) It is possible to use an unnamed function (that is, a lambda form) as a parameter whenever a function is expected. Use an unnamed function with g-sum to define a function
(convergent-series a b), which calculates the sum of the inverse-squares from a to b,
that is
convergent-series(a, b) = X
b
k=a
1
k
2
4. So far this semester, we have written several functions which find the n
th number in a sequence
which satisfies some property (e.g. the n
th even number). It would be helpful if we wrote a
higher order function which could take a function which generated the sequence and a function
which tested for the property in which we are interested as well as the integer n and returned
the n
th value in that sequence which satisfied the property (i.e. the test function returns true
when passed that value).
(a) Write a function, named find, which takes three parameters (sequence, a function; test,
a function and n, a positive integer) and returns the n
th value in sequence for which the
test function returns true (#t) when passed a value in sequence. (sequence k) should
return the k
th element of the sequence (where k is a positive integer); (test x) should
return #t if the property holds for x, #f otherwise.
(b) Test your program with by finding the 15th even non-negative integer and the 15th odd
non-negative integer. Hint: the first non-negative integer is 0.
(c) A Fibonacci prime is a Fibonacci number which is prime. Use your higher-order function
to define a function (nth-fib-prime n), which evaluates to the n
th Fibonacci prime.
Remember the “smooth” code from the lecture slides.
Note: recall that calculating Fibonacci numbers can be computationally intensive so
(nth-fib-prime n) can take a long time to calculate for large n. Two options: test
2 CSE 1729
on relatively small n values, or write an iterative routine to calculate Fibonacci numbers.
In either case, your function should be able to calculate (nth-fib-prime 6).
5. The composition of two functions f and g, denoted f ◦ g, is the function defined as
(f ◦ g)(x) = f(g(x))
(a) Write a Scheme function (comp f g) that returns the function f ◦ g. Once comp is defined
you would see the following behavior:
> ( define ( double x) (* 2 x ))
> ( define ( add-one x )(+ x 1))
> ( define com ( comp add-one double ))
> ( com 3)
7
> (( comp double add-one ) 3)
8
Carefully note and understand the syntax!
(b) Use comp to define the pos-cos function:
pos-cos(x) =
cos(x) if cos(x) ≥ 0
−cos(x) if cos(x) < 0
Key question: what two functions can be composed to produce pos-cos?
(c) Define square as follows: (define (square x)(* x x)).
Use comp to define the composition of square and sqrt. How does it behave? Does the
order of the functions in the composition matter?
1. Save your work to a file named lab4.rkt
2. Submit your solution file for grading via the Mimir site.
3 CSE 1729
