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[0]

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?