[Current] [News] [Glance] [Discussions] [Instructions] [Search] [Links] [Handouts] [Outlines] [Readings] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [Fall2000.01] [Spring2000]
In this reading and laboratory, you will continue your investigation into procedures that take procedures as parameters or return procedures as results. We call such procedures higher-order procedures.
We've already seen that Scheme includes some built-in higher order procedures.
The map
procedure takes as arguments a procedure and one
or more lists and builds a new list whose contents are the result of
applying the procedure to the corresponding elements of each list.
(That is, the ith element of the result list is the result of applying
the procedure to the ith element of each source list.)
The call-with-values
procedure takes as arguments two
procedures. The first has a result that contains multiple values and
the second expects that many values as arguments.
But Scheme has many other built-in higher-order procedures. You can read about many of them in section 6.4 of the Scheme report, which is available through the DrScheme Help Desk.
One of the most important built-in higher-order procedures is
apply
. which takes a procedure and a list as arguments
and invokes the procedure, giving it the elements of the list as its
arguments:
> (apply string=? (list "foo" "foo")) #t > (apply * (list 3 4 5 6)) 360 > (apply append (list (list 'a 'b 'c) (list 'd) (list 'e 'f) null (list 'g 'h 'i))) (a b c d e f g h i)
An operator section is a procedure that is derived from another
procedure by ``filling in'' some but not all of its arguments. For
instance, the double
procedure defined by
(define double (lambda (n) (* 2 n)))
qualifies as an operator section, since it fills in the first argument to
the *
procedure with the particular value 2. Operator
sections are often used as arguments to higher-order procedures such as
list-of
, tallier
, and generate-list
from the first lab on procedures
as values.
For instance, once we've written the 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 'n/a
(``not available'') in a given
list as (tallier (lambda (whatever) (eq? 'n/a whatever)))
.
Here the value of the lambda
-expression is an operator section
of eq?
, with the first argument filled in with the particular
value 'n/a
.
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 arity 2 ;;; param1, The first parameter to that procedure ;;; Purpose: ;;; Fills in one parameter to the procedure. ;;; Produces: ;;; A new procedure of arity 1 that applys proc to param1 and ;;; its parameter. ;;; Preconditions: ;;; proc is a procedure of arity 2 ;;; param1 is of appropriate type for the first parameter of proc ;;; Postconditions: ;;; The result procedure expects a parameter of the same type as ;;; the second parameter of proc. (define left-section (lambda (proc param1) (lambda (expected) (proc param1 expected))))
So we could define double
as (left-section * 2)
and (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: ;;; A list of numbers ;;; Purpose: ;;; Removes negative numbers from the list. ;;; Produces: ;;; A list containing no negative numbers. ;;; Preconditions: ;;; The input list contains only numbers [Unverified] ;;; Postconditions: ;;; The output list contains all non-negative numbers in the original ;;; list (and in the same order). ;;; The output list 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. Using the method described in the first lab on procedures as values, we can easily define such a procedure:
(define remove (lambda (predicate) (letrec ((recurrer (lambda (ls) (cond ((null? ls) null) ((predicate (car ls)) (recurrer (cdr ls))) (else (cons (car ls) (recurrer (cdr ls)))))))) recurrer))) (define remove-negatives (remove negative?)) (define remove-whitespace (remove char-whitespace?)) (define remove-n/a-symbols (remove (left-section eq? 'n/a)))
October 30, 1997 (John Stone or Henry Walker)
March 17, 2000 (John Stone)
Thursday, 2 November 2000 (Sam Rebelsky)
http://www.math.grin.edu/~stone/courses/scheme/procedures-as-values-continued.xhtml
[Current] [News] [Glance] [Discussions] [Instructions] [Search] [Links] [Handouts] [Outlines] [Readings] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [Fall2000.01] [Spring2000]
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Readings/hop.html
Source text last modified Thu Nov 2 14:12:44 2000.
This page generated on Thu Nov 2 14:16:50 2000 by Siteweaver. Validate this page's HTML.
Contact our webmaster at rebelsky@grinnell.edu