CSE 1729 – Introduction to Principles of Programming November 29, 2016 Laboratory Assignment 12
Ob jectives
• Program in “signal-processing” style • Work with streams
• Write and use some stream tools
Activities
To effectively write stream code you will need the Scheme primitives to deal with the stream data type. Add the following code to the beginning of your Racket file. You should be working in R5RS Scheme.
(define-syntax cons-stream (syntax-rules ()
((cons-stream head tail) (cons head (delay tail)))))
(define (stream-car x) (car x))
(define (stream-cdr x) (force (cdr x)))
(define stream-null? null?)
(This code, plus code for tracer, a useful thing, is available in the attached file stream-utils.rkt).
1. To use streams in signal-processing-style code we need to define the primitives. Here are a few to implement that have analogues in list programming. All should be ordered consistent with their stream parameter, and all should take advantage of delayed evaluation by using cons-stream, stream-car, and stream-cdr instead of cons, car, and cdr. Note: some of these were shown on the slides, but be careful as the slides may have had small bugs and should be cleaned up.
(a) (stream-filter p str) returns a stream made up of all of the elements of str for which the function p returns true.
Solution:
(define (stream-filter f str) (if (f (stream-car str))
(cons-stream (stream-car str)(stream-filter f (stream-cdr str))) (stream-filter f (stream-cdr str))))
1
(b) (stream-map f str) returns a stream made up of the results of applying function f to each element of str. Unlike the map function in Scheme this will only work for functions of 1 argument.
Solution:
(define (stream-map f str) (if (null? str)
’()
(cons-stream (f (stream-car str))
(stream-map f (stream-cdr str)))))
(c) (stream-nth index str) returns the nth element of a stream, where an index of 1 corre- sponds to the first element.
Solution:
(define (stream-nth n stream) (if (= n 1)
(stream-car stream)
(stream-nth (- n 1) (stream-cdr stream) )))
2. To make your debugging easier, write the Scheme function (str-to-list str k) which returns a list containing the first k elements of stream str.
Solution:
(define (str-to-list str n)
(cond ((or (null? str)(= n 0)) ’())
(else
(cons (stream-car str)
(str-to-list (stream-cdr str) (- n 1))))))
3. Using your functions above where appropriate, write the following stream functions:
(a) (scale-stream k str)returnsastreammadeupoftheresultsofmultiplyingeachelement of str by k.
2
Solution:
(define (scale-stream factor stream)
(stream-map (lambda (x) (* x factor)) stream))
(b) (add-streams str1 str2) returns a stream made up by adding the elements of the two streams pairwise. E.g., if str1 has the elements (s1 s2 s3) and str2 has the elements (t1 t2 t3), then (add-streams str1 str2) would have the elements (s1+t1 s2+t2 s3+t3).
Solution:
(define (add-streams s1 s2)
;; note: if one stream shorter fill it with zeroes
(cond ((and (null? s1)(null? s2)) ’()) ((null? s1) s2)
((null? s2) s1) (else
(cons-stream (+ (stream-car s1)(stream-car s2))
(add-streams (stream-cdr s1) (stream-cdr s2))))))
(c) (mult-streams str1 str2) returns a stream made up by multiplying the elements of the two streams pairwise. E.g., if str1 has the elements (s1 s2 s3) and str2 has the elements (t1 t2 t3), then (mult-streams str1 str2) would have the elements (s1*t1 s2*t2 s3*t3).
Solution:
(define (mult-streams s1 s2)
;; note: if one stream shorter fill it with zeroes
(cond ((and (null? s1)(null? s2)) ’())
((null? s1)(cons-stream 0 (mult-streams s1 (stream-cdr ((null? s2)(cons-stream 0 (mult-streams s2 (stream-cdr (else
s2)))) s1))))
(cons-stream (* (stream-car s1)(stream-car s2))
(mult-streams (stream-cdr s1) (stream-cdr s2))))))
(d) (append-streams str1 str2) returns a stream containing all of the elements of str1 followed by all of the elements of str2. (What happens if str1 is an infinite stream?)
Solution:
(define (append-streams s1 s2) (cond ((stream-null? s1) s2)
(else
(cons-stream (stream-car s1)
(append-streams (stream-cdr s1) s2)))))
4. Using your functions above where appropriate, write the following stream functions:
3
(a) (enumerate-integer-stream) returns a stream made up of the non-negative integers in ascending order. HINT–use a helper function.
(b) (odd-factors-of k) returns a stream made up all odd non-negative numbers that are evenly divisible by k. Write two different solutions to this in terms of your stream functions in signal-processing style.
Solution:
(define (odd-factors-of k)
(stream-filter odd? (scale-stream k (enumerate-integer-stream))))
(define (odd-factors-of k)
(stream-filter (lambda(x)(and (odd? x)(= (modulo x k) 0)))
(enumerate-integer-stream)))
(c) (partial-sums str) returns a stream containing the partial sums of str, that is, if s1, s2, s3,s4,… are the elements of str, the result stream contains s1, s1+s2, s1+s2+s3, s1+s2+s3+s4, …
Solution:
(define (partial-sums str)
(define (partial-sum-extend str sumprev)
(cons-stream (+ (stream-car str) sumprev) (partial-sum-extend (stream-cdr str)
(+ (stream-car str) sumprev))))
(partial-sum-extend str 0))
(d) (square-stream) returns a stream made up of the squares of the non-negative integers in ascending order.
Provide three different implementations of this using your code above. Which one is best (or worst), and why?
4
Solution:
(define (enumerate-integer-stream) (define (ints-from a)
(cons-stream a (ints-from (+ a 1)))) (ints-from 0))
Solution:
(define (square-stream1) (define (helper str)
(mult-streams str str))
(helper (enumerate-integer-stream)))
(define (square-stream2) (stream-map (lambda(x)(* x x))
(enumerate-integer-stream)))
(define (square-stream3) ;; worst–generates a lot more values (stream-filter (lambda(x)(=(round (sqrt x))(sqrt x)))
(enumerate-integer-stream)))
5