Packaging implicitly-defined streams
;;; write a function that returns an i-d stream
> (define (enumerate-ints)
(define ints
(cons-stream 0 (add-streams ones ints)))
ints)
> (enumerate-ints)
(0 . #
Could we use a let here? (define (enumerate-ints)
(let ((ints (cons-stream 0
ints))
(add-streams ones ints))))
Packaging implicitly-defined streams
;;; write a function that returns an i-d stream
> (define (enumerate-ints)
(define ints
(cons-stream 0 (add-streams ones ints)))
ints)
> (enumerate-ints)
(0 . #
Could we use a let here? NO! (define (enumerate-ints)
(let ((ints (cons-stream 0
ints))
(add-streams ones ints))))
Prime numbers and the Sieve of Eratosthenes
An integer x is prime if x > 1, and it has no factors (positive integers that divide it without a remainder) other than 1 and x.
(define (prime? x)
(define (is-factor? k x)
(= (modulo x k) 0))
(define (has-factor-le? j)
(cond ((< j 2) #f)
((is-factor? j x) #t)
(else
(has-factor-le? (- j 1)))))
(not (has-factor-le? (- x 1)))
Can this be improved?
If an integer has a factor > 1, it generally has 2: if y is a factor of x, then x/y is also a factor of x.
Either y = x/y = sqrt(x), y < sqrt(x) < x/y, or x/y < sqrt(x) < y ¡ú If x has a factor > 1, it has a factor ¡Ü sqrt(x)
(define (prime? x)
(define (is-factor? k x)
(= (modulo x k) 0))
(define (has-factor-le? j)
(cond ((< j 2) #f)
((is-factor? j x) #t)
(else
(has-factor-le? (- j 1)))))
(not (has-factor-le? (round (sqrt x)))))
Using prime?, define stream of primes
(define stream-of-primes
(stream-filter
prime?
(enumerate-integers-from 2)))
How much work do we do to check each number?
The Sieve of Eratosthenes
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23... 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23... 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23... 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23... 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23...
The Sieve of Eratosthenes
sieve code
(define (sieve k numbers)
(stream-filter
(lambda(x)(not (= (modulo x k) 0)))
numbers)
>(str-to-list (sieve 2 (enumerate-integers-from 3)) 20)
(3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41)
primes code
(define (prime-stream)
(define (primes-from str)
(cons-stream (stream-car str)
(primes-from
(sieve (stream-car str)
(stream-cdr str)))))
(primes-from (enumerate-integers-from 2)))
(define primes (prime-stream))
primes-from
car cdr
cons- stream
primes- from
sieve (filter not divisible by)
primes-from as a diagram
ints >1
primes
Successive approximation
Remember approximating square root using improve function? (define (sqrt-improve guess x)
(/ (+ guess (/ x guess)) 2.0))
We could construct a stream with successive values
(define (sqrt-approx-stream x)
(define (sqrt-improve guess)
(/ (+ guess (/ x guess)) 2.0))
(define (sqrt-approx-from v)
(cons-stream v (sqrt-approx-from (sqrt-improve v))))
(sqrt-approx-from 1))
Successive approximation
> (str-to-list (sqrt-approx-stream 2) 10)
(1
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095)
Successive approximation
> (str-to-list (sqrt-approx-stream 255) 10)
(1
128.0
64.99609375
34.459703224540235
20.929825438777183
16.556697878942657
15.979159870022801
15.96872283345579
15.968719422671676
15.968719422671313)
Streams of pairs
Suppose we want to construct a stream from two streams of integers, such that the resultant stream contains all pairs (i j), where i is from the first stream, j is from the second. The desired result is that each pair is reachable using successive stream-cdrs.
Suppose we had this problem for lists?
append the lists made up of the first element of list 1 with all elements of list2, then those made up of the second element of list 1 with all elements of list2, then the third, and so forth.
>(pairs ‘(1 2 3) ‘(1 2 3))
((1 1)(1 2)(1 3)(2 1)(2 2)(2 3)(3 1)(3 2)(3 3))
Does this work for lists?
list code:
(define (list-pairs a b)
(define (pairs-aux item)
(map (lambda(x)(list item x)) b))
(cond ((null? a) ‘())
(else
(append
(pairs-aux (car a))
(list-pairs (cdr a) b)))))
Does this work for streams?
stream code:
(define (stream-pairs a b)
(define (pairs-aux item)
(stream-map (lambda(x)(list item x)) b))
(cond ((null? a) ‘())
(else
(stream-append
(pairs-aux (stream-car a))
(stream-pairs (stream-cdr a)
b)))))
Suppose the streams are infinite, like the integers
Does this work for streams?
stream code:
(define (stream-pairs a b)
(define (pairs-aux item)
(stream-map (lambda(x)(list item x)) b))
(cond ((null? a)'())
(else
(let ((mapped (pairs-aux (stream-car a)))
(cons-stream (stream-car mapped)
(append-streams
(“fixed” by delaying stream-pairs)
(stream-cdr mapped)
(stream-pairs (stream-cdr a)
b)))))))
Does this work for streams?
>(define sp (stream-pairs ints ints)))
> sp
((0 0) . #
> (str-to-list sp 8)
((0 0)(0 1)(0 2)(0 3)(0 4)(0 5)(0 6)(0 7))
What position is (1 1) in this stream?
interleave the streams
(define (interleave s1 s2)
(if (stream-null? s1)
s2
(cons-stream
(stream-car s1)
(interleave s2 (stream-cdr s1)))))
Builds stream using elements from each stream in turn
interleave the streams
>(define x (interleave ints fibs))
Builds stream using elements from each stream in turn
> (str-to-list x 12)
(0 0 1 1 2 1 3 2 4 3 5 5)
(0 0 1 1 2 1 3 2 4 3 5 5)
Now we can pair the streams
(define (stream-pairs s t)
(cons-stream
(list (stream-car s) (stream-car t))
(interleave
(stream-pairs (stream-cdr s)
t)
(stream-map (lambda(x)(list(stream-car s) x))
(stream-cdr t)))))
Now we can pair the streams
>(define x (pairs ints ints))
>(str-to-list x 15)
((0 0)(1 0)(0 1)(2 0)(0 2)(1 1)(0 3)(3 0)
(0 4)(1 2)(0 5)(2 1)(0 6)(1 3)(0 7))
A pattern emerges based on the interleaving, so I could calculate the position of any pair (with some difficulty).
If we add a constraint, only get some of the pairs…
(define (nstream-pairs s t)
(cons-stream
(list (stream-car s) (stream-car t))
(interleave
(stream-map (lambda(x)(list(stream-car s) x))
(stream-cdr t))
(nstream-pairs (stream-cdr s)
(stream-cdr t)))))
If we add a constraint, only get some of the pairs…
>(define x (npairs ints ints))
>(str-to-list x 15)
((0 0) (0 1) (1 1) (0 2) (1 2) (0 3) (2 2)(0 4)
(1 3) (0 5) (2 3) (0 6) (1 4) (0 7) (3 3))
What is different about this stream of pairs?
(This is a feature you want in the homework)
In this week’s assignment you will use a different technique, weighted merging instead of interleaving, to ensure that you can combine results from infinite streams.