Functional Problem Solving (CSC 151 2014F) : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Summary: In this laboratory, you will use and define higher-order procedures.
Make sure that you understand what map
,
compose
, o
,
left-section
,
right-section
, and
apply
are intended to do.
map
and apply
a. Use
apply
and map
to sum the
first elements of each list in a list of lists of numbers. The result
should be a number.
>
(apply _____ (map _____ (list (list 1 2 3) (list 4 5 6) (list 7 8 9 10) (list 11 12))))
23 ; 1 + 4 + 7 + 11
b. Use
apply
and map
to sum the
last elements of each list in a list of lists of numbers. The result
should be a number.
>
(apply _____ (map _____ (list (list 1 2 3) (list 4 5 6) (list 7 8 9 10) (list 11 12))))
31 ; 3 + 6 + 10 + 12
a. Here are four expressions to generate the successors of the squares of the first ten positive integers. Verify that each works correctly.
(define v1 (map increment (map square (map increment (iota 10))))) (define v2 (map (lambda (i) (increment (square (increment i)))) (iota 10))) (define v3 (map (compose increment (compose square increment)) (iota 10))) (define v4 (map (o increment square increment) (iota 10)))
b. Which of the four definitions above you prefer? Why? Be prepared to discuss your reasons with the class.
Use apply
and map
to
concisely define a procedure, (
, 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
lst1
lst2
)
>
(dot-product (list 1 2 4 8) (list 11 5 7 3))
73
>
(dot-product null null)
0
Note that we get the first result because (1 x 11) + (2 x 5) + (4 x 7) + (8 x 3) = 11 + 10 + 28 + 24 = 73 and the second because there are no products to add.
Note: You should not use recursion.
The procedure (
is intended to produce
an acronym from a list of strings. For example,
acronym
strings
)
>
(acronym (list "GNU" "Image" "Manipulation" "Program"))
"GIMP"
>
(acronym (list "International" "Business" "Machinery"))
"IBM"
>
(acronym (list "Grinnell" "Independent" "Musical" "Productions"))
"GIMP"
Write acronym
as concisely as possible.
As a hint, you will want to use
string-ref
,
list->string
,
map
,
and either l-s
or r-s
.
(Recall that (
produces the string-ref
string
i
)i
th character in
string
.
list->string
takes a list of characters and turns
it into a string.)
Write a procedure, (
),
that takes a list and predicate as parameters and removes all elements for which
list-remove
lst
predicate
predicate
holds.
For example,
>
(define remove-whitespace (r-s list-remove char-whitespace?))
>
(remove-whitespace (list #\a #\space #\b #\c))
(#\a #\b #\c)
>
(list->string (remove-whitespace (string->list "Hello, my name is Dr. gigls")))
"Hello,mynameisDr.gigls"
Note: Although this problem
can be solved using map
and
apply
, it is much more straightforward to solve
using recursion.
It is often the case that we have situations in which we need more than
one predicate to hold. For example, since the odd?
predicate only works with integers, it is often helpful to test whether
a value is an integer before testing whether it is odd.
>
(odd? 3)
#t
>
(odd? 4)
#f
>
(odd? 3.5)
odd?: expects argument of type <integer>; given 3.5>
(define odd-integer? (lambda (val) (and (integer? val) (odd? val))))
>
(odd-integer? 3.5)
#f
>
(odd-integer? 3)
#t
>
(odd-integer? 4)
#f
But if it's common to combine predicates into a new predicate, we
might want to write a higher-order procedure that does that. For
example, we might write a procedure, (
that takes
two predicates as parameters, and returns a new predicate that holds
only when both of its component predicates hold.
both
p1
p2
)
>
(define odd-integer? (both integer? odd?))
>
(odd-integer? 3)
#t
>
(define one-element-list? (both pair? (o null? cdr)))
>
(one-element-list? 2)
#f
>
(one-element-list? null)
#f
>
(one-element-list? (list 1))
#t
>
(one-element-list? (cons 2 null))
#t
>
(one-element-list? (cons 2 3))
#f
Write the both
procedure.
a. Write (
, a procedure which takes two predicates
as parameters and returns a predicate that holds when either of those
predicates holds.
either
p1
p2
)
>
(define RGB-RED (rgb-new 255 0 0))
>
(rgb? RGB-RED)
#t
>
(color-name? RGB-RED)
#f
>
(color-name? "red")
#t
>
(rgb? "red")
#f
>
(define simple-color? (either color-name? rgb?))
>
(simple-color? "red")
#t
>
(simple-color? RGB-RED)
#t
>
(simple-color? (list 255 0 255))
#f
b. Write a procedure, (
, that returns negate
pred
)#t
on
the values for which pred
returns
#f
, and returns #f
on the values for
which pred
holds.
>
(define non-empty-list? (both list? (negate null?)))
>
(non-empty-list? (list 1 2 3))
#t
>
(non-empty-list? 32)
#f
>
(non-empty-list? (cons 1 2))
#f
>
(non-empty-list? null)
#f
Write a procedure, (
, that replaces
each element of vector-map!
proc
vec
)vec
with the result of applying
proc
to the original element.