CSE 1729 – Introduction to Principles of Programming Due October 16, 2015 Problem Set 5 – revised
1. One list is a prefix of another if the other list has the same values starting from the beginning, and potentially more. For example, ’(1 2) is a prefix of ’(1 2 3 4), and also a prefix of ’(1 2); ’() is a prefix of any list; and the empty list has only one prefix, itself.
(a) Define a Scheme function, is-prefix?, which takes two lists as arguments; it returns #t if the first list is a prefix of the second list, #f otherwise. You can depend on the parameters being lists of numbers, so you can use = to see if values are equal.
(b) We can define a common prefix of two lists l1 and l2 as any list that is a prefix of both lists. For example, ’(1 2 3) and ’(1 2) have common prefixes ’(),’(1),and ’(1 2).
Define a Scheme function, longest-common-prefix, which takes two lists as arguments, and returns the longest common prefix of the two lists. In the above example, that would be ’(1 2).
2. Generalized consecutives. In lab you wrote a functions, consecutive-squares based on consecutive-ints. Here you will generalize these in two ways.
(a) First, write a Scheme function (gen-consecutive f a b), where f is a function of one argument, and (as before) a and b are integers. (gen-consecutive f a b) evaluates to a list where each element is the result of applying f to an integer in the range a to b; that is, the values in the list are (f a)(f (+ a 1))…(f b). As an example, (gen-consecutive (lambda(x)(* x x)) 1 10) will produce the same result as (consecutive-squares 1 10).
(b) Next, write the even more general Scheme function (gen-sequence f a b next), where f, a, and b are as above, and next is a function of one integer argument. This function evaluates to the list of values obtained by applying f to a, then (next a), then (next (next a)) and so forth until the next one is greater than b. As an example, I could produce the list of the odd factorials from 1 to 5 by evaluating (gen-sequence factorial 1 5 (lambda(x)(+ x 2))), assuming I had defined the factorial function.
3. A useful function to have for lists is filter: a function that finds the values of a list that pass a certain test. Specifically, we want filter to take a function and a list as arguments, and return a list whose members are the elements of the original list for which the function returns true. For example,
(filtereven? ’(1234567))=>(246).
Or
(filter (lambda(x)(< (length x) 3)) ’((1) (2 3) (4 5 6 7))) => ((1)(2 3)).
Write a Scheme function (filter f lst) that implements this function. f should be a function that takes one argument and returns #t or #f.
4. (a) Write a Scheme function (value-at-position lst k) that takes a list lst and a non- negative integer k, and evaluates to the value at the kth position of the list. Position 1
1
should be the first element of the list. If the position is too large for the list, the function should result in an error.
(b) Demonstrate how you can use consecutive-ints, filter and value-at-position to write a function (nth-prime-between a b n) that will evaluate to the nth prime number between a and b. Feel free to use the is-prime? function from the lecture slides if that helps.
5. One of the points of complex numbers is that they allow us to find the square roots of a negative
√
We can define the principal square root of a complex number a + bi (with b ̸= 0) as γ + δi,
number, e.g. where
−9 = 3i.
√
a+ a2+b2 2
and
γ=
√
−a+ a2+b2
δ = sgn(b)
sgn(b)isthesignumofb: -1ifb<0,0ifb=0,and1ifb>0. Notethatthesquarerootsused
in the definitions of γ and δ all have real arguments – use sqrt function for these.
(a) Using the complex number implementation from this week’s lab (either yours or the version in the solutions), define a Scheme function (complex-sqrt x) that calculates the principal square root of a complex number. Given the repeated use of some things, using helper function(s) and/or let is probably a good idea.
Test your function on a few complex numbers where b ̸= 0 (that is, multiply the square root times itself) to show that it works.
(b) complex-sqrt has a bad feature, in that it doesn’t work correctly for some complex num- bers a + bi where b = 0. Use complex-sqrt on a number with zero as the imaginary part and verify that it is wrong. Remember that it is not wrong for all of these, but you should be able to find an example where it is.
(c) See if you can modify the definition of complex-sqrt to fix this. (HINT: look at what happens when b = 0 to sgn(b) – perhaps the fix could be made there.) The corrected version of the function should be named better-complex-sqrt.
2
2