Summary: In the previous reading, you encountered some basic issues for higher order procedures. Today, we continue some more sophisticated uses of such procedures.
An operator section is a procedure that is derived from another
filling in some but not all of its arguments. For
double procedure defined by
(define double (lambda (n) (* 2 n)))
qualifies as an operator section, since it fills in the first argument to
* procedure with the particular value 2. Operator
sections are often used as arguments to higher-order procedures.
For instance, once we've written the
make-tallier procedure that
generates a procedure that can tally values in a list that meet a precidate,
we could construct a procedure that counts the number of
occurrences of the symbol
not available) in a given
(make-tallier (lambda (whatever) (eq? 'n/a whatever))).
Here the value of the
lambda-expression is an operator section
eq?, with the first argument filled in with the particular
We can even define higher-order procedures to construct operator sections
for us. Such procedures are not primitives, but they are easily defined --
Let's use the name
left-section for a higher-order procedure
that takes a procedure of two arguments and a value to drop in as its first
argument, and returns the relevant operator section:
;;; Procedure: ;;; left-section ;;; Parameters: ;;; proc, A procedure with two parameters ;;; param1, The first parameter to that procedure ;;; Purpose: ;;; Fills in one parameter to proc. ;;; Produces: ;;; newproc, a new procedure with one parameter, param2 ;;; Preconditions: ;;; proc is a procedure with two parameters. ;;; param1 is of appropriate type for the first parameter of proc. ;;; Postconditions: ;;; newproc expects a parameter of the same type as the second ;;; parameter of proc. ;;; (newproc param) is the same as (proc param1 param2). (define left-section (lambda (proc param1) (lambda (expected) (proc param1 expected))))
So we could define
(left-section * 2)
(lambda (whatever) (eq? 'n/a whatever)) as
(left-section eq? 'n/a).
To filter a list is to examine each of its elements in turn, retaining some for a new list while eliminating others. For instance, given a list of integers, the following procedure filters it to remove the negative ones:
;;; Procedure: ;;; remove-negatives ;;; Parameters: ;;; lst, a list of numbers ;;; Purpose: ;;; Removes negative numbers from the list. ;;; Produces: ;;; no-negatives, a list containing no negative numbers. ;;; Preconditions: ;;; lst contains only numbers [Unverified] ;;; Postconditions: ;;; no-negatives list contains all non-negative numbers in lst ;;; (and in the same order). ;;; no-negatives contains no other numbers. (define remove-negatives (lambda (ls) (cond ((null? ls) null) ((negative? (car ls)) (remove-negatives (cdr ls))) (else (cons (car ls) (remove-negatives (cdr ls)))))))
We could write similar procedures to remove the whitespace characters from
a list of characters, or to exclude any occurrences of the symbol
'n/a from a list:
(define remove-whitespace (lambda (ls) (cond ((null? ls) null) ((char-whitespace? (car ls)) (remove-whitespace (cdr ls))) (else (cons (car ls) (remove-whitespace (cdr ls))))))) (define remove-n/a-symbols (lambda (ls) (cond ((null? ls) null) ((eq? 'n/a (car ls)) (remove-n/a-symbols (cdr ls))) (else (cons (car ls) (remove-n/a-symbols (cdr ls)))))))
Similar filtering procedures occur so frequently that it's useful to have a higher-order procedure to construct them.
;;; Procedure: ;;; make-remover ;;; Parameters: ;;; pred?, a unary predicate ;;; Purpose: ;;; Build a procedure that removes values from a list. ;;; Produces: ;;; remover, a procedure ;;; Preconditions: ;;; [None] ;;; Postconditions: ;;; remover takes a list as a parameter. ;;; Each element of that list must be a valid parameter of pred? ;;; (remover lst) consists of only the elements of lst for which ;;; pred? does not hold. (define make-remover (lambda (pred?) (letrec ((remover (lambda (ls) (cond ((null? ls) null) ((pred? (car ls)) (remover (cdr ls))) (else (cons (car ls) (remover (cdr ls)))))))) remover)))
In other words,
let remover be a recusive procedurer that steps through
the list, keeping the values that don't match the predicate; return that
We can now define the variations in terms of our new procedure
(define remove-negatives (make-remover negative?)) (define remove-whitespace (make-remover char-whitespace?)) (define remove-n/a-symbols (make-remover (left-section eq? 'n/a)))
October 30, 1997 [John Stone or Henry Walker]
March 17, 2000 [John Stone]
Thursday, 2 November 2000 [Sam Rebelsky]
Wednesday, 14 March 2001 [Samuel A. Rebelsky]
Sunday, 16 February 2003 [Samuel A. Rebelsky]
Tuesday, 17 February 2004 [Samuel A. Rebelsky]
I usually create these pages
on the fly, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Fri May 7 09:44:31 2004.
The source to the document was last modified on Tue Feb 17 13:38:31 2004.
This document may be found at
; ; Check with BobbySamuel A. Rebelsky, firstname.lastname@example.org