#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))