Homework 4: Scheme
Due by 11:59pm on Tuesday, 7/17
Instructions
Download hw04.zip.
Our course uses a custom version of Scheme (which you will build for Project 4) included in the starter ZIP archive. To start the interpreter, type
python3 scheme
. To run a Scheme program interactively, typepython3 scheme -i <file.scm>
. To exit the Scheme interpreter, type(exit)
.
Submission: When you are done, submit with python3 ok
--submit
. You may submit more than once before the deadline; only the
final submission will be scored. Check that you have successfully submitted
your code on okpy.org. See Lab 0 for more instructions on
submitting assignments.
Using Ok: If you have any questions about using Ok, please refer to this guide.
Readings: You might find the following references useful:
Grading: Homework is graded based on effort, not correctness. However, there is no partial credit; you must show substantial effort on every problem to receive any points.
Q0: Midsummer Survey
Congratulations on making it to Week 4 of the course! Please fill out this
survey to give feedback on the course so far. Once you complete the survey,
you will receive a passphrase in the confirmation screen. Assign that
passphrase as a string to the name passphrase
in the hw04.py
file. For
example, if the code at the end of the survey was scheme
, the assignment
statement should look like this:
passphrase = 'scheme'
Use Ok to test your code:
python3 ok -q survey
Q1: Sign
Using a cond
expression, define a procedure sign
that takes in one
parameter x
and returns -1 if x
is negative, 0 if x
is zero, and 1 if x
is positive.
(define (sign x)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q sign -u
python3 ok -q sign
Q2: Pow
Implement a procedure pow
for raising the number b
to the power of a
nonnegative integer n
that runs in Θ(log n) time.
Hint: Consider the following observations:
- b2k = (bk)2
- b2k+1 = b(bk)2
You may use the built-in predicates
even?
andodd?
.
(define (square x) (* x x))
(define (pow b n)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q pow -u
python3 ok -q pow
Q3: Cadr and Caddr
Define the procedures cadr
and caddr
, which return the second
and third elements of a list, respectively:
(define (cddr s)
(cdr (cdr s)))
(define (cadr s)
'YOUR-CODE-HERE
)
(define (caddr s)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q cadr-caddr -u
python3 ok -q cadr-caddr
Q4: Ordered
Implement a procedure called ordered?
, which takes a list of numbers and
returns True
if the numbers are in nondescending order, and False
otherwise. Numbers are considered nondescending if each subsequent number is
either larger or equal to the previous, that is:
1 2 3 3 4
Is nondescending, but:
1 2 3 3 2
Is not.
Hint: The built-in
null?
function returns whether its argument isnil
.
(define (ordered? s)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q ordered -u
python3 ok -q ordered
Q5: No Dots!
Implement the procedure nodots
, which takes a nested list of numbers that
may not be well-formed and returns a nested list with the same content and
structure, but which does not have any dots when displayed. Lists are not
well-formed if they do not properly terminate in a null list. In such cases,
the list will print with a dot before the final item to indicate that its
last two items are contained in a single pair. For example,
(cons 1 (cons 2 3))
would print as
(1 2 . 3)
for which nodots
should substitute
(1 2 3)
You may find the built-in
null?
andpair?
predicates useful.
(define (nodots s)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q nodots -u
python3 ok -q nodots
Sets as Ordered Lists
A set is a type of collection that stores unique elements. The main operation associated with sets is checking whether a given value is in a set.
There is no such built-in set data type in Scheme, but one way to represent a set is by using an ordered list, where the ordering is used to speed up search (although only by a constant factor). The following few questions explore this idea. Specifically, we will represent sets using Scheme lists ordered from least to greatest with no repeated elements.
Q6: Add
First, define add
, which takes a set s
and a value v
as arguments. It
returns a representation of a set containing the values in s
and the value
v
. There should be no repeated elements in the return value.
We've provided a function empty?
which returns #t
if the given set s
has
no elements.
(define (empty? s) (null? s))
(define (add s v)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q add -u
python3 ok -q add
Q7: Contains
Next, define contains?
, which returns whether a set s
contains value v
.
; Sets as sorted lists
(define (contains? s v)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q contains -u
python3 ok -q contains
Q8: Intersect and Union
Finally, define intersect
, which returns a set containing only values that
appear in both sets s
and t
, and union
, which returns a set containing
all values that appear in either set s
or t
.
Your implementation for both functions should run in linear time in the length of the input sets.
(define (intersect s t)
'YOUR-CODE-HERE
)
(define (union s t)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q intersect -u
python3 ok -q intersect
python3 ok -q union -u
python3 ok -q union