Homework 5: Currying and higher order functions

First, here's a super quick overview on currying: 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.

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).

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).

Heads up: this section is only required for the E tests

Define a function uncurry that takes a curried function of any number of parameters. It should return a normal Scheme uncurried version of that function. Thus ((uncurry (curry3 f)) x y z) returns the result of (f x y z), ((uncurry (curry4 g)) w x y z) would return the result of (g w x y z) if we had written curry4, and so on. (Thought question for yourself only: why didn't I ask you to also write a general curry function?)

Note that in your uncurry, you'll need to create a function that handles a variable number of parameters (however many parameters the curried function took. When the parentheses are omitted around the parameters in the lambda, Scheme bundles all inputs into a list. Here's an example:

(define get-all-but-first-input
  (lambda args 
    (cdr args)))

I can use it as follows:

(get-all-but-first-input 1 2 3) ;; Evaluates to (2 3)
(get-all-but-first-input 1 2 3 4 5) ;; Evaluates to (2 3 4 5)

Tips: There are two general approaches here:

• Create a helper function, using a separate define that takes in a function and a list as arguments. I think this may be the more straightforward approach. Note that helper functions, like all functions, should have a comment.
• Do everything in one function, recursively. If you take this option, you may find yourself in a situation where you wish you could somehow call a function on a list of arguments and have it treat that list as if it were not a list. I.e., you have the list (1 2 3) and what you'd like to do is (myfn 1 2 3), where each item in the list is a separate argument. The scheme function apply can help you in this situation. Dybvig talks about it here. apply can take in a function and a list and act as if that function received the elements of the list as separate arguments. For instance, (apply + '(4 5)) is equivalent to (+ 4 5).

We will discuss / have discussed higher-order Scheme functions such as map, fold-left, and fold-right. 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.

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 (set-union S1 S2) and (set-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) in a useful way to do this. You can also use the built-in function member if you find that useful. For example:

(set-union '(1 2 3) '(3 2 1)) ;; Evaluates to (1 2 3)
(set-union '(1 2 3) '(3 4 5)) ;; Evaluates to (1 2 3 4 5)
(set-union '(a b c) '(3 2 1)) ;; Evaluates to (a b c 1 2 3)
(set-intersect '(1 2 3) '(3 2 1)) ;; Evaluates to (1 2 3)
(set-intersect '(1 2 3) '(4 5 6)) ;; Evaluates to ()
(set-intersect '(1 2 3) '(2 3 4 5 6)) ;; Evaluates to (2 3) 

Note that you must use my-filter or filter within your code in order to earn a grade of M or E. Passing the tests alone is not sufficient.

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))   ;; Evaluates to   #t
(exists (lambda (x) (eq? x 2)) '(-1 0 1))   ;; Evaluates to  #f

Note that your tests may pass if you don't use my-filter or filter within your code, but the graders will not grant a grade of M or E if you do do not use one of these functions in a non-trivial way.

Define a function flatmap that works like map, but if the function returns a list of values, those values are "flattened" for the final list. Here's an example:

(define plus1 (lambda (x) (+ x 1)))
(flatmap plus1 '(1 2 3)) ;; Evaluates to (2 3 4)

(define doubleup (lambda (x) (list x x)))
(flatmap doubleup '(1 2 3)) ;; Evaluates to (1 1 2 2 3 3)

As with previous assignments, there are M tests and E tests. See the section of Scheme Intro 2 labeled "How to test your work" if you need a refresher on how to run these tests.