These exercises are about working with the generated (lazy) list package. These exercises require three files from the CS 325 Code Library:

Many of these problems are based on the exercises and examples in the stream chapter of The Structure and Interpretation of Computer Programs by Abelson and Sussman.

None of these exercises should require changing the code in glist.lisp. All should be solved by defining new functions in the glist-tests package, using just the public functions, such as delay, gcar, and so on.

Many of the exercise tests use a generated list that will signal an error if your code extracts more than a certain number of items. This is to catch code that doesn't properly delay execution and extraction as long as possible.

Exercise: Basic glist utilities

Function name: gnth, gmap, gfilter

Define (gnth n glist) to return the Nth (0-based) element of glist, if any, or NIL.

Define (gmap function glist) to take a function of one argument and a generated list, and return a new generated list, whose elements are the result of applying function to each element of glist. gmap should work for infinite lists, e.g., (gmap #'1+ (gintegers 1)) should produce the infinite list (without going into an endless loop!) (2 3 4 ...).

Define (gfilter function glist) to take a function of one argument and a generated list, and return a new generated list, whose elements are those elements of glist for which function returns true. gfilter should work for infinite lists, e.g., (gfilter #'oddp (gintegers 1)) should produce the infinite list (without going into an endless loop!) (1 3 5 ...).

Test with (run-tests gnth), (run-tests gmap), and (run-tests gfilter), respectively.

.

Exercise: GSCAN and GREDUCE

Function name: gscan, greduce

Define (gscan fn glist [val]) to take a function fn of two arguments, a generated list of elements g1, g2, g3, ..., and an optional value, default nil, and return a new generated list with the elements (v1 v2 v3...), where v1 = (fn val g1), v2 = (fn v1 g2), v3 = (fn v2 g3), ...

gscan is named thus because of its similarity to the Haskell function scanl.

Define (greduce fn glist &key start end initial-value) to take a function fn of two arguments, a generated list, a start value (default 0), and an end value (default nil), and an initial-value (default nil). It should return a value (not a generated list) that is the same as the value returned by (car (last (gextract (gscan fn glist val) n))). However, greduce should not construct any intermediate list of values.

Test with (run-tests gscan) and (run-tests greduce).

Faculty: Chris Riesbeck
Time: Monday, Wednesday, Friday: 1pm - 2pm
Location:Annenberg G15

Contents

Important Links