# CS 61A

Time: Wed 11/8/17 2 pm

## Pair Up (sp17-final-8)

Fill in the Scheme pairs function so that (pairs L), where L is a list, produces a list of lists, where each of these lists contains a pair of elements from L. The function must be tail-recursive. You need not define (or use) the reverse function.

``````scm> (pairs ’(1 2 3 4))
((1 2) (3 4))
scm> (pairs ’(1 2 3 4 5)) ; Odd element at end put in singleton list.
((1 2) (3 4) (5))
scm> (pairs ’())
()``````
``````(define (reverse P)
"""Returns the reverse of list P. This function is tail-recursive""" ;;; Implementation not shown
)

(define (pairs L)
(define (accum-pairs lst result)
(cond
( result)
( (cons ))
(else (accum-pairs
)
)
)
)
()
)``````

## 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))``````

## I Scheme for Ice Cream (fa16-final-6)

The built-in append procedure is equivalent in behavior to the following definition.

``(define (append s t) (if (null? s) t (cons (car s) (append (cdr s) t))))``
1. Is the recursive call to append in the definition above is a tail call?

2. Implement atoms, which takes a Scheme expression. It returns a list of the non-nil atoms contained in the expression in the order that they appear. A non-nil atom is a number, symbol, or boolean value.

``````scm> (atoms 1)
(1)
scm> (atoms '(+ 2 3))
(+ 2 3)
scm> (atoms '(+ (* 2 3) 4))
(+ * 2 3 4)
scm> (atoms '(* (+ 1 (* 2 3) (+ 4 5)))
(* + 1 * 2 3 + 4 5)``````
``````(define (atoms exp)
(cond
((null? exp) )
((atom? exp) )
(else (append  ))
)
)``````
3. If Scheme had only numbers and two-argument procedures, parentheses would be unnecessary. To demonstrate, implement `tally`, which takes the list of atoms in a Scheme expression. It returns a list whose first element is the value of the original expression. Assume that the original expression consists only of numbers and call expressions with arithmetic operators (such as `+` and `*`) and exactly two operands.

Hint: `tally` is similar to the built-in `eval` procedure: `(eval '(+ (* 2 3) 4))` evaluates to 10.

``````scm> (car (tally ’(1)))                 ; atoms in 1
1
scm> (car (tally ’(+ 2 3)))             ; atoms in (+ 2 3)
5
scm> (car (tally ’(+ * 2 3 4)))         ; atoms in (+ (* 2 3) 4)
10
scm> (car (tally ’(* + 1 * 2 3 + 4 5))) ; atoms in (* (+ 1 (* 2 3)) (+ 4 5))
63``````
``````(define (tally s)
(if (number? (car s))

(let ((first ))
(let ((second ))
(cons ( ( (car s) (car first) (car second)))

)
)
)
)
)``````