Currying and higher order functions (team assignment)
If you are on a team, this means that you and your partner should be doing the entirety of this assignment side-by-side, on a single computer, where one person is "driving" and the other is "navigating." Take turns every so often who is driving; you should each spend approximately 50% of the time driving.
Currying
First, here's a super quick overview on currying (to be discussed in class further): a curried function to handle multiplication can be defined as:
(define mult (lambda (a) (lambda (b) (* a b))))
A curried function of two arguments, for example, is one that really just takes one argument, and returns another function to handle the second argument.
(a) Define a function curry3
that takes a three-argument function and returns a
curried version of that function. Thus ((((curry3 f) x) y) z)
returns the result of (f x y z)
.
(b) Define a function uncurry3
that takes a curried three-argument function
and returns a normal Scheme uncurried version of that function. Thus ((uncurry3
(curry3 f)) x y z)
returns the result of (f x y z)
.
Higher order functions
(c) In class, we will discuss / have discussed higher-order Scheme functions such as
map
, foldl
, and foldr
. Scheme provides another such function called
filter
, for which you can find documentation here. Create a function called
my-filter
that works just like filter
does, but doesn't use filter
or any
other higher-order functions.
(d) In Scheme sets can be represented as lists. However, unlike lists, the order of
values in a set is not significant. Thus both (1 2 3)
and (3 2 1)
represent
the same set. Use your my-filter
function to implement Scheme functions
(union S1 S2)
and (intersect S1 S2)
, that handle set union and set
intersection. You may assume that set elements are always atomic, and that there
are no duplicates. You must use my-filter
(or the built-in filter
, if you
didn't succeed at making my-filter
work) to do this. You can also use the
built-in function member
if you find that useful. For example:
(union '(1 2 3) '(3 2 1)) ---> (1 2 3) (union '(1 2 3) '(3 4 5)) ---> (1 2 3 4 5) (union '(a b c) '(3 2 1)) ---> (a b c 1 2 3) (intersect '(1 2 3) '(3 2 1)) ---> (1 2 3) (intersect '(1 2 3) '(4 5 6)) ---> () (intersect '(1 2 3) '(2 3 4 5 6)) ---> (2 3)
(e) Use my-filter
(or filter
) to implement the function exists
, which
returns #t
if at least one item in a list satisfies a predicate. For example:
(exists (lambda (x) (eq? x 0)) '(-1 0 1)) ----> #t (exists (lambda (x) (eq? x 2)) '(-1 0 1)) ----> #f
You must use recursion, and not iteration. You may not use
side-effects (e.g. set!
).
Submit your code in a file called higherorder.rkt
via Moodle. Make sure that
it contains a comment including the names of both team members, if there are two
of you.
Thanks to Stephen Fruend and John Mitchell for ideas.