Lazy Lists (individual assignment)
Table of Contents
This assignment is to be done individually. You can talk to other people in the class, me (Dave), and any of the course staff (graders, lab assistants, teaching assistants, prefects) for ideas and to gain assistance. You can help each other debug programs, if you wish. The code that you write should be your own, however, and you shouldn't directly share your code with others. See the course syllabus for more details or just ask me if I can clarify.
1 Get started
1.1 Use GitHub classroom to create a repository for your assignment
The first think you'll need to do is to create a repository for your project using GitHub classroom. Visit this GitHub classroom link (which I've placed in Moodle). Log into GitHub if need to. GitHub should then hopefully respond with a screen that says "You're ready to go!" and will supply you with a link for the repository that you are creating. Click on that link, and you should be taken to the repository.
1.2 Clone your repository into Repl.it
Since this is an individual assignment, you'll again use the my-work
repl in Repl.it that you created. In Repl.it, start up your my-work
repl, and then make sure that you are in your home directory in the terminal window. You can always navigate there by typing
cd ~
in the terminal window. To further confirm, type pwd
(which is short for "print working directory.") You should see /home/runner
. If you see something different, you're not in the home directory, so try again or ask for help.
In a different browser tab (leave the one with Repl.it open), visit our our class GitHub organization page online. Once you've landed there, you should see the GitHub repository you created in the GitHub Classroom step above. It should be named scheme-lazylist-username
(where username is your username). Contact us for help if the repository isn't there. Click on that repository title. This should take you to the home page for that repository. There is a green box on the page that says "Clone or download." Click that box, and make sure it says "Clone with HTTPS." Highlight the https link shown, and copy it to the clipboard. The link that you're copying should look something like
https://github.com/carleton251-term/scheme-lazylist-username.git
… though your username and term will be different.
Then navigate back to the Repl.it tab with the repl that you created above, and click on the terminal window within your new repl. Your next step is to clone the repository from GitHub. To do that, type git clone, then a space, then paste in the URL from the github page that you copied from above. (To paste, you might need to right-click in the terminal window and choose paste rather than using a keyboard shortcut.)
For example, I would type the following, though your username and term will be different:
git clone https://github.com/carleton251-term/scheme-lazylist-username.git
You'll be prompted to enter your GitHub username and password.
If all goes well, you should receive a directory, titled scheme-lazylist-username. If you type ls
at the prompt, you should be able to see it. It will also appear in your file browser window with Repl.it on the left. Then navigate into that directory by typing in:
cd scheme-lazylist-username
… and you should be all set to work.
2 Main assignment
2.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) ---> (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) ---> #t
since 1+2=3. Similarly,
(pair-sum? (gen-list 1 100) 1000) ---> #f
since no two adjacent integers in the range 1 to 100 can sum to 1000.
2.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 Capstone work
Work in this section is 100% optional, and not worth any points. Nonetheless, if you're looking for an extra challenge, these are fun additional exercises to try.
3.1 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.
3.2 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.
4 Other info
You must use recursion, and not iteration. You may not use
side-effects (e.g. set!
).
5 How to test and submit your work
Go back and look at the sections at the end of Scheme Lab 2 labeled "How to test your work" and "How to submit your work." Those should apply identically here. Follow those instructions, and you should hopefully be all set.