# CS 61A

Time: Tue 10/31/17 3 pm

## 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?

## Highly Exclusive (fa15-final)

Complete the definition of `no-fib`, the stream of all positive integers that are not Fibonacci numbers. These are all positive integers excluding 1, 2, 3, 5, 8, 13, ... The stream starts with 4, 6, 7, 9, 10, 11, 12, 14.

``````(define (p prev curr n)
(if

)
)

(define no-fib (p 3 5 4))``````