-
Draw a boxes and arrows diagram to show the result of executing the following
definitions.
(define y '(2 3))
(define z (cons 3 y))
(define w (cons z y))
(define x (cons w '(2 3)))
-
Given the following definitions :
(define x '(1 2 3))
(define y (append x x))
(define z (cons x x))
(define foo '(7 2 3))
show the value of each of the following expressions. If something
is wrong, say so. (Obviously you could trivialize the problem by
typing these expressions into a Scheme interpreter and transcribing the
results. Feel free to use a computer to check your answers, but be
sure you can answer the questions without using a machine.)
(car x) => 1
(cdar x) => (cdr (car x)) => invalid since cdr cannot be applied on 1.
(cdar z) => (cdr (car z)) => (cdr x) => '(2 3)
(cons x foo) => '((1 2 3) 7 2 3)
(equal? (cdr x) (cdr foo)) => #t
(equal? (cdr y) x) => #f ((cdr y) is '(2 3 1 2 3))
(equal? (cdr z) (car z)) => #t ( since (car z) = x = (cdr z) )
(eqv? (cdr z) (car z)) => #t ( they both refer the SAME x)
(eqv? (cdr x) (cdr foo)) => #f ( not pointer equal )
(car '(cadar x)) => cadar
-
Define a function list-max that that returns the largest of the
elements in its list argument. For example:
; use the let so that I dont have to call (list-max (cdr x)) twice
(define (list-max lst) (if (null? (cdr lst)) (car lst)
(let ((y (list-max (cdr lst))))
(if (> y (car lst)) y (car lst)))))
-
Write a function divisors which, given an integer, returns a list
of all its proper divisors ( the proper divisors of a number are all divisors
except the number itself; 1 is included). You may find the Scheme function
modulo
to be useful. There should be no duplicate divisors.
Examples:
(define (divisors n)
; define a helper which given a first and n, returns all divisors of n > first.
(let (((divisor-help first n)
(if (= first n) () ; base case
(if (= (modulo n first) 0) (cons first (divisor-help (+ first 1) n))
(divisor-help (+ first 1) n)))))
(divisor-help 1 n)))
-
Now write a function is-perfect? that yields true if its argument
is a perfect number, and yields false otherwise. A number is perfect if
it is the sum of its proper divisors. The smallest perfect number is 6
(= 1+2+3). Another is 28 (= 1 + 2+ 4+ 7+ 14). (Hint: you may find the answers
to the previous two questions to be useful in your solution).
; we can use divisors and sum-list(that we saw in class) to implement is-perfect?
(define (is-perfect? n) (= n (sum-list (divisors n))))
-
Define a function fringe that takes as an argument a tree (an
arbitrary list) and returns a list containing the leaves of the tree in
left-to-right order. For example:
(define (fringe lst)
(if (null? lst) lst ; base case
(if (null? (car lst)) (fringe (cdr lst)) ; removes () nested inside lists
; recursvely go inside the car if car is a list in itself ..
(if (pair? (car lst)) (append (fringe (car lst)) (fringe (cdr lst)))
(cons (car lst) (fringe (cdr lst)))))))
-
Define a function rev that reverses the top-level elements of
the list that is its argument (i.e., give your own implementation
of the standard Scheme function reverse). For example:
(define ( rev lst)
(if (null? lst) lst ; base case
(append (rev (cdr lst)) (list (car lst)))))
-
Define a function deep-rev that reverses the elements of the list
that is its argument. If elements of the list are themselves lists,
they should be reversed recursively. Example:
; basically the same idea as fringe. If car is a list, recursively reverse the car
; otherwise just add (car lst) to the end of deep-rev of the cdr
(define (deep-rev lst)
(if (null? lst) lst ; base case
(if (pair? (car lst)) (append (deep-rev (cdr lst)) (list (deep-rev (car lst))))
(append (deep-rev (cdr lst)) (list (car lst))))))