61A Homework 13

Due by 11:59pm on Monday, 8/11

Readings: You might find the following references useful:

Submission: See the online submission instructions. We have provided the following starter files: hw13.py, hw13.scm

Table of Contents


For homework this week, we'll be redoing the coding problems on Midterm 2 and a couple of stream questions. This time, you'll have an interpreter to check your answers. In the starter file, replace all capitalized strings (such as "CONDITION" or "RESULT") with the code you need to fill in.

Question 1

We all know the higher order functions map, filter, and reduce. Today we're going to talk about their not-quite-so famous fourth sibling, scan. Scan is like reduce, only instead of accumulating the result into a single value, scan returns a list that contains all the intermediate values in reducing the list.

def scan(f, lst, start):
    """Returns a list containing the intermediate values of reducing the list.

    >>> from operator import add, mul
    >>> scan(add, [1, 2, 3, 4], 0)
    [1, 3, 6, 10]
    >>> scan(mul, [3, 2, 1, 0], 10)
    [30, 60, 60, 0]
    "*** YOUR CODE HERE ***"

Question 2

Write wheres-waldo, a Scheme procedure which takes in a Scheme list and outputs the index of waldo if the symbol waldo exists in the list. Otherwise, it outputs the symbol nowhere.

(define (wheres-waldo lst)
  (cond ((null? lst) 'nowhere)
	 (let ((found-him 'RESULT))
	   (if (equal? 'nowhere found-him)

(define (test-waldo)
  (assert-equal 1 "wheres-waldo" (wheres-waldo '(moe larry waldo curly)) 2)
  (assert-equal 2 "wheres-waldo" (wheres-waldo '(1 2)) 'nowhere))


Question 3

Here's an implementation of a Binary Search Tree:

We want to add a paths method to the BST class. It will return a generator yields all of the paths from the root of the tree to a leaf. Each path is represented as a list containing the individual datums.

    def paths(self):
        """Return a generator for all of the paths from the root to a leaf.

        >>> tree = BST(5, BST(3, BST(2), BST(4)), BST(10, None, BST(13, BST(12))))
        >>> gen = tree.paths()
        >>> next(gen)
        [5, 3, 2]
        >>> for path in gen:
        ...     print(path)
        [5, 3, 4]
        [5, 10, 13, 12]
        if not self.right and not self.left:
        if 'CONDITION':
            for VARIABLE in 'ITERABLE':
        if 'CONDITION':
            for VARIABLE in 'ITERABLE':

Question 4

We want to play a card game and we must evenly deal out all of the cards to each player. We have a linked list (Link) of cards. In this case, cards are represented as numbers. We want to write a function deal_deck that returns a Python list of linked lists of cards for each player (reverse order of how the cards were dealt - older cards on the bottom) and a linked list of the extra cards (in the original order). Do not call the Link constructor.

def deal_deck(linked_list, num_of_players):
    """Deals out a deck of cards.

    >>> deck = Link(1, Link(2, Link(3, Link(4, Link(5, Link(6, \
      Link(7, Link(8, Link(9, Link(10))))))))))
    >>> list_of_cards, remainder = deal_deck(deck, 4)
    >>> list_of_cards
    [Link(5, Link(1)), Link(6, Link(2)), Link(7, Link(3)), Link(8, Link(4))]
    >>> remainder
    Link(9, Link(10))
    # Create a list containing each player's hand.
    hands = [Link.empty for i in range(num_of_players)]
    # Give each player the right number of cards.
    for i in range(len(linked_list)//num_of_players):
        # For each player
        for VARIABLE in 'ITERABLE':
            linked_list, card = linked_list.rest, linked_list
            # Put the card in the player's hand
    return 'RESULT'


Question 5

Define a function partial_sums, which takes in a stream with elements

a1, a2, a3, ...

and outputs the stream

a1, a1 + a2, a1 + a2 + a3, ...

If the input is a finite stream of length n, the output should be a finite stream of length n. If the input is an infinite stream, the output should also be an infinite stream.

(define (partial-sums stream)

;; Doctests for partial-sums
(define finite
  (cons-stream 2
    (cons-stream 0
      (cons-stream 1
        (cons-stream 4 ())))))

(define ones (cons-stream 1 ones))
(define twos (cons-stream 2 twos))
(define nats (cons-stream 1 (stream-map 1+ nats)))

(define (test-partial-sums)
  (assert-equal 1 "partial-sums"
		(ss (partial-sums twos))
		'(2 4 6 8 10 12 14 16 18 20 ...))
  (assert-equal 2 "partial-sums" 
		(ss (partial-sums (interleave ones twos)))
		'(1 3 4 6 7 9 10 12 13 15 ...))
  (assert-equal 3 "partial-sums"
		(ss (partial-sums finite))
		'(2 2 3 7))
  (assert-equal 4 "partial-sums"
		(ss (partial-sums nats))
		'(1 3 6 10 15 21 28 36 45 55 ...)))


Question 6

An infinite set is said to be countably infinite if we can create an infinite stream such that any element in the set can be reached within a finite number of steps through the stream. For example, since we can create a stream of natural numbers, we know that the natural numbers are countable:

Now, we will show that the integers are also countable. Define a stream of all integers (including the negative ones). You may use the nats stream in your solution.

Hint: You should consider alternating positive and negative numbers - for example, your stream may look like (0 1 -1 2 -2 3 -3 ...).

(define nats
  (cons-stream 1
    (stream-map (lambda (x) (+ x 1)) nats)))

(define integers

;; Note:  This will infinite loop if you call it on an infinite stream
;; that does not have the element.
(define (has-element? elem stream max-size)
  (and (not (stream-null? stream))
       (> max-size 0)
       (or (equal? elem (stream-car stream))
	   (has-element? elem (stream-cdr stream) (- max-size 1)))))

(define (test-integers)
  (assert-equal 1 "integers" (has-element? 0 integers 1000) #t)
  (assert-equal 2 "integers" (has-element? 12 integers 1000) #t)
  (assert-equal 3 "integers" (has-element? -23 integers 1000) #t))


Question 7: Challenge Problem (optional)

Now, show that the (positive) rational numbers are countable. Recall that a rational number is just a pair of integers a/b, so we just need to make an infinite stream of all pairs of integers.

(define (pairs s t)

(define rationals
  (pairs nats nats))

(define (test-rationals)
  (assert-equal 1 "rationals" (has-element? 1 rationals 1000) #f)
  (assert-equal 2 "rationals" (has-element? '(1 1) rationals 1000) #t)
  (assert-equal 3 "rationals" (has-element? '(1 2) rationals 1000) #t)
  (assert-equal 4 "rationals" (has-element? '(3 4) rationals 1000) #t)
  (assert-equal 5 "rationals" (has-element? '(4 3) rationals 1000) #t)
  (assert-equal 6 "rationals" (has-element? '(5 2) rationals 1000) #t))

;; Uncomment the following line to test rationals:
; (test-rationals)