# Diagnostic 6: Week 6 review

## Scheme

### Question 1

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) (= (f1 x) (f2 x))))
;;; Tests
; (add-two 2) evaluates to 4, (square 2) also evaluates to 4
((equal-answer add-two square) 2)
; expect True
; (add-two 3) evaluates to 5, (square 3) instead evaluates to 9
((equal-answer add-two square) 3)
; expect False
((equal-answer (lambda (x) (* 5 x)) square) 5)
; expect True
((equal-answer (lambda (x) (* 5 x)) square) 1)
; expect False
((equal-answer (lambda (x) x) square) 1)
; expect True
((equal-answer square (lambda (x) x)) 1)
; expect True
((equal-answer (lambda (x) x) square) 5)
; expect False
((equal-answer square (lambda (x) x)) 5)
; expect False
((equal-answer (lambda (x) (/ x 1)) (lambda (x) x)) -1)
; expect True
```

### Question 2: all-satisfies

Implement a function `(all-satisfies lst pred)`

that returns `True`

if all of
the elements in `lst`

satisfy `pred`

.

```
(define (all-satisfies lst pred)
'YOUR-CODE-HERE
(if (null? lst)
True
(and (pred (car lst))
(all-satisfies (cdr lst) pred))))
;;; Tests
(all-satisfies nil even?)
; expect True
(all-satisfies '(2 4 6) even?)
; expect True
(all-satisfies '(2 3 6) even?)
; expect False
(all-satisfies '((1 2) (3 4 5) (6)) pair?)
; expect True
```

### Question 3: Remove

Implement a function `remove`

that takes in a list and
returns a new list with *all* instances of `item`

removed from `lst`

.

```
(define (remove item lst)
'YOUR-CODE-HERE
(cond ((null? lst) '())
((equal? item (car lst)) (remove item (cdr lst)))
(else (cons (car lst) (remove item (cdr lst))))))
;;; Tests
(remove 3 nil)
; expect ()
(remove 3 '(1 3 5))
; expect (1 5)
(remove 5 '(5 3 5 5 1 4 5 4))
; expect (3 1 4 4)
```

### Question 4

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
(if (or (null? s) (null? (cdr s)))
0
(+ (num-adjacent-matches (cdr s))
(if (= (car s) (cadr s)) 1 0))))
;;; Tests
; no pairs
(num-adjacent-matches '(1 2 3 4))
; expect 0
; one pair of 1's
(num-adjacent-matches '(1 1 2 3))
; expect 1
; one pair of 1's, one pair of 2's
(num-adjacent-matches '(1 1 2 2))
; expect 2
; three pairs of 1's
(num-adjacent-matches '(1 1 1 1))
; expect 3
(num-adjacent-matches '(6 6 6 1 6 1))
; expect 2
(num-adjacent-matches '(6))
; expect 0
(num-adjacent-matches '(6 1))
; expect 0
(num-adjacent-matches '(6 1 6 1 6 1))
; expect 0
(num-adjacent-matches '(6 6))
; expect 1
(num-adjacent-matches '(6 6 6 1 6 1))
; expect 2
(num-adjacent-matches '(0 1 6 6 6 1))
; expect 2
(num-adjacent-matches '(4 4 3 3 2 2 1 1))
; expect 4
```

Our base cases are when our input list `s`

is too short to have any adjacent
matches. We call `num-adjacent-matches`

recursively on `(cdr s)`

to count the
adjacent matches in the rest of the list `s`

, then add 0 or 1 depending on
whether the first and second elements of `s`

are equal.

### Question 5

Implement `how-many-dots`

, which takes in a nested scheme list `s`

and returns
the number of dots that appear when it is displayed by the interpreter (not
counting decimal points). You may assume that `s`

is a nested list that
contains only numbers.

*Hints*: A dot appears when the second element of a pair is not a well formed
list. The procedures `pair?`

, `null?`

, and `number?`

test whether a value is a pair, `nil`

, or a number, respectively.

```
(define (how-many-dots s)
'YOUR-CODE-HERE
(if (not (pair? s))
0
(+ (if (and (not (pair? (cdr s)))
(not (null? (cdr s))))
1
0)
(how-many-dots (car s))
(how-many-dots (cdr s))))
;;; Tests
(how-many-dots '(1 2 3))
; expect 0
(how-many-dots '(1 2 . 3))
; expect 1
(how-many-dots '((1 . 2) 3 . 4))
; expect 2
(how-many-dots '((((((1 . 2) . 3) . 4) . 5) . 6) . 7))
; expect 6
(how-many-dots '(1 . (2 . (3 . (4 . (5 . (6 . (7)))))))
; expect 0
```

### Question 6

Write a procedure `substitute`

that takes three arguments: a list `s`

, an `old`

word, and a `new`

word. It returns a list with the elements of `s`

, but with
every occurrence of `old`

replaced by `new`

, even within sub-lists.

```
(define (substitute s old new)
'YOUR-CODE-HERE
(cond ((null? s) nil)
((pair? (car s)) (cons (substitute (car s) old new)
(substitute (cdr s) old new)))
((= (car s) old) (cons new
(substitute (cdr s) old new)))
(else (cons (car s) (substitute (cdr s) old new)))))
;;; Tests
(substitute '(romeo romeo wherefore art thou romeo) 'romeo 'paris)
; expect (paris paris wherefore art thou paris)
(substitute '((to be) or not (to (be))) 'be 'eat)
; expect ((to eat) or not (to (eat)))
(substitute '(a b (c) d e) 'foo 'bar)
; expect (a b (c) d e)
```

## Interpreters

See the Scheme project!