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 thing 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 Create a repl in Repl.it
Once you see your repository in GitHub (not Repl.it), you should see a button labeled "Work in Repl.it." Click it. That should set up a new repl in Repl.it, and you should be all set to work. As always, make sure the repl created in Repl.it is private.
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 doesn't contribute towards your grade. 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.