Computer Science Fundamentals (CS153 2004S)
[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]
Summary: We continue to explore higherorder procedures.
Contents:
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 v_{0} v_{1} v_{2} ... v_{n1} v_{n}))
i. We could interpret the call to insert as
(proc v_{0} (proc v_{1} (proc v_{2} ... (proc v_{n1} v_{n}) ...)))
ii. We could interpret the call to insert as
(proc (proc ... (proc (proc (proc v_{0} v_{1}) v_{2}) v_{3}) ... v_{n1}) 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_{n1} + v_{n}) ...)))
or like this
(( ... ((v_{0} + v_{1}) + v_{2}) + ... + v_{n1}) + 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 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 stringappend
, as
in (leftmostinsert stringappend '("a" "b" "c" "d" "e"))
,
which will help you catch interesting rearrangement errors.
a. Define and test a generatelist
procedure that takes two
arguments: (1) a oneargument 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,
> (generatelist (lambda (x) (* x x)) 6) (0 1 4 9 16 25)
b. Define and test a generatelister
procedure that takes
one argument  a oneargument 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 leftsection
,
which fills in the left of the two arguments of a binary procedure.
Document, define, and test the analogous higherorder procedure
rightsection
, 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,
(rightsection expt 3)
is a procedure that computes the cube
of any number it is given.)
Using the generatelister
procedure from you defined
in a previous lab and an appropriate operator section, define a procedure
powersoftwo
that constructs and returns a list of powers
of two, in ascending order, given the length of the desired list:
> (powersoftwo 7) (1 2 4 8 16 32 64)
Here is an interesting list of symbols:
(define badadjectives (list 'grody 'sweet 'awesome))
Define a Scheme procedure removebadadjectives
that takes a
list of nonempty lists as its argument and filters out of it the lists in
which the first element is also an element of
badadjectives
. For example,
> (removebadadjectives (list (list 'awesome 'cool 'pizza)
(list 'wicked 'cool 'music)
(list 'supremely 'awesome 'food)
(list 'grody 'gunk)))
((wicked cool music) (supremely awesome food))
The intersection of two lists is a list that contains all of
the elements that appear in both lists. Using
remove
, complement
, member
,
and rightsection
, define (intersect lst1 lst2)
,
a procedure that interesects two lists.
Note that by remove
, I mean makeremover
from
the second reading on higherorder
procedures.
You should not use direct recursion in defining
intersect
.
The filters constructed by remove
are designed to
exclude list elements that satisfy a given predicate. Define a
higherorder procedure makefilter
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 (makefilter even?)
to a list of integers should return
a list consisting of just the even elements of the given list.
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.
(rightsection binproc val)
converts a
binary procedure to a unary procedure by filling in the second argument.
You should have defined rightsection
for this lab.
Thursday, 2 November 2000 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/hop.html
Wednesday, 14 February 2001 [Samuel A. Rebelsky]
Tuesday, 3 April 2001 [Samuel A. Rebelsky]
Wednesday, 4 April 2001 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/Labs/morehigherorder.html
Friday, 18 October 2002 [Samuel A. Rebelsky]
insert
).
insert
). The
stringappend example is due to Philip MorseFortier.
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/morehigherorder.html
Monday, 17 February 2003 [Samuel A. Rebelsky]
 This version available at
http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2003S/Labs/morehigherorder.html
Tuesday, 17 February 2004 [Samuel A. Rebelsky]
 Rewrote problem 5 from
removerepublicans
to removebadadjectives
.
 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/morehigherorder.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/higherorder2.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby
Samuel A. Rebelsky,
rebelsky@grinnell.edu