Fundamentals of CS I (CS151 2001S)

[Current]
[Discussions]
[Glance]
[Honesty]
[Instructions]
[Links]
[News]
[Search]
[Syllabus]
**Primary**

[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Quizzes]
[Readings]
[Reference]
**Sets**

[Blackboard]
[Scheme Report]
[SamR's Schedule]
[Rebelsky/Fall 2000]
[Walker/Fall2000]
[Stone/Spring2000]
**Links**

`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 (listv_{0 }v_{1}v..._{2}v_{n-1}v))_{n}

i. We could interpret the call to insert as

(procv(proc_{0 }v(proc_{1}v... (proc_{2}v_{n-1}v) ...)))_{n}

ii. We could interpret the call to insert as

(proc (proc ... (proc (proc (procv_{0 }v)_{1}v)_{2}v) ..._{3}v)_{n-1}v)_{n}

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

(v+ (_{0 }v+ (_{1}v+ ... + (_{2}v+_{n-1}v) ...)))_{n}

or like this

(( ... ((v+_{0 }v) +_{1}v) + ... +_{2}v) +_{n-1}v)_{n}

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 should
find that this works like the standard version of `sum`

.

c. Implement the leftmost version of `insert`

. You should
find that this works more like the version of `sum`

we did
in class.

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`

.

In the reading, you saw how we might define `left-section`

,
which fills in the left of the two arguments of a binary procedure.
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.)

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)

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`

.

Define `intersection`

(given two lists with no
duplicates, return the list
containing only elements that appear in both lists) using
`remove`

, `complement`

, `member`

,
and `right-section`

.

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.

Thursday, 2 November 2000 [Samuel A. Rebelsky]

- Created. Problems generally taken from elsewhere and reworded slightly.
- This version available at
`http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/hop.html`

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]

- Removed 6b.
- Updated 6 to clarify what procedures are available.
- This version available at
`http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/Labs/more-higher-order.html`

[Current]
[Discussions]
[Glance]
[Honesty]
[Instructions]
[Links]
[News]
[Search]
[Syllabus]
**Primary**

[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Quizzes]
[Readings]
[Reference]
**Sets**

[Blackboard]
[Scheme Report]
[SamR's Schedule]
[Rebelsky/Fall 2000]
[Walker/Fall2000]
[Stone/Spring2000]
**Links**

**Disclaimer**:
I usually create these pages on the fly. This means that they
are rarely proofread and may contain bad grammar and incorrect details.
It also means that I may update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.

This page was generated by Siteweaver on Thu May 3 23:07:53 2001.

This page may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/more-higher-order.html`

.

You may validate
this page's HTML.

The source was last modified Wed Apr 4 08:15:49 2001.