Fundamentals of Computer Science I (CS151 2003F)

More Higher-Order Procedures

Summary: In the previous reading, you encountered some basic issues for higher order procedures. Today, we continue some additional uses of such procedures.


Operator Sections

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.

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 'n/a (not available) in a given list as (make-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 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 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:
;;;   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))))))))

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 procedure.

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]

Monday, 10 March 2003 [Samuel A. Rebelsky]


Disclaimer: 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 Tue Dec 9 14:00:18 2003.
The source to the document was last modified on Mon Sep 1 13:26:32 2003.
This document may be found at

Valid HTML 4.0 ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky,