Topics: list recursion
As you know, the
(index-of val lst) procedure finds the
index of the first instances of
val is not in
it returns the value
What if we wanted all of the indices, not just the first one? We’d probably have to write our own procedure.
Document and write a recursive procedure,
lst), that creates a list of all the position in
val appears. If the value does not appear,
return the empty list.
> (indices-of 'skip (list 'hop 'skip 'and 'jump)) '(1) > (indices-of 'skip (list 'hop 'skip 'jump 'and 'skip 'again)) '(1 4) > (indices-of 5 (list 5 4 3 2 1 2 3 4 5)) '(0 8) > (indices-of "eraser" (list "pencils" "paper" "index cards" "markers" "ball-point pens")) '()
Note: You may not use
index-of) in implementing
Topics: list recursion
Document and write a procedure,
(riffle3 first second third),
that produces a new list containing alternating elements from the lists
second, and third. If one list runs out before the others,
continue riffling the remaining two lists.
> (riffle3 (list 'a 'b 'c) (list 'p 'q 'r) (list 'x 'y 'z)) '(a p x b q y c r z) > (riffle3 (list 'a 'b 'c 'd) (list 'e 'f) (list 'g 'h 'i)) '(a e g b f h c i d) > (riffle3 (list 'a 'b 'c) null (list 'd 'e 'f)) '(a d b e c f) > (riffle3 (list 'c 'b 'a) (list 'd 'd 'd) (list 'e 'f 'g)) '(c d e b d f a d g)
Given a list of items, it can be useful to know all possible ways the list can be uniquely ordered. A specific ordering of items is called a permutation and the notion appears frequently in mathematics.
Write, but do not document, a procedure called
lst) that takes a list as a parameter returns a list of all
possible permutations of the elements of
lst. Here are a few example
executions of the procedure.
> (permutations (list 1 2)) '((1 2) (2 1)) > (permutations (list 0 1 2)) '((0 1 2) (1 0 2) (1 2 0) (0 2 1) (2 0 1) (2 1 0)) > (permutations (list 'a 'b 'c)) '((a b c) (a c b) (b a c) (b c a) (c a b) (c b a)) > (permutations (list "a" 'b 7)) '(("a" b 7) ("a" 7 b) (b "a" 7) (b 7 "a") (7 "a" b) (7 b "a")) > (permutations (list "hello")) '(("hello")) > (permutations null) '(())
You will find the following procedure helpful. (You should understand what the procedure does. You need not understand how it achieves its goal.)
;;; Procedure: ;;; insert-everywhere ;;; Parameters: ;;; val, a Scheme value ;;; lst, a list ;;; Purpose: ;;; Create a new list consisting of the result of inserting `val` ;;; at every possible location in `lst`. ;;; Produces: ;;; inserted, a list of lists ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; * (length inserted) = (+ 1 (length lst)) ;;; * (list-ref inserted i) = is the result of inserting val before ;;; the value at position i in lst. ;;; Practica: ;;; > (insert-everywhere 'a (list 'b)) ;;; '((a b) (b a)) ;;; > (insert-everywhere 'a (list 1 2 3)) ;;; '((a 1 2 3) (1 a 2 3) (1 2 a 3) (1 2 3 a)) ;;; > (insert-everywhere 'a null) ;;; '((a)) (define insert-everywhere (lambda (val lst) (if (null? lst) (list (list val)) (cons (cons val lst) (map (section cons (car lst) <>) (insert-everywhere val (cdr lst)))))))
How will this procedure help? To compute the permutations of a non-empty list, you make all of the permutations of the cdr of the list, insert the car of the list at each position in each permutation, and then join them all together.
> (insert-everywhere 1 '(2)) '((1 2) (2 1)) > (insert-everywhere 0 '(1 2)) '((0 1 2) (1 0 2) (1 2 0)) > (insert-everywhere 0 '(2 1)) '((0 2 1) (2 0 1) (2 1 0)) > (append (insert-everywhere 0 '(1 2)) (insert-everywhere 0 '(2 1))) '((0 1 2) (1 0 2) (1 2 0) (0 2 1) (2 0 1) (2 1 0))
Topics: list recursion, sorting
Write but do not document a recursive procedure,
lst1 lst2), that takes as input two lists of real numbers
that are ordered from smallest to largest and returns the combination
of those two lists, still in sorted order.
You may not use
sort in your solution.
> (merge-sorted-lists '(1 5 6 7 22) '(0 2 3 4 7 18 19)) '(0 1 2 3 4 5 6 7 7 18 19 22) > (merge-sorted-lists '(1 3 5 7) '(2 3 4 5 6)) '(1 2 3 3 4 5 5 6 7)
Topics: numeric recursion, generalizing code
The following procedure finds the value of 2^x when x is a positive integer.
(define power-of-two (lambda (x) (if (= x 0) 1 (* 2 (power-of-two (- x 1))))))
While this procedure is useful in specific situations, we sometimes want to take negative exponents or raise numbers other than two to some power. Make the following improvements to this procedure:
a. Modify the procedure so it will work for negative exponents. Recall than . Include at least four test cases with your code for this part; these do not need to be in a rackunit test suite.
b. Modify the procedure so it takes an additional parameter, the base of the exponent and returns . You will need to rename the procedure and change its signature. Include at least four test cases with your code for this part; these tests do not need to be in a rackunit test suite.
Note: you may not use
expt or any other mathematical procedures other than
= in your solution to this problem.
We will primarily evaluate your work on correctness (does your code compute what it’s supposed to and are your procedure descriptions accurate); clarity (is it easy to tell what your code does and how it achieves its results; is your writing clear and free of jargon); and concision (have you kept your work short and clean, rather than long and rambly).