Time: Wed 11/8/17 2 pm
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
)
)
)
)
()
)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)))What expression will (directions 4 'a) evaluate to?
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))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))))Is the recursive call to append in the definition above is a tail call?
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 ))
)
)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)))
)
)
)
)
)