# 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

## Introduction

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]
"""

### 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)
('TEST-AND-RESULT)
(else
(let ((found-him 'RESULT))
(if (equal? 'nowhere found-him)
'RESULT
'RESULT
)))))

(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))

(test-waldo)``````

### 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 `datum`s.

``````    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:
'RESULT'
if 'CONDITION':
for VARIABLE in 'ITERABLE':
'RESULT'
if 'CONDITION':
for VARIABLE in 'ITERABLE':
'RESULT'``````

### 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.

>>> list_of_cards, remainder = deal_deck(deck, 4)
>>> list_of_cards
>>> remainder
"""
# 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 each player
for VARIABLE in 'ITERABLE':
# Put the card in the player's hand
'RESULT'
return 'RESULT'``````

## Streams

### 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)
'YOUR-CODE-HERE)

;; 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 ...)))

(test-partial-sums)``````

### 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
'YOUR-CODE-HERE)

;; 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))

(test-integers)``````

### 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)
'YOUR-CODE-HERE)

(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)``````