CSE 413 Winter 2002

Assignment 1 -- Scheme Warmup

All of these problems should be done without using side effects (i.e. redefining variables or using set!).  Be sure to test your functions on various cases, including empty lists, simple lists with no sublists, complex lists, etc.

Part I.  Written (paper) problems

1. Assuming that the following definitions are executed in this order,

(define a '(how now))

(define b (list 'brown 'cow))

(define roman '(I II III))

(define word 'say)

show the value that results from evaluating each of the following expressions.  If something is wrong, say so.  (Obviously you could trivialize the problem by typing these expressions into a Scheme interpreter and transcribing the results.  Feel free to use a computer to check your answers, but be sure you can answer the questions without using a machine.)



1. (car roman)

2. (cddr roman)

3. (cdr (car roman))

4. (car (cdr roman))

5. (cons word a)

6. (append a b)

7. (cons a b)

8. (pair? word)

9. (pair? roman)

10. (eq? '(I II III) roman)

11. (equal? '(I II III) roman)

2. (a) Draw a boxes and arrows diagram to show the result of executing the following definitions.

(define foo '(x y z))

(define bar (list 'a 'b foo))

(define baz (append bar foo))

(define qux (cons bar baz))

(b) How would the values of these 4 variables be displayed if those expressions were evaluated in a Scheme interpreter?

Part II. Programming Problems.

Write and test Scheme functions to solve the following problems.  You should save all of your function definitions in a single source file.  In DrScheme you can use  File->Save definitions as  to create a file that contains your function definitions.  The normal convention is to use the extension .scm to end Scheme file names.

You should turn in both the function definitions themselves and a printout showing a Scheme session where you test the functions.  Your test cases should be sufficient to show that the functions work correctly (i.e., works on both empty and non-empty lists, simple lists with no substructure, lists with nested lists, etc.).  In DrScheme, you can use File->Print Interactions to print the session transcript.

1. If a list contains multiple copies of the same element in succession, the list can be stored more compactly using run length encoding, in which the repeated element is given just once, preceded by the number of times it is repeated.
   
   Write a function run-length-decode which takes a run length encoded list and expands it to the full list.  Example:

   (run-length-decode '(a b 3 c d 4 e f) => (a b c c c d e e e e f)

2. Write a function merge-list that takes two sorted lists of integers with no duplicates and returns a single list that merges the two original lists.  The resulting list should be sorted, and, if the same number appears in both of the original lists, it should only appear once in the result.

(merge-list '(1 3 5 6 7) '(2 4 6)) => (1 2 3 4 5 6 7)

(merge-list '(10 20 25) '(5 10 15 20)) => (5 10 15 20 25)

(merge-list '(1 2 3) ('1 2 3)) => (1 2 3)

3. Write a function flatten that takes a list and returns a flattened list containing all of the elements in the original list as a single, top-level list with no sublists.  Example:

(flatten '(a (b (c d) e) (e ((f) g)))) => (a b c d e e f g)

4. Define a function (path item list) that returns the list of successive car's and cdr's needed to find the first occurrence of item in the list.  If the item does not occur in the list, return an empty list ().  Examples:

   (path 'c '((a b) (c d))) => (cdr car car)

   (path 'whazzup '((a b) (c d))) => ()

What to Hand In

For this assignment, you should turn in your work both electronically over the web and on paper.

Electronic Submission

Turn in a copy of your Scheme source file from part II using this turnin form.

Paper Submission

Hand in the following:

1. Written answers to the problems from Part I.
2. A printed copy of the receipt you received when you electronically turn in the file containing your Scheme functions from Part II.  This listing will include a copy of your Scheme code.
3. A printout showing the transcript of the Scheme session demonstrating the results produced by your functions for suitable test cases.  This should contain enough to show that your functions work, but no more than necessary to do that. Part of your grade will be determined by the quality of the test cases you use for this.  (Don't worry if there are some minor typos in the transcript - just draw a line through anything we should ignore.)