5.4. Recursion, Iteration, and Mapping
5.4. Recursion, Iteration, and Mapping
| (let name ((var val) ...) exp1 exp2 ...) | syntax |
| returns: value of the last expression | |
This form of let, called named let, is a general-purpose iteration and recursion construct. It is similar to the more common form of let (see Section 4.3) in the binding of the variables var … to the values val … within the body exp1 exp2 …. In addition, the variable name is bound within the body to a procedure that may be called to recur or iterate; the arguments to the procedure become the new values of the variables var ….
A named let expression of the form
(let name ((var val) ...) exp1 exp2 ...)
can be rewritten with letrec as follows.
((letrec ((name (lambda (var ...) exp1 exp2 ...))) name) val ...)
A syntax definition of let that implements this transformation and handles unnamed let as well can be found on page 201.
The procedure divisors defined below uses named let to compute the nontrivial divisors of a nonnegative integer.
(define divisors (lambda (n) (let f ((i 2)) (cond ((>= i n) '()) ((integer? (/ n i)) (cons i (f (+ i 1)))) (else (f (+ i 1))))))) (divisors 5) ⇒ () (divisors 32) ⇒ (2 4 8 16)
The version above is non-tail-recursive when a divisor is found and tail-recursive when a divisor is not found. The version below is fully tail-recursive. It builds up the list in reverse order, but this is easy to remedy, either by reversing the list on exit or by starting at n − 1 and counting down to 1.
(define divisors (lambda (n) (let f ((i 2) (ls '())) (cond ((>= i n) ls) ((integer? (/ n i)) (f (+ i 1) (cons i ls))) (else (f (+ i 1) ls))))))
| (do ((var val update) ...) (test res ...) exp ...) | syntax |
| returns: the value of the last res | |
do allows a common restricted form of iteration to be expressed succinctly. The variables var … are bound initially to the values of val … and are rebound on each subsequent iteration to the values of update …. The expressions test, update …, exp …, and res … are all within the scope of the bindings established for var ….
On each step, the test expression test is evaluated. If the value of test is true, iteration ceases, the result expressions res … are evaluated in sequence, and the value of the last expression is returned. If no result expressions are present, the value of the do expression is unspecified.
If the value of test is false, the expressions exp … are evaluated in sequence, the expressions update … are evaluated, new bindings for var … to the values of update … are created, and iteration continues.
The expressions exp … are evaluated only for effect and are often omitted entirely. Any update expression may be omitted, in which case the effect is the same as if the update were simply the corresponding var.
Although looping constructs in most languages require that the loop iterands be updated via assignment, do requires the loop iterands val … to be updated via rebinding. In fact, no side effects are involved in the evaluation of a do expression unless they are performed explicitly by its subexpressions.
See page 202 for a syntax definition of do.
The definitions of factorial and fibonacci below are straightforward translations of the tail-recursive named-let versions given in Section 3.2.
(define factorial (lambda (n) (do ((i n (- i 1)) (a 1 (* a i))) ((zero? i) a)))) (factorial 10) ⇒ 3628800 (define fibonacci (lambda (n) (if (= n 0) 0 (do ((i n (- i 1)) (a1 1 (+ a1 a2)) (a2 0 a1)) ((= i 1) a1))))) (fibonacci 6) ⇒ 8
The definition of divisors below is similar to the tail-recursive definition of divisors given with the description of named let above.
(define divisors (lambda (n) (do ((i 2 (+ i 1)) (ls '() (if (integer? (/ n i)) (cons i ls) ls))) ((>= i n) ls))))
The definition of scale-vector! below, which scales each element of a vector v by a constant k, demonstrates a nonempty do body.
(define scale-vector! (lambda (v k) (let ((n (vector-length v))) (do ((i 0 (+ i 1))) ((= i n)) (vector-set! v i (* (vector-ref v i) k)))))) (define vec (vector 1 2 3 4 5)) (scale-vector! vec 2) vec ⇒ #(2 4 6 8 10)
| (map procedure list1 list2 ...) | procedure |
| returns: list of results | |
map applies procedure to corresponding elements of the lists list1 list2 … and returns a list of the resulting values. The lists list1 list2 … must be of the same length, and procedure must accept as many arguments as there are lists.
(map abs '(1 -2 3 -4 5 -6)) ⇒ (1 2 3 4 5 6) (map (lambda (x y) (* x y)) '(1 2 3 4) '(8 7 6 5)) ⇒ (8 14 18 20)
While the order in which the applications themselves occur is not specified, the order of the values in the output list is the same as that of the corresponding values in the input lists.
map might be defined as follows.
(define map (lambda (f ls . more) (if (null? more) (let map1 ((ls ls)) (if (null? ls) '() (cons (f (car ls)) (map1 (cdr ls))))) (let map-more ((ls ls) (more more)) (if (null? ls) '() (cons (apply f (car ls) (map car more)) (map-more (cdr ls) (map cdr more))))))))
No error checking is done by this version of map; f is assumed to be a procedure and the other arguments are assumed to be proper lists of the same length. An interesting feature of this definition is that map uses itself to pull out the cars and cdrs of the list of input lists; this works because of the special treatment of the single-list case.
| (for-each procedure list1 list2 ...) | procedure |
| returns: unspecified | |
for-each is similar to map except that for-each does not create and return a list of the resulting values, and for-each guarantees to perform the applications in sequence over the lists from left to right. for-each may be defined as follows.
(define for-each (lambda (f ls . more) (do ((ls ls (cdr ls)) (more more (map cdr more))) ((null? ls)) (apply f (car ls) (map car more))))) (let ((same-count 0)) (for-each (lambda (x y) (if (= x y) (set! same-count (+ same-count 1)))) '(1 2 3 4 5 6) '(2 3 3 4 7 6)) same-count) ⇒ 3 
EAN: 2147483647
Pages: 98