- Work in pairs
- Change roles often!
- Follow the design recipe for
every problem.

*Exercise 1:*

Design a function that consumes an list of numbers`ln`

and checks if`0`

is a member of`ln`

.

*Exercise 2:*

Design a function that consumes an list of numbers`ln`

and checks if`6`

is a member of`ln`

.

*Exercise 3:*

Abstract over the previous two functions to design a function that consumes an list of numbers`ln`

and a number`n`

and checks if`n`

is a member of`ln`

.

*Exercise 4:*

Design a function that consumes an list of numbers`ln`

and filters out all members of`ln`

that are greater than`3`

.

*Exercise 5:*

Design a function that consumes an list of numbers`ln`

and a number`n`

and filters out all numbers less than`n`

in`ln`

.

*Exercise 6:*

Abstract over the previous two functions.

(define-struct unop (fun expr)) (define-struct binop (fun left right)) (define-struct var (x)) ;; An NAExpr is one of ;; -- (make-var String) ;; -- (make-unop [Number -> Number] NAExpr) ;; -- (make-binop [Number Number -> Number] NAExpr NAExpr) ;; -- Number

*Exercise 7:*

An

`NAExpr`

is an arithmetic expression on Numbers. Give the data definition for an arithmetic expression of Booleans,`BAExpr`

.

(Hint: Unary operators on Booleans include functions things`not`

, and binary operators on Booleans include functions like`and`

and`or`

.)

*Exercise 8: *

```
Abstract over the two previous data definitions to
obtain a data definition for a generic arithmetic expression.
That is:
``````
;; For any X, a [GAExpr X] is one of:
;; . . . ?
```

*Exercise 9:*

Design a function that consumes a generic arithmetic expression and counts all occurrences ofconstants(i.e., not variables or operations but the last case of the data definition).

*Exercise 10:*

Design a function that consumes a generic arithmetic expression, a String`s`

and a value`v`

and replaces all occurences of`(make-var s)`

in the expression with`v`

.What kind of data does

`v`

have to be? What is the contract of your function?

When people stand in a *queue* (a line), they stay in order.
New people enqueue (get in line) at the back, and when it’s their
turn, people dequeue from the front.

A queue comes with five operations:

*enqueue*adds an element at the end of the queue*dequeue*removes an element at the front and returns the remaining queue*queue-head*returns the element at the head of the queue*empty-queue?*tells whether a queue is empty*make-empty-queue*creates a new, empty queue

We will represent queues (somewhat inefficiently) using lists.

Here is a data definition for a queue of numbers is the following:

```
;; An NQueue is one of:
;; -- empty
;; -- (cons Number NQueue)
;; where the front of the NQueue is the first item in the list,
;; and the back of the NQueue is the final element of the list.
```

*Exercise 11:*

Give the data definition for a queue of strings.

*Exercise 12: *

Abstract over the two previous data definitions to obtain a data definition for a generic queue.

*Exercise 13: *

Design the five functions mentioned above for generic queues.

Can all of these functions succeed and return a sensible answer for all queues? If not, some of the functions may need to signal an error. See checked functions in Section 8.4.