Homework 5: Currying and higher order functions

You'll download the folder with the starter code from the link below. Like for homeworks 1 and 2, unzip the folder and move it to where you'd like: the folder for the Docker container if you're using Docker, or COURSES if you're not. Then get started in VS Code (see Homework 1 if you get stuck).

If when running tests you run into a permissions error, you can fix this by running the following code in the terminal:

chmod a+x test-e test-m

This tells the computer that all users should be permitted to execute (run) the files test-e and test-m.

Click here to download the starter files.

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

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 (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) in a useful way 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)) ;; Evaluates to (1 2 3)
(union '(1 2 3) '(3 4 5)) ;; Evaluates to (1 2 3 4 5)
(union '(a b c) '(3 2 1)) ;; Evaluates to (a b c 1 2 3)
(intersect '(1 2 3) '(3 2 1)) ;; Evaluates to (1 2 3)
(intersect '(1 2 3) '(4 5 6)) ;; Evaluates to ()
(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)

Go back and look at the sections at the end of Scheme Intro 2 labeled "How to test your work". Everything there about how to run M tests and E tests applies identically here.

You'll submit your work on Gradescope. First, create a CollaborationsAndSources.txt file in the same folder as your code. In that file, indicate in what ways (if any) you collaborated with other people on this assignment and . Indicate any people you talked about the assignment with besides your partner (if you had one), me (Anna), and our prefect. Did you share strategies with anyone else? Talk about any annoying errors and get advice? These are fine things to do, and you should note them in the CollaborationsAndSources.txt file. Give the names of people you talked with and some description of your interactions. If you used any resources outside of our course materials, that is also something to note in Collaborations.txt. If you didn't talk with anyone or use any outside sources, please note that explicitly in CollaborationsAndSources.txt. Look back at the Scheme intro 1 instructions if you want more details on the CollaborationsAndSources.txt file.

After making CollaborationsAndSources.txt and finishing the assignment, upload your files on Gradescope. On Gradescope, make sure to add your partner if you worked with a partner. This page has detailed instructions for how to do that.

Note that if you submit a zip on Gradescope, you should submit a zip of the files, not a zip of the folder that contains the files. If all tests fail on Gradescope but they're working on your machine, this is likely the problem.

On Gradescope, you should see autograder output for the same tests as you ran locally. There is a very small but possible chance that you have coded something highly unexpected that cause the tests pass on the computer you’re working on, but not on Gradescope. We will be grading this assignment based on the results of the tests on Gradescope, so you should make sure to pay attention to how the tests run there as well when you submit.

For grading, you'll earn at least an M if the following conditions are all met:

• All M tests pass
• You have used filter or my-filter as a key part of the code in the parts of the assignment where this constraint is given.
• A visual inspection of your code shows that you have not hyper-tailored your code to pass the tests. Hyper-tailoring your code would be doing things like checking for the exact input from the test, meaning you haven't written your code in a way that would work for similar inputs see Homework policies for more on this).
• You have a CollaborationsAndSources.txt with the information described above.

You'll earn an E if:

• All conditions above for an M are met.
• All the E tests pass.
• Your code is not significantly more complex than needed to accomplish the task.
• You have a comment before each function describing what the function does (its input/output behavior, not a play-by-play of "first checks… then makes a recursive call …").

If your code does not meet the criteria for an M or an E, then you'll earn a grade of NA (Not Assessable) or SP (Some Progress) for the assignment. Not Assessable means that your submission does not have an attempt at one or more functions in the assignment. Some Progress means that your submission has some code (in the correct language) for all functions in the assignment, but that the code does not pass all of the M tests, is hyper-tailored to the tests, and/or is missing a CollaborationsAndSources.txt file. You have two revisions to use at any point during the term if you earn an SP or M grade and would like to revise your code and have us change your grade.

Good luck, ask questions, and have fun!