*Due by 11:59pm on Thursday, 11/6*

**Instructions:** Download, complete, and submit the quiz2.scm starter file before the
deadline above. You must work alone, but you may talk to the course
staff (see **Asking Questions** below). You may use any
course materials, including an interpreter, course videos,
slides, and readings. Please **do not** discuss these
specific questions with your classmates, and **do not**
scour the web for answers or post your answers online.

Submit with `submit quiz2`

. You may submit more than
once before the deadline; only the final submission will be
scored. See Lab 1 for
submission instructions.

**Asking Questions.** If you believe you need
clarification on a question, make a private post on Piazza. Please do
not post publicly about the quiz contents. If the staff discovers a
problem with the quiz or needs to clarify a question, we will email the
class via Piazza. You can also come to office hours to ask questions
about the quiz or any other course material, but no answers or hints will
be provided in office hours.

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

Scheme does not have a built-in testing framework. To verify behavior, we will
use the following `assert-equal`

procedure, which tests whether an `expression`

evaluates to an expected `value`

.

```
(define (assert-equal value expression)
(if (equal? value (eval expression))
(print 'ok)
(print (list 'for expression ':
'expected value
'but 'got (eval expression)))))
```

When you evaluate your solution, a long sequence of `ok`

should be displayed.
Any test failures will describe the error instead.

(*1 point*) Implement `equal-answer`

, which takes two single-argument
procedures `f1`

and `f2`

and returns a procedure that takes one argument `x`

.
This returned procedure will return `true`

(`#t`

) if `f1`

and `f2`

return equal
values when called on argument `x`

and `false`

(`#f`

) otherwise.

Assume that the input procedures `f1`

and `f2`

always take and return numbers.
Test for equality using the `=`

procedure.

```
(define (equal-answer f1 f2)
'YOUR-CODE-HERE (lambda (x) 'replace-this))
(define (test-equal-answer)
(print (list 'testing 'equal-answer))
; (add-two 2) evaluates to 4, (square 2) also evaluates to 4
(assert-equal true '((equal-answer add-two square) 2))
; (add-two 3) evaluates to 5, (square 3) instead evaluates to 9
(assert-equal false '((equal-answer add-two square) 3))
)
(test-equal-answer)
```

(*1 point*) Implement `num-adjacent-matches`

, which takes as input a list of
numbers `s`

and returns the number of adjacent elements that are equal.

```
(define (num-adjacent-matches s)
'YOUR-CODE-HERE 'replace-this)
(define (test-num-adjacent-matches)
(print (list 'testing 'num-adjacent-matches))
; no pairs
(assert-equal 0 '(num-adjacent-matches '(1 2 3 4)))
; one pair of 1's
(assert-equal 1 '(num-adjacent-matches '(1 1 2 3)))
; one pair of 1's, one pair of 2's
(assert-equal 2 '(num-adjacent-matches '(1 1 2 2)))
; three pairs of 1's
(assert-equal 3 '(num-adjacent-matches '(1 1 1 1)))
)
(test-num-adjacent-matches)
```

(*2 points*) Implement `tally`

, which takes a list of `names`

and returns a
list of pairs, one pair for each unique name in `names`

. Each pair should
contain a name and the number of times that the name appeared in `names`

. Each
name should appear only once in the output, and the names should be ordered by
when they first appear in `names`

.

*Hint*: Use the `eq?`

procedure to test if two names are the same.

```
(define (tally names)
'YOUR-CODE-HERE 'replace-this)
(define (test-tally)
(print (list 'testing 'tally))
(assert-equal '((obama . 1))
'(tally '(obama)))
(assert-equal '((taft . 3))
'(tally '(taft taft taft)))
(assert-equal '((jerry . 2) (brown . 1))
'(tally '(jerry jerry brown)))
(assert-equal '((jane . 5) (jack . 2) (jill . 1))
'(tally '(jane jack jane jane jack jill jane jane)))
(assert-equal '((jane . 5) (jack . 2) (jill . 1))
'(tally '(jane jack jane jane jill jane jane jack)))
)
```

*Hint*: You may want to use `apply-to-all`

and `keep-if`

in your solution.

```
(define (apply-to-all fn s)
(if (null? s) nil
(cons (fn (car s))
(apply-to-all fn (cdr s)))))
(define (keep-if fn s)
(cond ((null? s) nil)
((fn (car s)) (cons (car s)
(keep-if fn (cdr s))))
(else (keep-if fn (cdr s)))))
```

*Partial Credit*: One way to implement `tally`

is to first find the list of
unique elements in `names`

and then count each one. You are not required to
implement `tally`

in this way, but 1 point of partial credit will be given for
a correct implementation of `unique`

that returns the elements in the order
that they first appear in `names`

.

```
; Using this helper procedure is optional. You are allowed to delete it.
(define (unique s)
'YOUR-CODE-HERE 'replace-this)
; Using this helper procedure is optional. You are allowed to delete it.
(define (count name s)
'YOUR-CODE-HERE 'replace-this)
; Passing these tests is optional. You are allowed to delete them.
(define (test-tally-helpers)
(print (list 'testing 'unique))
(assert-equal '(jane) '(unique '(jane jane jane)))
(assert-equal '(jane jack jill) '(unique '(jane jack jane jack jill jane)))
(assert-equal '(jane jack jill) '(unique '(jane jack jane jill jane jack)))
(print (list 'testing 'count))
(assert-equal 3 '(count 'jane '(jane jane jane)))
(assert-equal 0 '(count 'jill '(jane jane jane)))
(assert-equal 2 '(count 'jack '(jane jack jane jack jill jane)))
)
(test-tally-helpers)
(test-tally)
```