Homework 6: Scheme, Scheme Lists, Tail Calls
Due by 11:59pm on Thursday, August 4
Instructions
Download hw06.zip. Inside the archive, you will find a file called
hw06.scm, along with a copy of the ok
autograder.
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 correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.
Required Questions
Getting Started Videos
These videos may provide some helpful direction for tackling the coding problems on this assignment.
To see these videos, you should be logged into your berkeley.edu email.
Code Writing Questions
Q1: Thane of Cadr
Define the procedures cadr
and caddr
, which return the second
and third elements of a list, respectively. If you would like a quick refresher on scheme syntax consider looking at Lab 08 Scheme Refresher.
(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
Q2: Interleave
Implement the function interleave
, which takes a two lists lst1
and lst2
as
arguments. interleave
should return a new list that interleaves the elements
of the two lists. (In other words, the resulting list should contain elements
alternating between lst1
and lst2
.)
If one of the input lists to interleave
is shorter than the other, then
interleave
should alternate elements from both lists until one list has no
more elements, and then the remaining elements from the longer list should be
added to the end of the new list.
(define (interleave lst1 lst2)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q interleave -u
python3 ok -q interleave
Q3: My Filter
Write a procedure my-filter
, which takes a predicate pred
and a list lst
, and
returns a new list containing only elements of the list that satisfy the
predicate. The output should contain the elements in the same order that they
appeared in the original list.
Note: Make sure that you are not just calling the built-in filter
function in Scheme - we are asking you to re-implement this!
(define (my-filter pred lst)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q filter -u
python3 ok -q filter
Q4: Concatenate
Write a tail-recursive function concatenate
, which takes in s
, a list of lists,
and concatenates all the elements together into one list.
Hint: Recall the built-in
append
function
(define (concatenate s)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q concatenate -u
python3 ok -q concatenate