Due date: 9/20 @ 5:00 pm

The goal of this problem set is to practice data-centric programming
(also known as "structural recursion") using structures, lists,
S-expressions, recursive data definitions.

Use the HtDP Intermediate Student programming language.

**Warning:** This problem set is labor-intensive for those of you who have
little or no practice with Scheme programming.

**EoPL Problems**:

1.15 (1,2,8,9); 1.16 (1,2,3,4,5); 1.17 (1:see below); 1.18

**Additional Problem 0**:

Here is a recursively defined class of data:
```
(define-struct rectangle (x y width height))
(define-struct circle (x y radius))
(define-struct combination (top bot))
```

A *Shape* is one of:

- a Rectangle
- a Circle
- a Combination of two Shapes:
`(make-combination Shape Shape)`

A *Rectangle is* `(make-rectangle Number Number Number Number)`.

A *Circle is* `(make-circle Number Number Number)`.

Design the function `area`, which consumes a shape and computes the
area that it covers (counting overlaps twice).

Design `inside`. The function consumes a shape and two numbers, which
denote a position. It determines whether this position is inside the given
shape (not on the border).

Design the function `bb`, which consumes a `Shape` and produces
a bounding box. The latter is the smallest rectangle that includes the entire
shape (overlapping broders).

The following additional problems should recall basic things about sets, finite
functions (table), and relations. We will rely on those and a few more when we
formulate operational semantics for programming languages.

**Additional Problem 1**:

A *set* is a collection of `X`s that are all mutually
distinct. The `X`s are called *element*s.

You can represent a set of symbols as a list of symbols such that all symbols
are pairwise not `eq?`.

Design the function `element-of?`, which determines whether a given
element is in a given set.

Design the function `add-element`, which consumes a symbol and a set
and constructs a new set that includes this symbol.

Design the function `remove-element`, which removes a given symbol
from a given set. Hint: Is it always true that

```
(boolean=? (element-of? e (remove-element e s)) false)
```

for all elements `e` and sets `s`?
Design the function `union`, which creates a set from the elements of
two given sets.

Design the function `intersect`, which creates a set from the
elements that are common to two given sets.

You can use your functions with arbitrary lists of symbols, such as `'(a b
a b)`, that are not representations of sets. What can go "wrong" when you do
that? How could you ensure in Scheme that nobody ever "abuses" your functions in
this manner?

**Additional Problem 2**:

A *relation* is a set of tuples, which in turn is a list of symbols:

```
;; A tuple is (list Symbol Symbol).
;; Example:
(define a-tuple '(a b))
;; A relation is a set of tuples.
```

Design the function `domain`, which collects all firsts from a given
relation in a set.

Design the function `range`, which collects all seconds from a given
relation in a set.

Design the function `at`. It consumes a set `S`and a relation
`R`. Its purpose is to collect all the seconds from all tuples in
`R` whose first is a member of `S`.

Design the function `x`. It consumes two sets and creates a relation
that combines all elements from the first set with all elements from the second
set. Example:

```
(equal? (x '(a b) '(x y z))
'((a x) (a y) (a z) (b x) (b y) (b z)))
```

A relation is a function if every element in the domain is related to exactly
one element in the range. Design the function `function?`, which
consumes a relation and determines whether it is a function.

**Additional Problem 3**:

A *finite function* (or *table*) with respect to some universe
set `U` is a relation `R` whose domain is a finite subset of
`U` and for which we can always computationally pick an element in
`U` that is not an element of the domain of `R`. Our
representation of relations is naturally a representation of finite
relations. If we choose the natural numbers `N` as the universe, we can
make this representation a representation of finite functions.

Design the function `next`. It consumes a finite relation that relates
natural numbers to symbols. It produces a natural number that is not in the
domain of the given relation.

Design the function `allocate`. It consumes a symbol `S` and a
finite relation `R` that relates natural numbers to symbols. It produces
a relation that relates all elements in the domain of `R` to the same
symbol as `R` and a natural number that doesn't occur in the domain of
`R` to `S`.