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, 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 supplies 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, after the above is complete, should 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.

If you are working individually, you can continue to work in the my-work repl. If you are working in a pair, use the paired-work repl that you created for the BST assignment. Sharing with your partner should already be set up.

For the person on your team whose email comes second alphabetically (or just you, if you're working alone), you should now clone the repository from GitHub into Repl.it. If you're in a pair, you can in principle both be watching in multiplayer mode while you do this.

In Repl.it, make sure that you are in your home directory in the terminal window. You can always navigate there by typing

cd ~

in the terminal window. To further confirm, type pwd (which is short for "print working directory.") You should see /home/runner. If you see something different, you're not in the home directory, so try again or ask for help.

In a different browser tab (leave the one with Repl.it open), visit our our class GitHub organization page online. Once you've landed there, you should see the GitHub repository you created in the GitHub Classroom step above. It should be named scheme-higherorder-username (where username is either own username, or a combination of the two of you if you're working in a pair). Contact us for help if the repository isn't there. Click on that repository title. This should take you to the home page for that repository. There is a green box on the page that says "Clone or download." Click that box, and make sure it says "Clone with HTTPS." Highlight the https link shown, and copy it to the clipboard. The link that you're copying should look something like

https://github.com/carleton251-term/scheme-higherorder-username.git

… though your username and term will be different.

Then navigate back to the Repl.it tab with the repl that you created above, and click on the terminal window within your new repl. Your next step is to clone the repository from GitHub. To do that, type git clone, then a space, then paste in the URL from the github page that you copied from above. (To paste, you might need to right-click in the terminal window and choose paste rather than using a keyboard shortcut.)

For example, I would type the following, though your username and term will be different:

git clone https://github.com/carleton251-term/scheme-higherorder-username.git

You'll be prompted to enter your GitHub username and password.

If all goes well, you should receive a directory, titled scheme-higherorder-username. If you type ls at the prompt, you should be able to see it. It will also appear in your file browser window with Repl.it on the left. Then navigate into that directory by typing in:

cd scheme-higherorder-username

… 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 your tests may pass if you don't use my-filter or filter within your code, but the graders will take off points if you do it otherwise.

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 take off points 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)