Because procedures are values in Scheme, it is straightforward to abstract
the common structure of various similar-looking procedures and to write and
use higher-order procedures like map that supply that
structure automatically, without requiring the programmer to type it all in
again each time.
For instance, in the ``Variations on recursion'' lab, we considered two very similar filtering procedures -- one to remove the negative numbers from a given list, the other to remove numbers lying outside the range from 0 to 100:
(define filter-out-negatives
(lambda (ls)
(cond ((null? ls) '())
((negative? (car ls))
(filter-out-negatives (cdr ls)))
(else
(cons (car ls) (filter-out-negatives (cdr ls)))))))
(define filter-outliers
(lambda (ls)
(cond ((null? ls) '())
((or (< (car ls) 0)
(< 100 (car ls)))
(filter-outliers (cdr ls)))
(else
(cons (car ls) (filter-outliers (cdr ls)))))))
We can abstract the general filtering mechanism from the particular criterion used to exclude some elements and include others by making the latter into a parameter of a filter generator:
(define filter-generator
(lambda (test?)
(lambda (full-list)
(let kernel ((ls full-list))
(cond ((null? ls) '())
((test? (car ls))
(kernel (cdr ls)))
(else
(cons (car ls) (kernel (cdr ls)))))))))
Given any predicate test?, filter-generator
constructs and returns a customized filter procedure that in its turn takes
a list as argument and returns the filtered version of that list:
(define filter-out-negatives
(filter-generator negative?))
> (filter-out-negatives '(7 13 -8 16 0 -2 4))
(7 13 16 0 4)
(define filter-outliers
(filter-generator (lambda (n)
(or (< n 0) (< 100 n)))))
> (filter-outliers '(-50 0 50 100 150))
(0 50 100)
Another common pattern is using one parameter of a procedure to count the number of times some operation is to be performed, decrementing the counter on each recursive call until it reaches 0. Here are some examples of this pattern:
(define factorial
(lambda (steps)
(let loop ((result 1)
(steps-remaining steps))
(if (zero? steps-remaining)
result
(loop (* steps-remaining result)
(- steps-remaining 1))))))
(define iota
(lambda (steps)
(let loop ((result '())
(steps-remaining steps))
(if (zero? steps-remaining)
result
(loop (cons (- steps-remaining 1) result)
(- steps-remaining 1))))))
(define harmonic-sum
(lambda (steps)
(let loop ((result 0)
(steps-remaining steps))
(if (zero? steps-remaining)
result
(loop (+ (/ steps-remaining) result)
(- steps-remaining 1))))))
The only components of these definitions that don't match are the initial
value of result and the operation used to combine the number
of steps remaining with the result obtained so far. We could abstract the
common elements to obtain a generator for procedures that have this
pattern:
(define countdown-procedure-generator
(lambda (initial-result combiner)
(lambda (steps)
(let loop ((result initial-result)
(steps-remaining steps))
(if (zero? steps-remaining)
result
(loop (combiner steps-remaining result)
(- steps-remaining 1)))))))
(define factorial
(countdown-procedure-generator 1 *))
(define iota
(countdown-procedure-generator '() (lambda (steps result)
(cons (- steps 1) result))))
(define harmonic-sum
(countdown-procedure-generator 0 (lambda (steps result)
(+ (/ steps) result))))
Using countdown-procedure-generator, define a procedure named
sum-of-squares that takes one argument, a natural number, and
returns the sum of the squares of all natural numbers up to and including
that argument:
> (sum-of-squares 2) ; 12 + 22 5 > (sum-of-squares 7) ; 12 + ... + 72 140
Here are three procedures that have a common structure:
(define longest-on-list
(lambda (ls)
; precondition test
(if (or (null? ls)
(not (list? ls)))
(error 'longest-on-list
"The argument must be a non-empty list"))
; body
(let kernel ((so-far (car ls))
(rest (cdr ls)))
(if (null? rest)
so-far
(kernel (longer-string so-far (car rest))
(cdr rest))))))
> (longest-on-list '("red" "white" "and" "blue"))
"white"
(define concatenate-with-spaces
(lambda (ls)
; precondition test
(if (or (null? ls)
(not (list? ls)))
(error 'concatenate-with-spaces
"The argument must be a non-empty list"))
; body
(let kernel ((so-far (car ls))
(rest (cdr ls)))
(if (null? rest)
so-far
(kernel (string-append so-far " " (car rest))
(cdr rest))))))
> (concatenate-with-spaces '("alpha" "beta" "gamma" "delta"))
"alpha beta gamma delta"
(define list->number
(lambda (ls)
; precondition test
(if (or (null? ls)
(not (list? ls)))
(error 'list->number
"The argument must be a non-empty list"))
; body
(let kernel ((so-far (car ls))
(rest (cdr ls)))
(if (null? rest)
so-far
(kernel (+ (* so-far 10) (car rest))
(cdr rest))))))
> (list->number '(9 3 0 5))
9305
Abstract the common structure and write a generator that contains that common structure and enables you to define any of these three procedures simply by invoking the generator with appropriate arguments.
Use the generator from the previous exercise to define a procedure that takes one argument, a non-empty list of characters, and returns whichever element of that list comes first in the local collating sequence.
This document is available on the World Wide Web as
http://www.math.grin.edu/courses/Scheme/fall-1998/procedures-continued.html
created October 30, 1997
last revised June 21, 1998