# Laboratory: More Higher-Order Procedures

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? lst)
0
(+ (car lst) (sum (cdr lst))))))
```

c. Implement the leftmost 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)
(let kernel ((lst lst) (result 0))
(if (null? lst)
result
(kernel (cdr lst) (+ result (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 natural numbers:

```(define republican-voter-ids (list 1471 4270))
```

Define a Scheme procedure `remove-republicans` 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 `republican-voter-ids`.

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

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 ```

```  ```

``` ```
``` [Skip to Body] Primary: [Front Door] [Current] [Glance] - [EC] [Honesty] [Instructions] [Links] [Search] [Syllabus] Groupings: [EBoards] [Examples] [Exams] [Handouts] [Homework] [Labs] [Lab Writeups] [Outlines] [Readings] [Reference] ECA: [About] [Grades] [Quizzes] [Submit Work] [Change Password] [Reset Password] Misc: [Experiments in Java] [Scheme Reference] [Scheme Report] [CS153 2002S (Walker)] [CS151 2003S (Rebelsky)] [CS152 2000F (Rebelsky)] [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 Tue May 6 09:19:54 2003. The source to the document was last modified on Mon Feb 17 20:34:17 2003. This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2003S/Labs/more-higher-order.html. You may wish to validate this document's HTML ; ; Check with Bobby Samuel A. Rebelsky, rebelsky@grinnell.edu ```