Homework 4: Lazy Lists

You'll download the folder with the starter code from the link below. Like for homeworks 1 and 2, unzip the folder and move it to where you'd like: the folder for the Docker container if you're using Docker, or COURSES if you're not. Then get started in VS Code (see Homework 1 if you get stuck).

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.

Click here to download the starter files.

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.

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.

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

Go back and look at the sections at the end of Scheme Intro 2 labeled "How to test your work". Everything there about how to run M tests and E tests applies identically here.

You'll submit your work on Gradescope. First, create a CollaborationsAndSources.txt file in the same folder as your code. In that file, indicate in what ways (if any) you collaborated with other people on this assignmen. Indicate any people you talked about the assignment with besides your partner (if you had one), me (Anna), and our prefect. 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 our course materials, that is also something to note in Collaborations.txt. If you didn't talk with anyone or use any outside sources, please note that explicitly in CollaborationsAndSources.txt. Look back at the Scheme intro 1 instructions if you want more details on the CollaborationsAndSources.txt file.

After making CollaborationsAndSources.txt and finishing the assignment, upload your files on 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.

Note that if you submit a zip on Gradescope, you should submit a zip of the files, not a zip of the folder that contains the files. If all tests fail on Gradescope but they're working on your machine, this is likely the problem.

On Gradescope, you should see autograder output for the same tests as you ran locally. There is a very small but possible chance that you have coded something highly unexpected that cause the tests pass on the computer you’re working on, but not on Gradescope. We will be grading this assignment based on the results of the tests on Gradescope, so you should make sure to pay attention to how the tests run there as well when you submit.

For 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 see Homework policies for more on this).
• You have a CollaborationsAndSources.txt 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 …").

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 have two revisions to use at any point during the term if you earn an SP or M grade and would like to revise your code and have us change your grade.