*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

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.

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 ***"
```

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

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'
```

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
'RESULT'
return 'RESULT'
```

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

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

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