Homework 8: Due Friday April 8, 2011

Scheme Part 2 - Functions

1 Write a Scheme function called insert that takes two arguments: a number and a list of numbers sorted in ascending order. The function should return a list with the number inserted in the list in the proper position to maintain the sorted order. Examples:

(insert 7 '(1 3 4 5 9 10)) returns (1 3 4 5 7 9 10)

(insert 6 ()) returns (6)

2. Write a Scheme function called insert-sort which takes one argument: a list of numbers. The function should return a list with the numbers arranged in ascending order. This function should use a recursive insertion sort - insert the first element of the argument list into the list obtained by sorting the remainder of the list. Note that the function written in problem 1 will be called by insert-sort to do the insertions. Example:

(insert-sort '(9 2 5 1 6)) returns (1 2 5 6 9)

3. Exercise 10.6 (a). The tail recursive log2 function will need a local helper function. Define this function using letrec (a version of let for recursive definitions). All arithmetic should be done on the parameters passed into the helper (all processing done on the way in, none on the way out).

4. Exercise 10.10. Write the straightforward version of the flatten function described in this exercise. The trees mentioned in this problem are nested lists. The flatten function should return a list with the elements of the original in the same relative positions, but with all nesting removed. For example:

(flatten '(a (b c) d (e (f g) h) i)) returns (a b c d e f g h i)

The same-fringe function works by flattening the two lists and if they are equal then they trees they represent have the same leaves. Note there is a typo in the same-fringe code - it should be equal? as shown:

(define same-fringe
   (lambda (T1 T2)
      (equal? (flatten T1) (flatten T2))))

Examples:

(same-fringe '(a (b c) d (e (f g) h) i) '(a b c (d e) f (g h i))) returns #t

(same-fringe '(a b (d) c) '(a b (c) d)) returns #f

Save all function definitions in one file and zip the file. (The online submission will only accept .zip files.)