Week 11 Discussion/Lab Notes

Administrivia

• This week is the last week to sign up for Project 3 face-to-face grading.
• Quiz 3 next Wednesday. It will cover mutation, concurrency, and streams.
• Don't go to lab next week. Stay home and do the reading instead. Turn in Lab 12 by Friday night.
• Supplemental discussion section next Friday (4-14), 5-6:30 PM in 320 Soda.

Discussion Outline

• hw11
• #2 fract-stream
• remainder and quotient are useful
• use show-stream (or ss) to display streams
• syntax: (ss stream n)
• n specifies how many elements to show (optional)
• cons, car, cdr, cons-stream, stream-car, stream-cdr, delay, force
• which are special forms? why?
• remember cons-stream uses a backwards naming style than the rest
• respect the data abstraction barriers!
• streams can be implemented independently of delay/force and pairs
• delay/force can be implemented independently of lambda
• implicit stream definitions
• example
• (define ones (cons-stream 1 ones))
• why doesn't (define ones (cons 1 ones)) work? what happens?
• what about (define (ones) (cons 1 (ones)))?
• interleaving
• how to combine two infinite streams?
• memoization
• recomputing stream elements is inefficient, so we memoize elements
• only return values are stored!
• countability (for those of you who have Math 55 or CS70 experience)
• ordered pairs, rational numbers, ...
• anything representable by a single stream is "countable" and vice-versa
• AI and game trees
• examples/exercises
• complete this alternative construction of a stream of positive integers:
• (define naturals (cons-stream 1 (stream-map <??> naturals)) )
• construct a stream of all the integers (positive, negative, 0)
• describe what the following does and explain how it works:
     (define (divides? divisor n)
        (= (remainder n divisor) 0) )
     (stream-filter (lambda (x) (divides? 2 x))
                    (stream-filter (lambda (x) (not (divides? 3 x)))
                                   naturals))
• power series
• cos(x) = 1 - x²/2! + x⁴/4! - x⁶/6! + ...
• write a procedure approx-cos. It should take an argument x and should generate a stream that contains successively closer approximations to cos(x)
• hint: use the partial-sums function from exercise 3.55

(I suggest also reading Benson Limketkai's stream notes.)

Countability

(You don't need to know this for the course.)

Those of you who have taken or are taking Math 55 or CS70 should already be familiar with the concept of countability. We say that a set is countable if either of the following is true:

• the set has a finite number of elements
• the set has a one-to-one correspondence with the natural numbers {1, 2, 3, 4, ...}

The first case is fairly trivial and isn't very interesting, so let's look at the second case, which deals with infinite sets.

The second case means that if we can find a mapping such that every element in S has some natural number mapped to it, then S is countable. (Technically this satisfies the surjective half for one-to-one correspondence. But actually, the injective half of the requirement isn't important for countability.)

stream-ref provides a mapping from the natural numbers to the elements of a stream. To obtain the n^th element of a stream, we merely need to call (stream-ref stream (- n 1)). This covers all of the elements of the stream, and thus, every (flat) stream is countable!

Conversely, every countable set can be represented as a stream. If the mapping from the natural numbers to this set is given by the function f, then we merely need to construct a stream such that the n^th element is f(n).

What are some examples of countable sets that have an infinite number of elements? The set of all integers (positive, negative, and 0) is a countable set. We can map a natural number n to the integer (-1)ⁿ ceiling(ⁿ/₂). As a stream, this would look like: 0, -1, 1, -2, 2, -3, 3, ....

The set of all rational numbers is also countable. (Dr. Math has the explanation. Note that although the proof only addresses positive rationals, we can show that the set of all rationals is countable by using the same technique as we used for the integers.) Note the similarity between rational numbers and ordered pairs.

What are some examples of uncountable sets? The set of real numbers is not countable. The power set (the set of all subsets) of the natural numbers is also not countable.