Programming Languages -- Spring 1996

Homework Two: More Basic Scheme

Due Monday, January 22, at 9:00am

Write the function union that takes two lists of symbols without duplicates s0 and s1 and returns a new list containing all the symbols in s0 and s1 without duplicates, where order isn't important.
```
> (union '(a b c) '(d e f))
(a b c d e f)
> (union '(a b c) '(b a d))
(a b c d)     
```
Write the function set? that takes a list of symbols ls and returns #t if ls is a representation of a set: a list of symbols without duplicates.
```
> (set? '(a b b c))
#f
> (set? '(a b c))
#t
```

Write the function depth that takes a possibly deep list ls and returns the depth of ls.

> (depth '())
1
> (depth '(a ((b) c) d))
3
> (depth '((((a))) b (((c d (e) f))) g h))
5

Write the function div that performs integer division on nonnegative integers. You may not use quotient, remainder or modulo for this problem. Hint: A number can be defined as a ``rest'' (between 0 and m-1) and a multiple addition of m. The number of additions is the result.
```
> (div 7 5)
1
> (div 8 2)
4
> (div 2 3)
0
```

Write the function double* which takes an atom a and a (possibly deep) list ls and doubles each occurrence of a in ls.

> (double* (quote fried)
     (quote ((fried potatoes) (baked (fried)) tomatoes)))
((fried fried potatoes) (baked (fried fried)) tomatoes)
> (double* (quote a) (quote ((b c (((d)) c b b)))))
((b c (((d)) c b b)))

Write the procedure prefixes that takes a list ls and returns a list of the prefixes of ls in no particular order.

> (prefixes '(a b c))
(() (a) (a b) (a b c))
> (prefixes '(a (a b) c))
(() (a) (a (a b)) (a (a b) c))
> (prefixes '())
(())

Write the procedure curry2 that takes a procedure of two arguments f and returns a curried version of the procedure; that is, one which takes the first argument and returns a procedure that takes the second argument.
```
> (((curry2 +) 1) 2)
3
> (define consa ((curry2 cons) 'a))
> (consa '(b))
(a b)
> (consa '(c d))
(a c d)
```
Write the procedure vector-index that takes an atom a and a vector v and returns the zero-based index of the first occurrence of a in v, or -1 if a does not occur in v.
```
> (vector-index 'c '#(a b c d))
2
> (vector-index 'c '#(a d b e))
-1
```
Write the procedure flatten that takes a (possibly deep) list of symbols ls and returns a new flat list containing all the symbols of ls in the same order as they were previously; that is, flatten removes all of the inner parentheses from its argument.
```
> (flatten '(a b c))
(a b c)
> (flatten '((a b) c (((d)) e)))
(a b c d e)
> (flatten '(a b (() (c))))
(a b c)
```
Write the procedure path that takes a number n and a binary search tree bst which contains the number n, and returns a list of occurrences of the symbol r and l showing how to find the node containing n. If n is found at the root, it returns the empty list.
```
> (path 17 '(14 (7 () (12 () ()))
	        (26 (20 (17 () ())
		        ())
		    (31 () ()))))
(r l l)
```
Submission

Write your answers to the exercises in a file (with comments, following the proper indentation rules), and send that file to
c311@lakshmi.cs.indiana.edu
with the subject line
2
Assuming you've saved your homework in the file ``asgn.ss'' in the current directory, one way to submit is with the command:
Mail -s "2" c311@lakshmi.cs.indiana.edu < asgn.ss

Back to the c311 page

ehilsdal@cs.indiana.edu

Mon Jan 15 11:45:03 EST 1996

Programming Languages -- Spring 1996

Homework Two: More Basic Scheme

Submission