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]
"""
accumulated = start
def closure(item):
nonlocal accumulated
accumulated = f(accumulated, item)
return accumulated
return list(map(closure, lst))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)
((equal? (car lst) 'waldo) 0)
(else
(let ((found-him (wheres-waldo (cdr lst))))
(if (equal? 'nowhere found-him)
found-him
(+ 1 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))
(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 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:
yield [self.datum]
if self.left:
for lp in self.left.paths():
yield [self.datum] + lp
if self.right:
for rp in self.right.paths():
yield [self.datum] + rpWe 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 x in range(num_of_players):
linked_list, card = linked_list.rest, linked_list
# Put the card in the player's hand
cards.rest = hands[x]
hands[x] = card
return hands, linked_listDefine 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)
(if (stream-null? stream)
stream
(cons-stream (stream-car stream)
(stream-map (lambda (x) (+ (stream-car stream) x))
(partial-sums (stream-cdr 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 ...)))
(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
(cons-stream 0
(interleave nats (stream-map - nats))))
;; 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)
(cons-stream (list (stream-car s) (stream-car t))
(interleave
(stream-map (lambda (x) (list (stream-car s) x)) (stream-cdr t))
(pairs (stream-cdr 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)