Homework 9: Scheme Lists
Due by 11:59pm on Thursday, April 20
Instructions
Download hw09.zip. Inside the archive, you will find a file called
hw09.scm, along with a copy of the ok
autograder.
Submission: When you are done, submit the assignment by uploading all code files you've edited to Gradescope. 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 Gradescope. 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.
Q1: Ascending
Implement a procedure called ascending?
, which takes a list of numbers asc-lst
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
.Note: The question mark in
ascending?
is just part of the function name and has no special meaning in terms of Scheme syntax. It is a common practice in Scheme to name a function with a question mark at the end if the function returns a boolean value indicating whether or not a condition is satisfied. For instance,ascending?
is a function that essentially asks "Is the argument in ascending order?",null?
is a function that asks "Is the argumentnil
?",even?
asks "Is the argument even?", etc.
(define (ascending? asc-lst)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q ascending -u
python3 ok -q ascending
Q2: My Filter
Write a procedure my-filter
, which takes a predicate pred
and a list s
, 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 s)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q filter -u
python3 ok -q filter
Q3: 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
Q4: No Repeats
Implement no-repeats
, which takes a list of numbers lst
as input and returns
a list that has all of the unique elements of lst
in the order that they first
appear, but no repeats. For example, (no-repeats (list 5 4 5 4 2 2))
evaluates to (5 4 2)
.
Hint: How can you make the first time you see an element in the input list be the first and only time you see the element in the resulting list you return?
Hint: You may find it helpful to use the
my-filter
procedure with a helperlambda
function to use as a filter. To test if two numbers are equal, use the=
procedure. To test if two numbers are not equal, use thenot
procedure in combination with=
.
(define (no-repeats lst)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q no_repeats -u
python3 ok -q no_repeats
Exam Practice
The following are some Scheme List exam problems from previous semesters that you may find useful as additional exam practice.
- Fall 2022 Final, Question 8: A Parentheses Scheme
- Spring 2022 Final, Question 11: Beadazzled, The Scheme-quel
- Fall 2021 Final, Question 4: Spice
Submit
Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.