Homework #9

This problem requires Lecture 7 and book section 1.2.

Exercise 1.15, problems 6-9
Exercise 1.16, problem 2, p.25-26 - (60 minutes)

Define, test, and debug the following procedures. Assume that s is a symbol, n is a nonnegative integer, lst is a list, v is a vecotr, los is a list of symbols, vos is a vector of symbols, slist is an s-list, and x is any object, etc. Also assume that pred is a predicate, that is, a procedure that takes any Scheme object and returns either #t or #f. Make no other assumptions about the data unless further restrictions are given as part of a particular problem. For these exercises, there is no need to check that the input matches the description; ofr each procedure, assume that its input values are members of the specified set.

Exercise 1.15, problems 6-9
6.(vector-index pred v) returns the zero-based index of the first element of v that satifies the predicate pred, or #f if no element of v satisfies pred.

	> (vector-index (lambda (x) (eqv? x 'c)) '#(a b c d))
	2
	> (vector-ref '#(a b c)
		(vector-index (lambda (x) (eqv? x 'b)) '#(a b c)))
	b

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

7. (list-set lst n x) returns a list like lst, except that the n-th element, using zero-based indexing, is x.

	> (list-set '(a b c d) 2 '(1 2))
	(a b (1 2) d)
	> (list-ref (list-set '(a b c d) 3 '(1 5 10)) 3)
	(1 5 10)

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

8. (product los1 los2) returns a list of 2-lists that represents the Cartesian product of los1 and los2. The 2-lists may appear in any order.

	> (product '(a b c) '(x y))
	((a x) (a y) (b x) (b y) (c x) (c y))

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

9. (down lst) wraps parentheses around each top-level element of lst.

	> (down '(1 2 3))
	((1)(2)(3))
	> (down '((a)(fine)(idea)))
	(((a))((fine))((idea)))
	> (down '(a (more (complicated)) object))
	((a)((more (complicated)))(object))

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

Exercise 1.16, problem 2
2. (swapper s1 s2 slist) returns a list the same as s-list, but with all occurances of s1 replaced by s2 and all occurances of s2 replaced by s1.

	> (swapper 'a 'd '(a b c d))
	(d b c a)
	> (swapper 'a 'd '(a d () c d))
	(d a () c a)
	> (swapper 'x 'y '((x) y (z (x))))
	((y) x (z (y)))

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

To test these procedures, at the very minimum try all of the given examples. Also use other examples to test these procedures, since the given examples are not adequate to reveal all possible errors.

If the operations involve lists, you must process them recursively as lists without converting them to vectors.

Hint: swapper is just a bidirectional version of subst, so structure it the same way.

YOU MUST NAME YOUR FUNCTIONS WITH THE SAME NAMES THEY HAVE IN THE BOOK (i.e., vector-index, list-set, product, down, and swapper).

Instructions on submitting homework is here

Last updated at 3:02 pm on Wednesday, June 29, 2005.