Higher-order procedures

Goals

This laboratory exercise provides experience defining and using higher-order procedures.

Steps for this Laboratory Exercise

1. Consider the following procedures:

   (define substitute
     (lambda (template old new)
   
       ;; precondition test
       (if (not (list? template))
           (error 'substitute "The template must be a list"))
   
       (let kernel ((rest template)
                    (result '()))
         (if (null? rest)
             (reverse result)          ;; Reverse the final list, because the
                                       ;;   recursion builds it back to front.
             (let ((first (car rest)))
               (kernel (cdr rest)
                       (cons (if (equal? old first) new first) result)))))))
   (define sub
     (lambda (old new)
       (lambda (template)
         (substitute template old new))))
   

   Using sub, define and test a month-replacer procedure that substitutes the symbol November for each top-level occurrence of the symbol month in a given list.

2. Write a curried version of the expt procedure. Curried-expt should take one argument, a number x, and return a procedure that "remembers" x and raises it to any specified power:

   (define power-of-two
     (curried-expt 2))
   
   > (power-of-two 7)
   128
   
   > ((curried-expt 10) 3)
   1000
   
   > ((curried-expt -2) 5)
   -32
   
   > ((curried-expt 9/10) 4)
   6561/10000
   
   > (map (curried-expt 9) '(2 3 1/2 -3))
   (81 729 3.0 1/729)
   

3. The reading about the insertion sort showed how a procedure could be defined that returns a list of numbers in ascending order. In that lab, an ordering predicate (e.g., <= or >=) is used to compare specific data, but all of the rest of the code is independent of the type of data and the nature of the ordering required.

   Apply the idea of currying to produce a higher-order procedure general-sort that takes an ordering predicate (e.g., <= or >=) as parameter and that returns a sorting procedure based on that predicate. Thus, an alternative definition of sort-numbers-ascending might be:

   
        (define sort-numbers-ascending (general-sort <=))
   

   while a procedure for sorting list elements in descending order might be:

   
        (define sort-numbers-descending (general-sort >=))
   

4. The call (compose car reverse) returns a procedure. Describe the effect of applying this procedure to a list.

5. Suppose that we have two procedures f and g of arity 1 that always return numbers as values. We can perform "function addition" on them -- that is, we can use them to generate a new procedure that takes one argument and returns the sum of the results of applying f and g to that argument. Define a procedure function-add that implements the operation of function addition.

   > ((function-add double /) 5)
   51/5
   
   > ((function-add (lambda (n) (* n n))
                    (lambda (n) (- 128 n))) 100)
   10028
   
   > ((function-add string-length
                    (lambda (str)
                       (char->integer (string-ref str 0)))) "America")
   72     ;; 7 characters in "America", #\A is ASCII character 65
   
   (define sin-plus-cos
     (function-add sin cos))
   
   > (sin-plus-cos 0)
   1
   
   (define pi 3.1415926535897932)
   
   > (sin-plus-cos (/ pi 4))
   1.414213562373095
   
   (define sum
     (lambda (ls)
        (apply + ls)))
   
   > ((function-add length sum) '(3 2 4 9))
   22
   

6. Why do we need to define a separate procedure function-add, instead of simply applying the built-in addition procedure, +? In the last example above, for instance, would there be anything wrong with simply writing ((+ length sum) '(3 2 4 9))? If so, what?

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-higher-order-proc.shtml

Henry M. Walker (walker@cs.grinnell.edu)

created April 2, 1997 by John David Stone last revised February 3, 2005 by Henry M. Walker
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.