CSE 413 -- Assignment 1 -- Scheme Warmup (rev)

Due at the beginning of lecture on Wednesday, April 7, 1999

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.

Draw a boxes and arrows diagram to show the result of executing the following definitions.
```
(define y '(2 3))
```
```
(define z (cons 3 y))
```
```
(define w (cons z y)) 
```
```
(define x (cons w '(2 3))) 
```
Given the following definitions :
```
(define x '(1 2 3))
```
```
(define y (append x x))
```
```
(define z (cons x x))
```
```
(define foo '(7 2 3))
```
show the value of 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 x)
```
2. ```
(cdar x)
```
3. ```
(cdar z)
```
4. ```
(cons x foo)
```
5. ```
(equal? (cdr x) (cdr foo))
```
6. ```
(equal? (cdr y) x)
```
7. ```
(equal? (cdr z) (car z))
```
8. ```
(eqv? (cdr z) (car z))
```
9. ```
(eqv? (cdr x) (cdr foo))
```
10. ```
(car '(cadar x))
```
Define a function list-max that that returns the largest of the elements in its list argument. For example:
```
(list-max '(1 2 3 4))  => 4
```
```
(list-max '(1 17 192 -76)) => 192
```
Write a function divisors which, given an integer, returns a list of all its proper divisors ( the proper divisors of a number are all divisors except the number itself; 1 is included). You may find the Scheme function modulo to be useful. There should be no duplicate divisors. Examples:
```
(divisors 6)  => (1 2 3)
```
```
(divisors 28) => (1 2 4 7 14)
```
Now write a function is-perfect? that yields true if its argument is a perfect number, and yields false otherwise. A number is perfect if it is the sum of its proper divisors. The smallest perfect number is 6 (= 1+2+3). Another is 28 (= 1 + 2+ 4+ 7+ 14). (Hint: you may find the answers to the previous two questions to be useful in your solution).
```
(is-perfect? 6)  => #t
```
```
(is-perfect? 28) => #t
```
```
(is-perfect? 24) => #f
```

Define a function fringe that takes as an argument a tree (an arbitrary list) and returns a list containing the leaves of the tree in left-to-right order. For example:

(fringe '(not very interesting))  => (not very interesting)

(fringe '((this is) a (seriously ((more ( ) (complex)) tree)))) =>

                        (this is a seriously more complex tree)

Define a function rev that reverses the top-level elements of the list that is its argument (i.e., give your own implementation of the standard Scheme function reverse). For example:
```
(rev '(1 2 3 4))  => (4 3 2 1)
```
```
(rev '((A B) C (D (E F))) => ((D (E F)) C (A B))
```
Define a function deep-rev that reverses the elements of the list that is its argument. If elements of the list are themselves lists, they should be reversed recursively. Example:
```
(deep-rev '(1 2 3 4)) => (4 3 2 1)
```
```
(deep-rev '((A B) C (D (E F))) => (((F E) D) C (B A))
```