Assignment 5 - Lazy Lists

Due: Friday, April 10, 2026, at 10pm

Starter code: a5_lazylists.zip
Upload solutions via Gradescope

Goals

This assignment is designed to help you with the following:

  • practice working with partial application
  • write and use functions that return functions

Collaboration policy

For this assignment, you may work alone or with a partner, but you must type up all of the code yourself. (It is therefore unexpected for two code submissions to be completely identical.)

You may also discuss the assignment at a high level with other students.

You should list any student with whom you discussed the assignment, and the manner of discussion (high level, partner, etc.) in your readme.txt file.

If you work alone, you should say so instead.

Assessment

Core requirements:

  • all CR tests pass
  • your code is not hyper-tailored to pass the tests
  • you use recursion, not iteration
  • you do not use side effects (e.g., set!)
  • readme.txt contains your collaboration statement, sources, and reflection

Advanced requirements:

  • satisfy the Core requirements
  • all AD tests pass
  • your code is not significantly more complex than needed to accomplish the task
  • each function has a comment before it describing its high-level behavior
  • your code uses good Scheme coding style

Getting started

As before, you should download the starter files, unzip that file, and copy the folder to where you’ll work (probably your ProgrammingLanguages folder). Refer to the Assignment 1 instructions if you’re unsure what to do.

Part A: Normal lists

Part A1: gen-list

The function gen-list should generate a list of consecutive integers, from start to stop, inclusive:

(gen-list 1 5)                             ; evaluates to: (1 2 3 4 5)

If start > stop then gen-list should return the empty list.

Part A2: pair-sum?

The predicate pair-sum? should check whether any two adjacent values in a given Scheme list sum to the given value. For example:

(pair-sum? '(1 2 3 4) 5)                   ; evaluates to: #t

as 2+3 = 5. Similarly,

(pair-sum? '(gen-list 1 100) 1000)         ; evaluates to: #f

as no two adjacent integers in the range 1 to 100 sum to 1000.

Part B: 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)
        '()
        (cons start
              (lambda () (gen-lazy-list (+ start 1) stop))))))

When called, gen-lazy-list returns a pair of values:

  • The car is the first integer in this sequence (i.e., start).

  • the cdr is a function that, when called, will return another such pair. That pair consists of the next integer in the sequence plus another suspension function. When the end of the sequence is reached, this function instead returns '(), indicating that no more values can be produced.

Add this function to your code in main.scm.

Part B1: pair-sum-lazy?

Write a new version of your pair-sum? predicate called pair-sum-lazy? that takes a lazy integer sequence as defined by gen-lazy-list and returns either #t or #f depending on whether any two adjacent values in the lazy integer sequence sum to the given value.

Part B2: make-lazy

Write a function called make-lazy that 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 '(), indicating that no more values can be produced.

Here’s an example:

(make-lazy '(1 5))                          ; evaluates to: (1 . <procedure for generating rest of list>)
(car (make-lazy '(1 5)))                    ; evaluates to: 1
(cdr (make-lazy '(1 5)))                    ; evaluates to: <procedure for generating rest of list>
((cdr (make-lazy '(1 5))))                  ; evaluates to: (5 . <procedure for generating rest of list>)
((cdr ((cdr (make-lazy '(1 5))))))          ; evaluates to: ()

Part C (AD only)

Part C1: first-n

Write a function called first-n that takes a lazy list and an integer and returns an ordinary Scheme list contianing the first n values in the lazy list. If the lazy list contains fewer than n values then all of the values in the lazy list are returned. You may assume that n is an integer greater than or equal to 1. If the lazy list is empty, then first-n returns an empty list ('()).

Here’s an example:

(first-n (gen-lazy-list 4 10) 3)             ; evaluates to: (4 5 6)

Part C2: filter-multiples

Write a function filter-multiples that returns a new lazy list that has n and all integer multiples of n removed from the lazy list.

For example:

(filter-multiples (make-lazy '(2 3 4 5 6)) 2)           ; evaluates to: a lazy list corresponding to (3 5)
(filter-multiples (make-lazy '(3 4 5 6 7 8)) 3)         ; evaluates to: a lazy list corresponding to (4 5 7 8)

Part D: Optional extensions

The work in this section is 100% optional and does not contribute to your grade in any way. Still, if you’re looking for an extra challenge or ideas on what to practice to study the material, there will be occasional “optional extensions” sections of assignments that contain one or more additional exercises to try.

For this assignment, you are encouraged to implement the following two functions:

  • nth
  • count-smaller-numbers

Part D1: nth (not graded) 

(nth lazy-list n)

Define a function nth that takes a lazy list and an integer and returns the n-th value in the lazy list (counting from 1). If the lazy list contains fewer than n values, then '() is returned.

Part D2: count-smaller-numbers (not graded) 

(count-smaller-numbers lazy-list num)

Define a function count-smaller-numbers that takes a lazy list and a number num and counts the number of entries in the lazy list that are less than num.

Testing your work

As with the previous assignment, there are CR and AD tests for core and advanced functionality (mapping to requirements above). Look at the instructions from A2 if you want a refresher on how to run this tests.

Submitting your work

As with the previous assignments, you will submit your work in two files.

Scheme code

The file main.scm should contain all of your procedures. Make sure to add a comment above each of your procedures (including any helper functions you choose to write) to describe its behavior at a high level (e.g., what it takes as input and what it returns as output).

Readme

For each assignment for this course you will also need to submit a file readme.txt in which you should write:

  1. Your collaborations with anyone on the assignment
  2. Your use of any outside sources on the assignment
  3. Your reflection

You should be specific about your collaborations and sources – they shouldn’t just be empty or lists of names of people. If you worked alone and/or did not use any outside sources, you should say so.

For your reflection, spend a couple of sentences answering the following:

  • Were there any particular issues or challenges you dealt with in completing this assignment?
  • How long did you spend on this assignment?

Submitting to Gradescope

Once you have your two files, you will combine them into a single file using this command:

./zipitup

(make sure you’re in the terminal in the assignment folder). If you get an error about file permissions, first run chmod a+x zipitup.

Submit your .zip file to Gradescope at this link.

Note that it is possible (although unlikely) that the tests will pass on your computer but fail on Gradescope. If this happens, it’s probably because you coded something in an unusual way. Double-check that you’re submitted to the correct assignment and then check if any error messages can help you troubleshoot. If you’re still having issues, check with Tanya.