Computer Science Fundamentals (CS153 2004S)

Laboratory: Higher-Order Procedures (2)

Summary: We continue to explore higher-order procedures.



Exercise 1: Insert

insert is a procedure which takes two parameters, a binary procedure and a list, and gives the result of applying the procedure to neighboring values. There are two ways to think about insert based on the way we interpret

(insert proc (list v0 

i. We could interpret the call to insert as

(proc v0 
      (proc v1
            (proc v2
                   (proc vn-1
                         vn) ...)))

ii. We could interpret the call to insert as

      (proc v0

That is, we can apply the operation in a rightmost manner (i) or in a leftmost manner (ii). For addition, the difference is between grouping like this

(v0 + (v1 + (v2 + ... + (vn-1 + vn) ...)))

or like this

(( ... ((v0 + v1) + v2) + ... + vn-1) + vn)

a. Does it make a difference which way we do things? (Hint, consider subtraction as a binary operation.)

b. Implement the rightmost version of insert. You may want to base it on this version of sum. Note that you'll probably need to choose a new base case.

(define sum
  (lambda (lst)
    (if (null? (cdr lst))
        (car lst) 
        (+ (car lst) (sum (cdr lst))))))

c. Implement the leftmost version of insert. You may want to base it on this version of sum.

(define sum
  (lambda (lst)
    (let kernel ((remaining (cdr lst)) (result (car lst)))
      (if (null? remaining)
          (kernel (cdr remaining ) (+ result (car remaining)))))))

If you have difficulty with the named let construct, you may want to base it on the following, equivalent definition.

(define sum
  (lambda (lst)
    (letrec ((kernel 
              (lambda (remaining result)
                 (if (null? remaining)
                     (kernel (cdr remaining) (+ result (car remaining)))))))
      (kernel (cdr lst) (car lst)))))

d. Test the two versions of insert using +, -, and * as the binary operators. You may also want to test it using string-append, as in (leftmost-insert string-append '("a" "b" "c" "d" "e")), which will help you catch interesting rearrangement errors.

Exercise 2: Making Lists

a. Define and test a generate-list procedure that takes two arguments: (1) a one-argument procedure, proc, that can be applied to a natural number and (2) n, a natural number. Your procedure should generate a list of length n whose ith element is the result of applying proc to i. For example,

> (generate-list (lambda (x) (* x x)) 6)
(0 1 4 9 16 25)

b. Define and test a generate-lister procedure that takes one argument -- a one-argument procedure, proc, that can be applied to a natural number -- and generates a new procedure that takes one parameter, a natural number, n, and returns a list of length n whose ith element is the result of applying proc to i.

Exercise 3: Right section

In the reading, you saw how we might define left-section, which fills in the left of the two arguments of a binary procedure. Document, define, and test the analogous higher-order procedure right-section, which takes a procedure of two arguments and a value to drop in as its second argument, and returns the operator section that expects the first argument. (For instance, (right-section expt 3) is a procedure that computes the cube of any number it is given.)

Exercise 4: Powers of Two

Using the generate-lister procedure from you defined in a previous lab and an appropriate operator section, define a procedure powers-of-two that constructs and returns a list of powers of two, in ascending order, given the length of the desired list:

> (powers-of-two 7)
(1 2 4 8 16 32 64)

Exercise 5: Removing Elements

Here is an interesting list of symbols:

(define bad-adjectives (list 'grody 'sweet 'awesome))

Define a Scheme procedure remove-bad-adjectives that takes a list of non-empty lists as its argument and filters out of it the lists in which the first element is also an element of bad-adjectives. For example,

> (remove-bad-adjectives (list (list 'awesome 'cool 'pizza)
                               (list 'wicked 'cool 'music)
                               (list 'supremely 'awesome 'food)
                               (list 'grody 'gunk)))
((wicked cool music) (supremely awesome food))

Exercise 6: Intersection

The intersection of two lists is a list that contains all of the elements that appear in both lists. Using remove, complement, member, and right-section, define (intersect lst1 lst2), a procedure that interesects two lists.

Note that by remove, I mean make-remover from the second reading on higher-order procedures.

You should not use direct recursion in defining intersect.

Exercise 7: Filtering

The filters constructed by remove are designed to exclude list elements that satisfy a given predicate. Define a higher-order procedure make-filter that returns a filtering procedure that retains the elements that satisfy a given predicate (excluding those that fail to satisfy it). For instance, applying the filter (make-filter even?) to a list of integers should return a list consisting of just the even elements of the given list.


Notes on Exercise 6: Intersection

In case you've forgotten, here's a little bit of info on the procedures you should use. (remove pred? lst) builds a list that has all the elements that match pred? removed. Here's one definition

(define remove
  (lambda (pred? lst)
      ((null? lst) null)
      ((pred? (car lst)) (remove pred? (cdr lst)))
      (else (cons (car lst) (remove pred? (cdr lst)))))))



Thursday, 2 November 2000 [Samuel A. Rebelsky]

Wednesday, 14 February 2001 [Samuel A. Rebelsky]

Tuesday, 3 April 2001 [Samuel A. Rebelsky]

Wednesday, 4 April 2001 [Samuel A. Rebelsky]

Friday, 18 October 2002 [Samuel A. Rebelsky]

Monday, 17 February 2003 [Samuel A. Rebelsky]

Tuesday, 17 February 2004 [Samuel A. Rebelsky]

  • Rewrote problem 5 from remove-republicans to remove-bad-adjectives.
  • Updated title.
  • Changed sample code for rightmost sum to make it easier to use as a template.

Thursday, 19 February 2004 [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 Fri May 7 09:44:16 2004.
The source to the document was last modified on Thu Feb 19 10:23:10 2004.
This document may be found at

You may wish to validate this document's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky,