Homework 4: Lazy Lists
Table of Contents
1. Pair programming structure
This is a "pair" assignment, which means that you and your partner should use the pair programming model. You should be physically together, sharing a computer and both looking at the same screen.
Each partner has an active role to play during pair programming - please review the instructions on Moodle about pair programming, and make sure you understand what you should be doing when you are the navigator and when you are the driver. You should make sure that over the course of an assignment that you each spend roughly the same amount of time "driving." My recommendation is to set a timer and switch drivers every 10-15 minute.
If pair programming in real-time doesn't work for you and your partner, then you will need to amicably split up and work individually. If you choose this option, you must communicate that to me [Anna]. Please do so as soon as that decision is made. If you split, a new partner typically cannot be assigned until the rest of the class switches partners.
2. Get started
Download the folder with the starter code from the link below. Like for previous homeworks, unzip the folder and move it to where you'd like: most likely the folder for the Docker container. Then get started in VS Code.
If when running tests you run into a permissions error, you can fix this by running the following code in the terminal:
chmod a+x test-e test-m
This tells the computer that all users should be permitted to execute (run)
the files test-e and test-m.
3. Main assignment
You'll complete all parts in main.scm.
3.1. Generate lists
Write a pair of Scheme functions, (gen-list start stop) and (pair-sum? lst
val). The function gen-list will generate a list of consecutive integers,
from start to stop. (If start > stop then the empty list is generated.) For
example:
(gen-list 1 5) ;; Returns (1 2 3 4 5)
The predicate pair-sum? tests whether any two adjacent values in lst sum to
val. For example,
(pair-sum? '(1 2 3) 3) ;; Returns #t
since 1+2=3. Similarly,
(pair-sum? (gen-list 1 100) 1000) ;; Returns #f
since no two adjacent integers in the range 1 to 100 sum to 1000.
3.2. Generate lazy lists
An alternative to generating the entire list of numbers is to instead produce a lazy list. Consider the following example.
(define gen-lazy-list (lambda (start stop) (if (> start stop) #f (cons start (lambda () (gen-lazy-list (+ start 1) stop))))))
When called, gen-lazy-list defines a pair of values. The
car is the first integer in the sequence. The cdr
is a function that, when called, will return another pair. That pair
consists of the next integer in the sequence plus another suspension
function. When the end of the sequence is reached, the function in
the cdr of the pair returns #f, indicating that no more
values can be produced.
Rewrite your solution to pair-sum? as a new function
called pair-sum-lazy? that takes a lazy integer sequence as
defined by gen-lazy-list. pair-sum-lazy? should return
either #t or #f.
3.3. make-lazy
Write a function called make-lazy which takes a traditional Scheme list as a
parameter, and returns a lazy version of that list. Like above, when the end of
the list is reached, the function in
the cdr of the pair returns #f, indicating that no more
values can be produced. Here's an
example:
(make-lazy '(1 5)) ;; Returns (1 . procedure for generating rest of list) (car (make-lazy '(1 5))) ;; Returns 1 (cdr (make-lazy '(1 5))) ;; Returns procedure for generating rest of list ((cdr (make-lazy '(1 5)))) ;; Returns (5 . procedure for generating rest of list) ((cdr ((cdr (make-lazy '(1 5)))))) ;; Returns #f
4. Optional Extensions
Work in this section is 100% optional, and not worth any points. Nonetheless, if you're looking for an extra challenge, I'll sometimes include fun additional exercises to try in this section.
4.1. any-sum-lazy?
Write a function called any-sum-lazy? which is similar to pair-sum-lazy? (it should take a lazy list as a parameter), but instead of checking to see if two adjacent integers add to a value that is provided, instead it should see if any two integers in the list add to the value provided.
5. Other info
You must use recursion, and not iteration. You may not use side-effects (e.g.
set!).
6. How to test and submit your work
6.1. Testing your work
As with previous assignments, there are M tests and E tests. See the section of Scheme Intro 2 labeled "How to test your work" if you need a refresher on how to run these tests.
6.2. Submitting your work
6.2.1. Acknowledging help
Create a file called CollaborationsAndSources.txt, and in it,
indicate in what ways (if any) you collaborated with other people or consulted
outside resources on this assignment.
Did you share strategies with anyone else? Talk about any annoying errors and get advice? These are
fine things to do, and you should note them in the CollaborationsAndSources.txt
file. Give the names of people you talked with and some description of
your interactions. If you used any resources outside of notes taken in class or the homework/lab starter files that
Anna provided, that is also something to note.
If you didn't talk with anyone or use any outside sources, please note
that explicitly in CollaborationsAndSources.txt.
6.2.2. Generating the submission file and uploading to Gradescope
After completing CollaborationsAndSources.txt and finishing the
assignment, run ./zipitup (if you get a permissions error, run chmod u+x ./zipitup first).
This script will create a zip file XXX_submission.zip where XXX is the assignment name or number.
Upload this file to Gradescope.
On Gradescope, make sure to add your partner if you worked with a partner. This page has detailed instructions for how to do that.
On Gradescope, you should see autograder output for the same tests as you ran locally. There is a small chance that the tests will fail on Gradescope, even if they passed on your own computer. Usually this means that you coded something in a different way than we expected when writing the autograders. We will be grading based on the results of the tests on Gradescope, so make sure to pay attention to the results of the tests there. (If you run into this issue, check that you are submitting to the correct assignment on Gradescope. Then try resubmitting and rerunning the autograder. If the error messages are legible, feel free to debug further, but it's also fine to reach out to Anna or the graders at this point.)
6.2.3. Grading
You'll earn at least an M if the following conditions are all met:
- All M tests pass
- A visual inspection of your code shows that you have not hyper-tailored your code to pass the tests. Hyper-tailoring your code would be doing things like checking for the exact input from the test, meaning you haven't written your code in a way that would work for similar inputs.
- You have a
CollaborationsAndSources.txtfile with the information described above.
You'll earn an E if:
- All conditions above for an M are met.
- All the E tests pass.
- Your code is not significantly more complex than needed to accomplish the task.
- You have a comment before each function describing what the function does (its input/output behavior, not a play-by-play of "first checks… then makes a recursive call …").
- Your code follows good style convention (we will get more strict on this as we progress with each language).
If your code does not meet the criteria for an M or an E, then you'll earn a
grade of NA (Not Assessable) or SP (Some Progress) for the assignment. Not Assessable means that your submission does not
have an attempt at one or more functions in the assignment. Some Progress means
that your submission has some code (in the correct language) for all functions in the
assignment, but that the code does not pass all of the M tests, is
hyper-tailored to the tests, and/or is missing a CollaborationsAndSources.txt
file.
You are welcome to revise your submission until the revision deadline (see Gradescope).
If you revise your submission, double-check to make sure that the autograder tests pass and that you
have included CollaborationsAndSources.txt.
Assignment originally designed by Dave Musicant - thanks for sharing!