# Laboratory: Higher-Order Procedures (2)

Summary: We continue to explore higher-order procedures.

Contents:

## Exercises

### 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
v1
v2
...
vn-1
vn))
```

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
(proc
...
(proc
(proc
(proc v0
v1)
v2)
v3)
...
vn-1)
vn)
```

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)
result
(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)
result
(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

### 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)
(cond
((null? lst) null)
((pred? (car lst)) (remove pred? (cdr lst)))
(else (cons (car lst) (remove pred? (cdr lst)))))))
```
• `(complement pred?)` builds a predicate that does the opposite of `pred?`. It should be defined in the reading.
• `(member val lst)` determines if `val` is a member of `list` (and returns the portion of lst that starts with `val)`. It is a standard Scheme procedure.
• `(right-section binproc val)` converts a binary procedure to a unary procedure by filling in the second argument. You should have defined `right-section` for this lab.

## History

Thursday, 2 November 2000 [Samuel A. Rebelsky]

Wednesday, 14 February 2001 [Samuel A. Rebelsky]

• Moved a few problems into a new lab so that there are now two higher-order procedures labs. This lab is intented to be the second of the two labs.
• Added a new introductory problem.

Tuesday, 3 April 2001 [Samuel A. Rebelsky]

• Updated 6b to deal with a different order of presentation.

Wednesday, 4 April 2001 [Samuel A. Rebelsky]

Friday, 18 October 2002 [Samuel A. Rebelsky]

• Added example code for problem 1 (`insert`).
• Added part d of problem 1 (`insert`). The ```string-append example is due to Philip Morse-Fortier. ```
• ``` Rewrote problem 6 (intersect) for clarity. ```
• ``` Added notes on problem 6 (<intersect). ```
• ``` This version available at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Labs/more-higher-order.html ```
``` Monday, 17 February 2003 [Samuel A. Rebelsky] This version available at http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2003S/Labs/more-higher-order.html 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] Corrected stupid typos. (Thanks Saul!) This version available at http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2004S/Labs/more-higher-order.html ```

```  ```

``` ```
``` [Skip to Body] Primary: [Front Door] [Current] [Glance] - [Honesty] [Instructions] [Links] [Search] Groupings: [EBoards] [Examples] [Exams] [Handouts] [Homework] [Labs] [Outlines] [Readings] [Reference] Misc: [Experiments in Java] [Java API] [Scheme Reference] [Scheme Report] [CS153 2003S] [CS151 2003F] [CS152 2000F] [SamR] 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 http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2004S/Labs/higher-order-2.html. You may wish to validate this document's HTML ; ; Check with Bobby Samuel A. Rebelsky, rebelsky@grinnell.edu ```