# CS 61A

Time: Wed 10/25/17 2 pm

## Tree Stuff

Consider the following implementation:

``````def tree(label, branches=[]):
return [label] + branches

def label(tree):
return tree

def branches(tree):
return tree[1:]``````

There are multiple ways to get started on playing with such tree structure! As a few examples:

• Track 1
1. Given a tree, how can we find a largest/smallest label in the leaves?
2. Given a tree, how can we find a largest/smallest label in the tree?
3. Given a tree, how can we find the sum of all labels (assuming all labels are numbers)?
• Track 2
1. Given a tree, how can we clone it?
2. Given a tree, how can we make a copy of it with all the leaves pruned?
• Track 3
1. Given a tree and a label, how can we check if the label we want is in the tree?
2. Given a tree, how can we check if there aren't any descendent nodes of a same label for any node in the tree?

## Exceptions in Python

``````try:
pass # Some bunch of stuff
except Exception as e:
pass # Do something regarding the exception``````

## Scheme Syntax

### Building Block

``````1 ; 1

True ; True``````

### Define Variables

``````(define a 1) ; a

a ; 1

(define (foo x)
(+ x 2)
) ; foo
; Is equivalent to the following
(define foo
(lambda (x)
(+ x 2)
)
) ; foo

(foo 2) ; 4``````

### Primitive Expressions

``````(+ 1 2)

(display 2)
(print 1)

(cons 1 2)
(list 1 2)``````

Use the `=` predicate when you wish to test whether two numbers are equivalent.
Use the `eqv?` predicate when you wish to test whether two non-numeric values are equivalent.

### Special Forms

``````(if True 1 2) ; 1

(if True
(/ 1 1)
(/ 1 0)
) ; 1

(cond
(False (/ 1 0))
(True 1)
(else 100)
) ; 1

(lambda (x)
(/ 1 0)
) ; (lambda (x) (/ 1 0))

(and 0 False 1) ; False
(or 5 False (/ 1 0)) ; 5``````

`(and ...)` returns the first false value, otherwise the last one.
`(or ...)` returns the first true value, otherwise the last one.

The boolean `False` is the only false value.

### Quotes

``````'a ; a
(quote a) ; a

'(1 2) ; (1 2)
(quote (1 2)) ; (1 2)

'(1 . 2) ; (1 . 2)
'(1 . ()) ; (1)
'(1 . (2 . (3))) ; (1 2 3)``````

## Lazy Sunday (fa14-final-4)

1. Implement the Scheme procedure directions, which takes a number `n` and a symbol `sym` that is bound to a nested list of numbers. It returns a Scheme expression that evaluates to `n` by repeatedly applying `car` and `cdr` to the nested list. Assume that `n` appears exactly once in the nested list bound to `sym`.

Hint: The implementation searches for the number `n` in the nested list `s` that is bound to `sym`. The returned expression is built during the search. See the tests at the bottom of the page for usage examples.

``````(define (directions n sym)

(define (search s exp)
; Search an expression s for n and return an expression based on exp
(cond
((number? s) )
((null? s) nil)
(else (search-list s exp))
)
)

(define (search-list s exp)
; Search a nested list s for n and return an expression based on exp
(let
(
(first )
(rest )
)
(if (null? first) rest first)
)
)

(search (eval sym) sym)

)

(define a '(1 (2 3) ((4))))
(directions 1 'a)
; expect (car a)
(directions 2 'a)
; expect (car (car (cdr a)))
(define b '((3 4) 5))
(directions 4 'b)
; expect (car (cdr (car b)))``````
2. What expression will `(directions 4 'a)` evaluate to?