;; The objective is to develop a Scheme procedure that takes a tree of real
;; numbers as argument and returns a list containing all the numbers in the
;; tree, in ascending numerical order.
;; The precondition for the application of this procedure is that its
;; argument be a tree of real numbers. The following predicate,
;; TREE-OF-REALS?, performs the test necessary to determine whether a given
;; Scheme value meets this condition. To qualify, the value must be either
;; the null list or else a pair in which the car is either a real number or
;; a tree of real numbers and the cdr is a tree of real numbers.
(define tree-of-reals?
(lambda (obj)
(or (null? obj)
(and (pair? obj)
(let ((first-element (car obj)))
(or (real? first-element)
(tree-of-reals? first-element)))
(tree-of-reals? (cdr obj))))))
;; The basic technique that we'll use for building up a list of reals in
;; ascending numerical order is _merging_. A merging operation combines
;; two such ascending lists into one larger ascending list. At the lowest
;; level of the tree, we'll form the shortest lists (containing one
;; element, or none at all) without having to worry about ordering; all
;; lists of two or more elements will be formed by merging, at successively
;; higher levels.
;; To merge two ascending lists, determine first whether one or the other
;; of them is empty. If so, the other can be returned unchanged as the
;; result of the merging operation. Otherwise, compare the first element
;; of one list with the first element of the other. Whichever is less
;; should become the first element of the result. To obtain the rest of
;; the elements of the result, call the MERGE procedure recursively!
;; This won't work unless both arguments are in fact in ascending order to
;; begin with. I've presented the necessary precondition tests here, but
;; I've commented them out because I can prove that they are superfluous
;; whenever MERGE is invoked by the CONTENTS procedure. The ASCENDING?
;; predicate is left as a further exercise for the reader.
(define merge
(lambda (left right)
;; precondition tests
;; These are provably superfluous when MERGE is invoked by CONTENTS.
; (if (or (not (list? left))
; (not (list? right)))
; (error 'merge "Both arguments must be lists"))
; (if (or (not (ascending? left))
; (not (ascending? right)))
; (error 'merge "Both argument lists must be in ascending order"))
(let kernel ((lt left)
(rt right))
(cond ((null? lt) rt)
((null? rt) lt)
((<= (car lt) (car rt))
(cons (car lt) (kernel (cdr lt) rt)))
(else
(cons (car rt) (kernel lt (cdr rt))))))))
;; The CONTENTS procedure performs the deep recursion on the given tree
;; structure. If the tree is empty, it returns a null list; otherwise,
;; its kernel procedure calls itself recursively to get a list, in
;; ascending order, of the elements in the cdr, and merges that with
;; an ascending-order list of the elements in the car, which is obtained
;; either by applying LIST to the car (if the car is itself a real number)
;; or by issuing another recursive call to the kernel procedure (if the
;; car is itself a tree of reals).
(define contents
(lambda (tree)
;; precondition test
(if (not (tree-of-reals? tree))
(error 'contents
(string-append "The argument must be a tree structure "
"containing only real numbers")))
(let kernel ((subtree tree))
(if (null? subtree)
'()
(let ((first-element (car subtree))
(rest-of-elements (kernel (cdr subtree))))
(merge (if (real? first-element)
(list first-element)
(kernel first-element))
rest-of-elements))))))
;; The HARMONIC procedure takes two arguments, N and K, both of which are
;; supposed to be positive integers, and computes and returns the sum of
;; the reciprocals of the Kth powers of the positive integers from 1 to N.
(define harmonic
(lambda (n k)
;; precondition tests
(if (not (and (integer? n)
(positive? n)
(integer? k)
(positive? k)))
(error 'harmonic "Both arguments must be positive integers"))
(let loop ((counter 1) ; runs through the integers from 1 to n
(total 0)) ; the sum of all the reciprocal powers seen so far
(if (< n counter)
total
(loop (+ counter 1) (+ total (/ (expt counter k))))))))
;; In the last line, recall that if the / procedure is given only one
;; argument, it returns the reciprocal of that argument.
;; The PRIME? procedure determines whether a given natural number is prime.
(define prime?
(lambda (n)
;; precondition test
(if (or (not (integer? n))
(negative? n))
(error 'prime? "The argument must be a non-negative integer"))
(and (>= n 2)
(or (= 2 n)
(odd? n))
(let loop ((trial-divisor 3))
(or (< n (* trial-divisor trial-divisor))
(and (not (zero? (remainder n trial-divisor)))
(loop (+ trial-divisor 2))))))))
;; In English: To qualify as prime, a natural number must meet three
;; conditions. (A) It must be greater than or equal to 2. (B) It must
;; either be equal to 2 or odd -- 2 is the only even prime. (This
;; condition makes it unnecessary to perform any division tests in which
;; the divisor is even; an odd value of N cannot have any even divisors.)
;; (C) When you try dividing N by successive odd numbers, beginning with 3,
;; you get only non-zero remainders until you reach a trial divisor whose
;; square is greater than the number being tested.
;; It is okay to stop searching for a divisor of N as soon as the square of
;; the trial divisor exceeds N, because none of the subsequent odd numbers
;; less than N can possibly be a divisor of N. (Suppose that there were an
;; odd divisor K of N such that N < K * K. Then N/K would also be an odd
;; integer, would also divide N evenly, and would have occurred as a trial
;; divisor earlier in the search.)
This document is available on the World Wide Web as
http://www.math.grin.edu/courses/Scheme/spring-1997/solutions-2.html