Diagnostic 6: Week 6 review

Diagnostics are meant for you to check your understanding of the week's material. They are not worth any points and are not counted towards midterm recovery points; instead, diagnostics are solely for your benefit. If you find yourself struggling with the questions in this diagnostic, consider signing up for Tutoring.

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!