C311 Fall 1996 -- Programming Languages

Assignment 1: Basic Scheme

Due Friday, September 13, 5:00P

Write the function member-twice? that returns true if a particular atom appears at least twice in a list of atoms:

> (member-twice? (quote c) (quote (a b c d d b a)))
#f
> (member-twice? (quote b) (quote (a b c d d b a)))
#t

Write the function list-index that takes an atom a and a list ls, and returns the zero-based index of a in ls. If the atom a does not occur in ls, it should return -1. This is a difficult exercise.
```
> (list-index (quote a) (quote (b a c)))
1
> (list-index (quote d) (quote (b a c)))
-1
```
Write the function duplicate that takes a number n and an atom a and returns a list containing only n occurrences of a.
```
> (duplicate 3 'foo)
(foo foo foo)
> (duplicate 0 'foo)
()
```
Write the function assq that takes an atom a and an association list (a list of non-empty lists) als, and returns the first list in als whose car is a. If there are no lists in als whose car is a, assq returns #f.
```
> (assq 'g '((b c) (d f g) (g c 3) (f (g h))))
(g c 3)
> (assq 'g '((b c) (d f g) (f (g h))))
#f
```
Write the function list-ref that takes a number n and a list ls of length at least n+1, and returns the (zero-based) nth element in ls.
```
> (list-ref 3 '(a b c d e f))
d
> (list-ref 0 '(a b c d))
a
```
Write the function snoc that takes a list ls and a datum i, and returns a new list where i has been added to the end of ls.
```
> (snoc '(a b c) '(x y))
(a b c (x y))
> (snoc '() 'a)
(a)
```
Write the function intersection that takes two sets (lists of symbols without duplicates) s0 and s1, and returns a new set containing all elements that are in both s0 and s1.
```
> (intersection '(a b c) '(b c d))
(b c) or (c b)
> (intersection '(a b c) '(d e f))
()
```
Write the function count-parens that takes a possibly deep list ls and returns the number of parentheses in the printed representation of the list.
```
> (count-parens '((a b) (()) c))
8
> (count-parens '())
2
```
Write the function sum-of-squares that takes a tuple (list of numbers) tup and returns the sum of the squares of the numbers.
```
> (sum-of-squares '())
0
> (sum-of-squares '(3))
9
> (sum-of-squares '(3 4))
25
```
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 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 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)
```

Submission

Write your answers to the exercises in a file (following the indentation rules), and send that file to

c311@lakshmi.cs.indiana.edu

with the subject line

handin 1

Assuming you've saved your homework in the file ``one.ss'' in the current directory, one way to submit is with the command:

Mail -s "handin 1" c311@lakshmi.cs.indiana.edu < one.ss

Chris Haynes / chaynes@indiana.edu