# Homework 9

*Due by 11:59pm on Tuesday, 10/31*

## Instructions

Download hw09.zip.

Our course uses a custom version of Scheme (which you will build for Project 4) included in the starter ZIP archive. To start the interpreter, type

`python3 scheme`

. To run a Scheme program interactively, type`python3 scheme -i <file.scm>`

. To exit the Scheme interpreter, type`(exit)`

.

**Submission:** When you are done, submit with
`python3 ok --submit`

.
You may submit more than once before the deadline; only the final submission
will be scored. Check that you have successfully submitted your code on
okpy.org.
See Lab 0
for more instructions on submitting assignments.

**Using Ok:** If you have any questions about using Ok, please
refer to this guide.

**Readings:** You might find the following references
useful:

### Q1: Cadr and Caddr

Define the procedures `cadr`

and `caddr`

, which return the second
and third elements of a list, respectively:

```
(define (cddr s)
(cdr (cdr s)))
(define (cadr s)
'YOUR-CODE-HERE
)
(define (caddr s)
'YOUR-CODE-HERE
)
```

Use Ok to unlock and test your code:

```
python3 ok -q cadr-caddr -u
python3 ok -q cadr-caddr
```

### Conditional expressions

The `cond`

special form is a general conditional expression, similar to
a multi-clause conditional statement in Python. The general form of a
conditional expression is:

```
(cond
(<p1> <el1>)
(<p2> <el2>)
...
(<pn> <eln>)
(else <else-expressions>))
```

This consists of the symbol `cond`

followed by sequences of expressions ```
(<p>
<el>)
```

called *clauses*.

The first expression in each pair is a
*predicate*: an expression whose value is interpreted as either being true
or false.

In Scheme, *all* values except the special boolean value `#f`

are
interpreted as true values (unlike Python). (Our particular version of the
Scheme interpreter allows you to write `True`

and `False`

in place of
`#t`

and `#f`

, and prints boolean values as `True`

and `False`

. This is not
standard.)

Conditional expressions are evaluated as follows:

- The predicate
`<p1>`

is evaluated first. If its value is`#f`

, then`<p2>`

is evaluated. - If
`<p2>`

's value is also`#f`

, then`<p3>`

is evaluated. This process continues until the first predicate

`<pi>`

is found whose value is true, in which case the interpreter returns the result of evaluating each of the corresponding list of consequent expressions`<eli>`

and returning the last value as the value of the whole conditional expression.**Note:**Unless some of the expressions have side-effects, there is no point in having more than one expression in an expression list`<eli>`

.- The
`else`

keyword, if present, is taken to be true, so that if none of the`<p>`

's is found to be true, the interpreter evaluates the`else-expressions`

and returns the last value. - If no clause has a true predicate, the result is an "unspecified value".

This is a somewhat simplified version of the semantics of `cond`

, covering the
cases we usually encounter.

### Q2: Sign

Using `cond`

, define a procedure `sign`

that returns `-1`

for negative
arguments, `0`

for zero, and `1`

for positive arguments:

```
(define (sign x)
'YOUR-CODE-HERE
)
```

Use Ok to unlock and test your code:

```
python3 ok -q sign -u
python3 ok -q sign
```

### Q3: Pow

Implement a procedure `pow`

for raising the number `b`

to the power of a
nonnegative integer `n`

that runs in Θ(log n) time.

Hint:Consider the following observations:

- b
^{2k}= (b^{k})^{2}- b
^{2k+1}= b(b^{k})^{2}You may use the built-in predicates

`even?`

and`odd?`

.

```
(define (square x) (* x x))
(define (pow b n)
'YOUR-CODE-HERE
)
```

Use Ok to unlock and test your code:

```
python3 ok -q pow -u
python3 ok -q pow
```

### Q4: Ordered

Implement a procedure called `ordered?`

, which takes a list of numbers and
returns `True`

if the numbers are in nondescending order, and `False`

otherwise.
Numbers are considered nondescending if they are in a monotonically increasing
sequence, that is:

`1 2 3 3 4`

Is nondescending, but:

`1 2 3 3 2`

Is not.

Hint: The built-in`null?`

function returns whether its argument is`nil`

.

```
(define (ordered? s)
'YOUR-CODE-HERE
)
```

Use Ok to unlock and test your code:

```
python3 ok -q ordered -u
python3 ok -q ordered
```

### Q5: No Dots!

Implement the procedure `nodots`

, which takes a nested list of numbers that
may not be well-formed and returns a nested list with the same content and
structure, but which does not have any dots when displayed. Lists are not
well-formed if they do not properly terminate in a null list. In such cases,
the list will print with a dot before the final item to indicate that its
last two items are contained in a single pair. For example,

`(cons 1 (cons 2 3))`

would print as

`(1 2 . 3)`

for which `nodots`

should substitute

`(1 2 3)`

You may find the built-in

`null?`

and`pair?`

predicates useful.

```
(define (nodots s)
'YOUR-CODE-HERE
)
```

Use Ok to unlock and test your code:

```
python3 ok -q nodots -u
python3 ok -q nodots
```

### Sets as Ordered Lists

One way to represent a set is by using an ordered list, where the ordering is used to speed up search (although only by a constant factor). The following few questions explore this idea, assuming a "set" is a Scheme list with no repeated elements that is already ordered from least to greatest.

### Q6: Contains

Define `contains?`

, which returns whether a set `s`

contains value `v`

. The
Python implementation of this procedure is provided for your reference.

```
; Sets as sorted lists
(define (empty? s) (null? s))
(define (contains? s v)
(cond ((empty? s) #f)
'YOUR-CODE-HERE
(else nil) ; replace this line
))
; Equivalent Python code, for your reference:
;
; def empty(s):
; return s is Link.empty
;
; def contains(s, v):
; if empty(s):
; return False
; elif s.first > v:
; return False
; elif s.first == v:
; return True
; else:
; return contains(s.rest, v)
```

Use Ok to unlock and test your code:

```
python3 ok -q contains -u
python3 ok -q contains
```

### Q7: Add

Define `add`

, which takes a set `s`

and a value `v`

as arguments. It returns a
representation of a set containing the values in `s`

and the value `v`

. There
should be no repeated elements in the return value.

```
(define (add s v)
(cond ((empty? s) (list v))
'YOUR-CODE-HERE
(else nil) ; replace this line
))
```

Use Ok to unlock and test your code:

```
python3 ok -q add -u
python3 ok -q add
```

### Q8: Intersect and Union

Define `intersect`

, which returns a set containing only values that appear in
both sets `s`

and `t`

. Your implementation should run in linear time in the
length of the input sets. A Python implementation of this procedure is
provided for your reference.

Also, define `union`

, which returns a set containing all values that appear
in either set `s`

or `t`

.

```
(define (intersect s t)
(cond ((or (empty? s) (empty? t)) nil)
'YOUR-CODE-HERE
(else nil) ; replace this line
))
; Equivalent Python code, for your reference:
;
; def intersect(set1, set2):
; if empty(set1) or empty(set2):
; return Link.empty
; else:
; e1, e2 = set1.first, set2.first
; if e1 == e2:
; return Link(e1, intersect(set1.rest, set2.rest))
; elif e1 < e2:
; return intersect(set1.rest, set2)
; elif e2 < e1:
; return intersect(set1, set2.rest)
(define (union s t)
(cond ((empty? s) t)
((empty? t) s)
'YOUR-CODE-HERE
(else nil) ; replace this line
))
```

Use Ok to unlock and test your code:

```
python3 ok -q intersect -u
python3 ok -q intersect
python3 ok -q union -u
python3 ok -q union
```