4.1 Goal🔗

Functional programmers don’t actually spend all day writing recursive functions over lists. Rather, they use so-called “higher-order” functions, which are functions that consume other functions, to do that kind of work. That is, in functional programming, a loop is just a function, and different kinds of loops correspond to different kinds of higher-order functions. In this assignment you will learn about some of these “looping functions”.

4.2 Plagiarism🔗

This assignment has become notorious for plagiarism. Every year we have found a significant number of students (up to 20%) have cheated on at least one of the problems. In the past we gave students another chance, but this has gotten tiresome, especially given the reason provided.

The standard argument we have heard is, “I cheated because the problem was hard”. This is a terrible argument. The problems are here to both prepare you for 0190 and make sure that it’s the right course for you. If you struggle here, you will struggle there also (perhaps much more!). How do you plan to handle that? Do you intend to cheat throughout the semester as well?

If we have good reason to believe you have plagiarized or used AI toolsYou should anyway be careful about using AI tools: recent research shows that it both hurts learning and gives you an inflated sense of confidence.), we will refer you to the Academic Code committee, which will very likely sanction you. You will also not be admitted to 0190. So you will end up with a sanction on a course you didn’t take, couldn’t take, and that you didn’t need to take. What a way, especially for those of you starting college, to begin your academic career!

Please also remember that there’s going to be an in-person, on-paper exam that will cover similar material. So if you cheat now but don’t do well on that exam later, you won’t be able to take the class.

In short, please do the work honestly and turn in what you are able to do.

4.3 Language🔗

For the following assignment, you must use Racket’s Intermediate Student with lambda language. Go to the Language menu, select Choose Language, and pick the language from the Teaching Languages section.

4.4 Library🔗

You may also use any library function you were permitted to use on prior assignments, particularly in Placement 3.

Any other library function you need, you should implement yourself using the above set of functions.

4.5 Reading🔗

4.6 Programming🔗

You will define the following functions. In doing so, you are not allowed to use recursion (where a function calls itself) directly;Don’t try to be clever about this, e.g., having A call B and then B call A. That’s still recursion; it’s called mutual recursion. you must use one of the functions listed in Library in its stead. You are of course welcome to write helper functions (that follow the same rule).

You are welcome to reuse anything appropriate that you wish from your Placement 3 submission, e.g., purpose statements and tests. You do not need to write templates.

We do expect you to do a thorough job on testing, building on the feedback you receive for Placement 3.

• elim-contains-char :: Char, List-of-Strings -> List-of-Strings

  Consumes a list of strings and produces a list of the same strings, in the same order, excluding those strings that contain the given character.

• is-palindrome :: String -> Boolean

  A palindrome is a string with the same letters in each of forward and reverse order (ignoring capitalization). Design a program called is-palindrome that consumes a string and determines whether the string with all spaces and punctuation removed is a palindrome. Treat all non-alphanumeric characters as punctuation. The functions char-alphabetic? and char-numeric? may be useful.

• ready-teams :: List-of-String, List-of-Team -> List-of-String

  A consulting firm assembles teams to send out on client engagements. A team can only be sent out once it covers every skill the engagement calls for: for each required skill, at least one person on the team must have it. A single person may well cover several of the required skills, and a team may have people whose skills aren’t required at all.

  Team data are represented as follows:

  ;; name :: String

  ;; skills :: List-of-String

  (define-struct person [name skills])

  ;; name :: String

  ;; people :: List-of-person

  (define-struct team [name people])

  Design the function ready-teams, which consumes a list of the skills required for an engagement and a list of teams, and produces the names of those teams that are ready to be sent out. Team names should be in the same order as they appear in the input.

  Think carefully about what should happen when a team has no people on it, and when the engagement requires no skills at all. How can you test your understanding?

• orders-to-bill :: Number, List-of-Order -> List-of-String

  An online store offers free shipping on any order whose total meets or exceeds some threshold. When a customer later returns part of an order, those items are marked as returned, and what’s left may no longer clear the threshold—in which case the store bills the customer for shipping after all. But if the customer returns everything, the order is treated as cancelled and they are billed nothing.

  Order data are represented as follows:

  ;; name :: String

  ;; price :: Number

  ;; returned? :: Boolean

  (define-struct item [name price returned?])

  ;; id :: String

  ;; items :: List-of-item

  (define-struct order [id items])

  Design the function orders-to-bill, which consumes the free-shipping threshold and a list of orders, and produces the ids of exactly those orders whose customer must be billed for shipping. These are the ones where the kept items—those not marked returned—total strictly less than the threshold, yet at least one item was kept. An order whose kept items still meet the threshold, and an order in which every item was returned, are not billed for shipping. Order ids should be in the same order as they appear in the input.

  You may find it useful to write helper functions that decompose the task into cleaner, more easily comprehensible pieces, and then compose those to produce the solution.

4.7 Turnin🔗

You will have two submission drops on Gradescope: one each for programs and tests.

Please name the program file p4-code.rkt.

For the test files, please use the following names:

Please remind yourself of the instructions from Placement 3 on the contents of these files. Please remember that if you don’t follow the rules, our testing infrastructure will probably error and give you zero credit. So please take some time to double-check everything.

You will upload your work using Gradescope.