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)