[Current] [News] [Glance] [Discussions] [Instructions] [Search] [Links] [Handouts] [Outlines] [Readings] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [Fall2000.01] [Spring2000]
If you have not done so already, please scan the corresponding reading on higher-order procedures.
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
.
Define a procedure, dot-product
, that takes as arguments two
lists of numbers, equal in length, and returns the sum of the products
of corresponding elements of the arguments:
> (dot-product (list 1 2 4 8) (list 11 5 7 3)) 73 ; ... because (1 x 11) + (2 x 5) + (4 x 7) + (8 x 3) = 11 + 10 + 28 + 24 = 73 > (dot-product null null) 0 ; ... because in this case there are no products to add
Use apply
and map
to give an extremely
concise definition of this procedure.
Sarah and Steven Schemer suggest that ``apply
is irrelevant.
After all,'' they say, ``when you write
(apply prog (arg1 ... argn))
you're just doing the same thing as
(proc arg1 arg2 ... argn)
.''
Given your experience in the previous exercise, are they correct? Why or why not?
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
earlier 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
.
a. Define intersection
(given two lists, return the list
containing only elements that appear in both lists) using
remove
and right-section
.
b. Rewrite intersection
so that it takes an arbitrary
number of lists as parameters.
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
[Current] [News] [Glance] [Discussions] [Instructions] [Search] [Links] [Handouts] [Outlines] [Readings] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [Fall2000.01] [Spring2000]
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/hop.html
Source text last modified Thu Nov 2 14:19:56 2000.
This page generated on Thu Nov 2 14:24:02 2000 by Siteweaver. Validate this page's HTML.
Contact our webmaster at rebelsky@grinnell.edu