#lang racket #| CSC324 Fall 2019: Lab 6 |# ;------------------------------------------------------------------------------- ; * Task 0: Lazy list implementation * ;------------------------------------------------------------------------------- #| This section defines an implementation of streams using lazy lists. The key idea is in s-cons, which is exactly analogous to Racket's cons, except that it wraps its arguments in *thunks* so that they are only evaluated when accessed, rather than when passed to s-cons, as they would be during standard eager evaluation order. List value/function Stream analogue ------------------- --------------------- null (empty list) s-null (empty stream) null? s-null? cons s-cons first s-first rest s-rest |# ; Empty stream value, and check for empty stream. (define s-null 's-null) (define (s-null? stream) (equal? stream s-null)) #| (thunk ) : A Racket expression. (*Not* a datum, the actual expression.) Rewrites this into a thunk (i.e., nullary function) that wraps . As we saw in lecture, this is used to delay evaluation of . (This is actually a built-in macro, but we've provided an implementation here to be explicit.) |# (define-syntax thunk (syntax-rules () [(thunk ) (lambda () )])) #| (s-cons ) : A Racket expression. : A stream (e.g., s-null or another s-cons expression). Returns a new stream whose first value is , and whose other items are the ones in . Unlike a regular list, is wrapped in a thunk, so it isn't evaluated until called (see s-rest below). |# (define-syntax s-cons (syntax-rules () [(s-cons ) (cons (thunk ) (thunk ))])) ; These two define the stream-equivalents of "first" and "rest". ; We need to use car and cdr here for a technical reason that isn't important. ; Note that each one both accesses a thunk and then calls it to return the ; value stored within it. (define (s-first stream) ((car stream))) (define (s-rest stream) ((cdr stream))) (module+ test ; TODO: Fill in all the (void)s below with relevant stream values/functions ; so that all the tests pass. (require rackunit) (test-true "Create an empty stream and check that it's empty." (void)) (test-false "Create a stream of length 1 and check that it's non-empty." (void)) (test-equal? "Create a stream of length 1 containing the number 165 and access the item." (void) (first (cons 165 null))) (test-equal? "Create a stream of length 3 containing the numbers 4, 5, 6 and access the third item." (void) 6)) ;------------------------------------------------------------------------------- ; * Task 1: Lazy list functions * ;------------------------------------------------------------------------------- #| (s-sum numbers) numbers: a stream of numbers Returns the sum of the numbers in the stream. |# (define (s-sum numbers) (if (s-null? numbers) 0 (void))) #| (s-sum-tail numbers acc) A tail-recursive version of s-sum. |# (define (s-sum-tail numbers acc) (void)) #| (s-member v stream) Analogous to Racket's `member` list function. (Note that when `v` is in the stream, this returns a stream! See https://docs.racket-lang.org/reference/pairs.html. |# (define (s-member v stream) (void)) #| (stream->list stream) stream: A stream Returns a list containing the values in this stream. |# (define (stream->list stream) (void)) #| (s-range start end) start, end: integers. Precondition: start <= end Returns a stream containing the numbers start, start+1, ..., end-1. Returns an empty stream if (equal? start end). |# (define (s-range start end) (void)) #| (s-take stream n) stream: A stream n: A non-negative integer Returns a new stream that contains the first n elements of `stream`, or all of the elements of `stream` if it has fewer than n elements. |# (define (s-take stream n) (void)) ;------------------------------------------------------------------------------- ; * Task 2: Infinite lists * ;------------------------------------------------------------------------------- #| Hints: 1. These functions should all be explicitly recursive (i.e., call themselves). It's up to you to figure out how, exactly. 2. You can test your work using `s-take` and `stream->list` from above. |# #| (repeat x) x: A value Returns an infinite stream whose elements are all equal to `x`. |# (define (repeat x) (void)) #| (range-to-infinity n) n: An integer Returns an infinite stream of the integers n, n+1, n+2, ... |# (define (range-to-infinity n) (void)) #| (cycle x1 ...) x1 ...: A value Takes an arbitrary, but non-zero, number of values, and returns an infinite stream whose elements are the arguments to cycle, repeated infinitely often. For example, (cycle 1 2 3) should return the stream `1,2,3,1,2,3,1,2,3,...` |# (define cycle (void))