Due: Wednesday, April 8, 2026, at 10pm

Starter code: a4_hof.zip
Upload solutions via Gradescope

Goals

This assignment is designed to help you with the following:

• practice using functions as data
• write and use higher-order functions in Scheme

Collaboration policy

For this assignment, you may work alone or with a partner, but you must type up all of the code yourself. (It is therefore unexpected for two code submissions to be completely identical.)

You may also discuss the assignment at a high level with other students.

You should list any student with whom you discussed the assignment, and the manner of discussion (high level, partner, etc.) in your readme.txt file.

If you work alone, you should say so instead.

Assessment

Core requirements:

• all CR tests pass
• your code is not hyper-tailored to pass the tests
• you use recursion, not iteration
• you do not use side effects (e.g., set!)
• readme.txt contains your collaboration statement, sources, and reflection

Advanced requirements:

• satisfy the Core requirements
• all AD tests pass
• your code is not significantly more complex than needed to accomplish the task
• each function has a comment before it describing its high-level behavior
• your code uses good Scheme coding style

Getting started

As before, you should download the starter files, unzip that file, and copy the folder to where you’ll work (probably your ProgrammingLanguages folder). Refer to the Assignment 1 instructions if you’re unsure what to do.

Part A: Higher-order functions

Your first task is to write the following functions:

• my-filter
• exists?
• find-docs (only needed for AD requirements)

Part A1: my-filter

You can find online documentation for filter here. You should write your own function my-filter that behaves just like filter, but your implementation shouldn’t use filter or any other common higher-order functions (e.g., don’t use map, fold-left, filter, etc.).

Here is an example of using my-filter:

(my-filter even? '(1 2 3 4 5))             ; evaluates to: (2 4)

Part A2: exists?

You should then use my-filter to implement exists? (or use filter if you’re having trouble getting my-filter to work). The exists? function should return #t if at least one item in a list satisfies a given predicate, or #f otherwise.

Here s an example of using exists?:

(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: The tests may pass if you don’t use my-filter/filter in your code, but you will not satisfy CR requirements if you do not use one of these functions in a non-trivial way.

Part A3: find-docs (AD only)

Suppose that we have a set of documents, each represented as a list of words, with a name for each document. We could represent this in Scheme as follows:

(define doclist '((cs (Welcome to the Carleton CS department))
                  (art (The department consists of two separate majors))
                  (geology (The geology department retains a spirit of exploration))
                  (president (Alison R Byerly is Carleton College's 12th president))))

Write a function named find-docs which takes a list in the above format, and returns a list containing the name of each document that matches a particular word. For example:

(find-docs 'department doclist)     ; evaluates to: (cs art geology)
(find-docs 'Carleton doclist)       ; evaluates to: (cs president)
(find-docs 'schiller doclist)       ; evaluates to: ()

You should make use of higher-order functions like map, fold-left, fold-right, filter (or your my-filter), exists (or exists?), and so on. You might also find the member function useful. You can use helper functions if you wish, but you should not have any recursive calls in your code—the goal is to use higher-order functions to do the work.

Part B: Currying

For the second half of the assignment, you should write the following functions:

• curry3
• uncurry3
• uncurry (only needed for AD requirements)

Part B1: curry3

As a short overview of currying, here is a curried function to multiply two numbers:

(define mult2
  (lambda (a)
    (lambda (b)
      (* a b))))

Thus, a curried function of two arguments is just one that takes one argument and returns another function to handle the second argument. We could therefore call ((mult2 5) 6) to multiple 5 and 6, giving us 30.

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

Part B2: uncurry3

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

Part B3: general uncurrying (AD only)

Define a function uncurry that takes a curried function of any number of parameters. It should return a nomral 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: why didn’t I ask you to also write a general curry function?)

Note that in your uncurry procedure, you’ll need to create a function that handles a variable number of parameters (however many the curried function took). When the parentheses are ommitted around the parameters in a 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 this function 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)

There are two general approaches here, so go with what feels natural to you:

• Create a helper function, using a separate define, that takes in a function and a list as arguments. This may be more straightforward. Note that any helper functions, like all functions you write for homework in this course, should have a comment.

• Do everything in one function, recursively. If you choose this approach, you may find yourself in a situation in which 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 (some-function 1 2 3), where each item in the list is a separate argument, rather than having (some-function '(1 2 3)) with the whole list as a single argument. The Scheme function apply can help you in this situation (it’s explained in Dybvig here). The procedure apply takes in a function and a list and acts as if that function received the elements of the list as separate arguments. For instance, (apply + '(4 5)) is equivalent to (+ 4 5).

Part C: Optional extensions

The work in this section is 100% optional and does not contribute to your grade in any way. Still, if you’re looking for an extra challenge or ideas on what to practice to study the material, there will be occasional “optional extensions” sections of assignments that contain one or more additional exercises to try.

For this assignment, you are encouraged to implement the following two functions:

• flatmap
• set-intersect

Part C1: flatmap (not graded)

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. For example:

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

(define doubleup (lambda (x) (list x x)))
(doubleup 'abc)                           ; evaluates to: (abc abc)
(flatmap doubleup '(1 2 3))               ; evaluates to: (1 1 2 2 3 3)

Part C2: set-intersect (not graded)

In Scheme, sets can be represented as lists. However, unlike in a list, 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 a procedure (set-intersect s1 s2) that computes the intersection of two provided sets. 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) in a useful way to do this. You may also find member useful.

Here are some examples:

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

Testing your work

As with the previous assignment, there are CR and AD tests for core and advanced functionality (mapping to requirements above). Look at the instructions from A2 if you want a refresher on how to run this tests.

Submitting your work

As with the previous assignments, you will submit your work in two files.

Scheme code

The file main.scm should contain all of your procedures. Make sure to add a comment above each of your procedures (including any helper functions you choose to write) to describe its behavior at a high level (e.g., what it takes as input and what it returns as output).

Readme

For each assignment for this course you will also need to submit a file readme.txt in which you should write:

1. Your collaborations with anyone on the assignment
2. Your use of any outside sources on the assignment
3. Your reflection

You should be specific about your collaborations and sources – they shouldn’t just be empty or lists of names of people. If you worked alone and/or did not use any outside sources, you should say so.

For your reflection, spend a couple of sentences answering the following:

• Were there any particular issues or challenges you dealt with in completing this assignment?
• How long did you spend on this assignment?

Submitting to Gradescope

Once you have your two files, you will combine them into a single file using this command:

./zipitup

(make sure you’re in the terminal in the assignment folder). If you get an error about file permissions, first run chmod a+x zipitup.

Submit your .zip file to Gradescope at this link.

Note that it is possible (although unlikely) that the tests will pass on your computer but fail on Gradescope. If this happens, it’s probably because you coded something in an unusual way. Double-check that you’re submitted to the correct assignment and then check if any error messages can help you troubleshoot. If you’re still having issues, check with Tanya.