;;; ADU SICP, October 2000
;;; Code for lecture on streams
;;; stream-ref returns the nth element of a stream (where the first
;;; element of the stream is counted as the 0th)
;;;
;;; NOTE: different from code on p.319 of textbook, which doesn't
;;; check for stream-null?
(define (stream-ref s n)
(cond ((stream-null? s) the-empty-stream)
((= n 0) (stream-car s))
(else (stream-ref (stream-cdr s) (- n 1)))))
;;; stream-map maps a procedure onto a stream
(define (stream-map proc s)
(if (stream-null? s)
the-empty-stream
(cons-stream (proc (stream-car s))
(stream-map proc (stream-cdr s)))))
;;; stream-for-each applies a procedure to each element of a
;;; stream, but does not build the answers back up into a stream
(define (stream-for-each proc s)
(if (stream-null? s)
'done
(begin (proc (stream-car s))
(stream-for-each proc (stream-cdr s)))))
;;; can use stream-for-each to write a procedure for viewing
;;; streams
;;;
;;; NOTE: do not try this on infinite streams
(define (display-stream s)
(stream-for-each display-line s))
(define (display-line x)
(newline)
(display x))
;;; defining some finite streams
(define a (cons-stream 1 (cons-stream 2 the-empty-stream)))
(define b (cons-stream 3 (cons-stream 4 (cons-stream 5 the-empty-stream))))
;;; a procedure to help us define a finite stream with integers
;;; between a given interval
(define (stream-enumerate-interval low high)
(if (> low high)
the-empty-stream
(cons-stream low (stream-enumerate-interval (+ low 1) high))))
(define stream-1-to-1000 (stream-enumerate-interval 1 1000))
;;; definitions for cons-stream, stream-car and stream-cdr use
;;; delay and force
;;; memoization: a way to prevent recalculating values every time
;;; we access a particular element of the stream
(define (memo-proc proc)
(let ((already-run? false)
(result false))
(lambda ()
(if (not already-run?)
(begin (set! result (proc))
(set! already-run? true)
result)
result))))
;;; and now we redefine delay in terms of memo-proc
;;; Infinite streams
;;; a convenient procedure for printing the first n elements of a stream
(define (print-stream s n)
(cond ((stream-null? s) the-empty-stream)
((= n 0) 'done)
(else (display-line (stream-car s))
(print-stream (stream-cdr s) (- n 1)))))
;;; defining add-streams
(define (add-streams s1 s2)
(cons-stream (+ (stream-car s1) (stream-car s2))
(add-streams (stream-cdr s1)
(stream-cdr s2))))
;;; defining scale-stream
(define (scale-stream s factor)
(cons-stream (* (stream-car s) factor)
(scale-stream (stream-cdr s) factor)))
;;; defining a few infinite streams
(define zeros (cons-stream 0 zeros))
(define ones (cons-stream 1 ones))
(define twos (cons-stream 2 twos))
(define odds (cons-stream 1 (add-streams odds twos)))
;;; defining integers, a stream of positive integers, two
;;; different ways
(define integers
(cons-stream 1 (add-streams integers ones)))
(define integers
(add-streams (cons-stream 0 integers)
ones))
;;; defining stream of fibonnaci numbers
(define fib
(cons-stream 1 (cons-stream 1 (add-streams fib
(stream-cdr fib)))))
;;; partial-sums takes a stream as an argument and returns the
;;; stream whose elements are s0, s0+s1, s0+s1+s2, s0+s1+s2+s3, ...
;;; for example, (partial-sum integers) would be 1, 3, 6, 10, 15, ...
(define (partial-sums s)
(cons-stream (stream-car s)
(add-streams (partial-sums s)
(stream-cdr s))))
;;; merge combines two ordered streams into one ordered result
;;; stream, eliminating repetitions
(define (merge s1 s2)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else (let ((s1car (stream-car s1))
(s2car (stream-car s2)))
(cond ((< s1car s2car)
(cons-stream s1car
(merge (stream-cdr s1) s2)))
((> s1car s2car)
(cons-stream s2car
(merge s1 (stream-cdr s2))))
(else
(cons-stream s1car
(merge (stream-cdr s1)
(stream-cdr s2)))))))))
;;; A famous problem, first raised by R. Hamming, is to enumerate,
;;; in ascending order with no repetitions, all positive integers
;;; with no prime factors other than 2, 3, or 5. One obvious way
;;; to do this is to simply test each integer in turn to see whether
;;; it has any factors other than 2, 3, and 5. But this is very
;;; inefficient, since, as the integers get larger, fewer and fewer
;;; of them fit the requirement. As an alternative, let us call
;;; the required stream of numbers H and notice the follwoing facts
;;; about it.
;;; h begins with 1
;;; The elements of (scale-stream h 2) are also elements of s.
;;; The same is true for (scale-stream h 3) and (scale-stream h 5)
;;; These are all the elements of h.
(define h
(cons-stream 1
(merge (scale-stream h 2)
(merge (scale-stream h 3)
(scale-stream h 5)))))