Earlier in the semester, we defined the
Tree class, which contains a
label and multiple branches leading to its
children. Here’s the class for reference:
class Tree: def __init__(self, label, children=()): self.label = label for branch in children: assert isinstance(branch, Tree) self.children = list(children) def is_leaf(self): return not self.children
We wish to make these trees iterable, and display each label of the tree in preorder traversal. That is, we iterate over the label of a tree before the labels of any of its children. We also iterate over each child in the order presented in the
- What are the new method(s) you need to add in order to make these trees iterable?
- Write out the code for these new method(s).
One solution is to use a generator in our
class Tree: def __iter__(self): yield self.label for child in self.children: for label in child: yield label
What are the first four values of the stream
(define (sweet dreams) (cons-stream (list dreams) (sweet (list dreams)))) (define (mix tape) (cons-stream (car (car tape)) (mix (append (match cdr-stream (cdr tape)) (list (cdr-stream (car tape))))))) (define (match dot com) (if (null? com) nil (cons (dot (car com)) (match dot (cdr com))))) (define s (mix (match sweet '(1 2 3))))
The key here is to think about the purpose of
sweet: This returns a stream of lists, with each next element enclosed in one more set of parentheses.
match: This is basically the
map procedure in disguise. We’re taking the procedure
dot and applying it to every element in the list
mix: Takes a list of streams
tape as input. It pulls the first element from the first stream, then moves the first stream to the end of the list. Finally, it moves every stream in the list forward
Deciphering the final line, we first look at the innermost expression:
(match sweet '(1 2 3))
Here, we’re just mapping the procedure
sweet over the list
(1 2 3). This gives us back a list of three infinite streams - here’s the first one:
: (1) : ((1)) : (((1))) : ((((1)))) ...
The other two streams look the same, but with the numbers
(((1) . #[delayed]) ((2) . #[delayed]) ((3) . #[delayed]))
So far so good! Now that we know what
mix does, we can apply it to this list of streams to get the first four elements of our new stream
: (1) : ((2)) : (((3))) : ((((1)))) ...