Currying and higher order functions (pair assignment)

The first thing you’ll need to do is to create a repository for your project using GitHub classroom. If you are working on a team, this repository will be shared, so only one of you should do this. To help reduce a round of communication, I’m going to designate that if you are working in a pair, the member of your team whose Carleton official email address comes second alphabetically should do this next step of setting up the GitHub repository. This is opposite from the previous pair assignment; I’m trying to give everyone an equal chance to participate. If you are working alone, then you should do this step.

If you are the designated person above, who I will refer to as Person A, visit this GitHub classroom link (which I’ve placed in Moodle). Log into GitHub if your browser prompts you to after you get to GitHub. You should be taken to a screen that invites you to either “Join an existing team” or to “Create a new team”. Pick the team that you created for the last team assignment. GitHub should then hopefully respond with a screen that says “You are ready to go!” and supply you with a link for the repository that you are creating. Click on that link, and you should be taken to the repository. If you’ve gotten this far, you have successfully created the repository, and you the user who is logged in have access to it. Contact your partner if you have one and tell them that this step worked. (If you are working alone on the project, you can skip the next step.)

The other one of you (i.e., Person B): after the above is complete, visit the same GitHub classroom link in the first sentence in the previous paragraph. You’ll see the screen asking you to “Join an existing team” or to “Create a new team.” You should be able to see the team that your partner created above; click the “Join” button. This should then take you to the “You are ready to go!” screen, and you can hopefully find a link to the repository. Click on it. You now both have access to the same GitHub repository.

Person A should continue these steps below. You do not need to wait for Person B to finish the last step above before proceeding forward. (In other words, Person A can set up this whole thing if you like, and Person B can catch up later.)

Person A: Once you see your repository in GitHub (not Repl.it), you should see a button labeled “Work in Repl.it.” Click it. That should set up a new repl in Repl.it, and you should be all set to work. Hopefully this is more streamlined than it was in the first assignment, since more of it should be set up, but ask for help if need be. As always, make sure the repl created in Repl.it is private.

Once you have created the repl, click the “Share” button at the top right in Repl.it, and invite your partner, i.e. Person B. (If you’re working alone, skip this step.) You can do this by typing in their Carleton email address, or by emailing them directly the sharing link. Sometimes the email is a little slow to send, but it works. Perhaps try both strategies.

… and you should be all set to work!

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

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

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))   ---->   #t
(exists (lambda (x) (eq? x 2)) '(-1 0 1))   ---->   #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 it otherwise.

Define a function uncurry that takes a curried function of any number of parameters and returns 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?)

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)) ----> (2 3 4)

(define doubleup (lambda (x) (list x x)))
(flatmap doubleup '(1 2 3)) ----> (1 1 2 2 3 3)