1. Define a Scheme procedure attach-at-end that takes any
value as its first argument and a list as its second argument and returns a
list containing all of the the same elements as the given list except that
the given value has been added as the last element.
(define attach-at-end
(lambda (val li)
(if (null? li)
(list val)
(cons (car li) (attach-at-end val (cdr li))))))
2. Define a Scheme procedure concatenate that takes any two
lists as arguments and returns a single list containing all of the elements
of the first list, in order, followed by all of the elements of the second
list, in order. (Scheme already has a built-in procedure called
append that does this. Don't use it.)
(define concatenate
(lambda (list-1 list-2)
(if (null? list-1)
list-2
(cons (car list-1) (concatenate (cdr list-1) list-2)))))
3. Define a Scheme procedure position that takes any value as
its first argument and a list as its second argument and returns the number
of elements of the given list that precede the first occurrence of the
given value, or #f if the given value does not occur at all on
the given list.
(define position
(lambda (val li)
(cond ((null? li) #f)
((equal? val (car li)) 0)
(else (add-1-if-number (position val (cdr li)))))))
(define add-1-if-number
(lambda (val)
(if (number? val)
(+ val 1)
val)))
4. Define a Scheme procedure mean that takes a non-empty list
of numbers and returns the arithmetic mean of its elements.
(define mean
(lambda (li)
(/ (sum li) (length li))))
(define sum
(lambda (li)
(if (null? li)
0
(+ (car li) (sum (cdr li))))))
5. Adapt the mean procedure so that it calls the
error procedure if it is given an empty list.
(define mean
(lambda (li)
(if (null? li)
(error "The procedure mean is not defined for the empty list.")
(/ (sum li) (length li)))))
6. Adapt the mean procedure so that it takes any list
as an argument and returns the arithmetic mean of just the elements that
are numbers, ignoring the rest. It should call error if the
list contains no numbers.
(define mean
(lambda (li)
(mean-of-ntuple (extract-numbers li))))
(define mean-of-ntuple
(lambda (li)
(if (null? li)
(error "The procedure mean is not defined for lists that contain no numbers.")
(/ (sum li) (length li)))))
(define extract-numbers
(lambda (li)
(cond ((null? li) '())
((number? (car li)) (cons (car li) (extract-numbers (cdr li))))
(else (extract-numbers (cdr li))))))
7. Define a Scheme procedure iota that takes a natural number
and produces a list, in ascending order, of all the smaller natural
numbers. For instance, the value of (iota 5) should be
(0 1 2 3 4); the value of (iota 1) should be
(0); and the value of (iota 0) should be the empty
list.
(define iota
(lambda (n)
(if (zero? n)
'()
(attach-at-end (- n 1) (iota (- n 1))))))
or
(define iota
(lambda (n)
(iota-helper n 0)))
(define iota-helper
(lambda (rest so-far)
(if (zero? rest)
'()
(cons so-far (iota-helper (- rest 1) (+ so-far 1))))))
8. Using the procedures presented in chapter 3 of the textbook for rational
arithmetic (make-ratl, numr, and
denr), define a Scheme procedure rpower that takes
a rational number as its first argument and an integer (which may be
positive, zero, or negative) as its second argument and returns a rational
number representing the result of raising the given rational number to the
power of the given integer.
(define rpower
(lambda (x n)
(cond ((positive? n) (make-ratl (expt (numr x) n)
(expt (denr x) n)))
((zero? n) (make-ratl 1 1))
((zero? (num x))
(error "rpower: cannot raise zero to negative power"))
(else (make-ratl (expt (denr x) (- n))
(expt (numr x) (- n)))))))
9. Similarly, using those procedures, define a Scheme procedure
rfloor that takes any rational number as its first argument
and returns the greatest integer not greater than that rational number.
(I'd prefer an exact integer, so use floor only as a last
resort -- there is a way to do it without floor.)
(define rfloor
(lambda (x)
(cond ((rpositive? x) (quotient (numr x) (denr x)))
((rzero? x) 0)
((zero? (remainder (numr x) (denr x)))
(quotient (numr x) (denr x)))
(else (sub1 (quotient (numr x) (denr x)))))))
10. As described in exercise 3.17 in the textbook (page 93), write versions
of the make-ratl, numr, and denr
procedures that will ensure that the internal representation of each
rational number is unique by forcing the denominator to be positive and
reducing the fraction to lowest terms.
(define make-ratl
(lambda (n d)
(cond ((zero? d)
(error "make-ratl: The denominator cannot be zero."))
((negative? d)
(reduce (- n) (- d) (gcd (abs n) (- d))))
(else
(reduce n d (gcd (abs n) d))))))
(define reduce
(lambda (n d divisor)
(list (quotient n divisor) (quotient d divisor))))
(define numr car)
(define denr cadr)