From-CS15 Homework 1: Functional Programming

--- tags: Homeworks --- # From-CS15 Homework 1: Functional Programming **Due:** Friday Jan 29, anywhere on earth (= 8am EST on 1/30) **Submit to:** Gradescope **Collaboration:** Collaborate as much as you like, but make sure you are able to write these for yourself, as we will assume you can program in this style for the rest of CS18. ### Introduction This assignment gets you practice writing programs in the functional programming style. Such programs have three key features: - they don't use assignment statements or operations that modify the contents of data - they use *higher-order functions*, which are a form of iterators that you customize with the specific function to perform on each element of your data. Here, we will work with two common iterators: `map` and `filter` - they create additional intermediate data structures (like additional lists) as part of their computations (in contrast to modifying lists and arrays in place) The [coming-from-15 webpage](https://brown-cs18-master.github.io/coming-from-15.html) provides both Java and Python versions of a simple animals class hierarchy. It also contains a Python file showing how to write a recursive function to process linked lists. Use these to learn the Python syntax and code style that you'll need for this segment. **For those of you who have programmed in Python before**, we are explicitly asking you to work with dataclasses, rather than full Python classes. Why? Because dataclasses do not support methods inside classes. As part of preparing you for the functional programming work to come later in 18, we want you to practice writing programs with top-level functions rather than methods. *You may use any Python environment that you want for these problems. We've set up stencil files (with the function names and types) in one possible online Python editor to make things easier. But if you prefer another tool, that's fine. Just copy out the stencil to your preferred Python tool.* ## Problems Write a solution to each of the following problems, using a combination of explicit list-recursion, `map`, and `filter`. **Do not use for-loops to solve these problems**. You've passed CS15: we know you can write code with for loops. The point here is to get you used to writing recursive functions to process recursively-defined datatypes (in this case, lists). **Note:** If you are new to writing basic recursive functions to process lists, we recommend that you do the two practice problems at the end of the `recursive_lists.py` file before working on these problems. ### Rainfall Design a program called rainfall that consumes a list of real numbers representing daily rainfall readings. The list may contain the number -999 indicating the end of the data of interest. Produce the average of the non-negative values in the list up to the first -999 (if it shows up). There may be negative numbers other than -999 in the list (representing faulty readings). Assume that there is at least one non-negative number before -999. Example: ```rainfall([list: 1, -2, 5, -999, 8]) is 3``` **Task:** Write the rainfall program. Make sure to test your implementation thoroughly. [Here is a link](https://tio.run/##bY6xasNAEER7fcXgFJYhRUw6gbv0btIvi7UXHZxWZndF0NcrJzuIFKln3ry5LzFM@r6uvSQYZ01cSjsuVLLHqWsAvODz@nHtkHIpyIoYsiPNeos8KVrWHt@WQ8C6YJByF9tjr20OLNMMFekR02mbhEnMpnhrmuavmEI86MYu3j7lv3Z04L7iNcYjRppsm7Wd3Z0PjN3FAmdcLji/4iBmFRjFnb/kULU5gUh5FKKtcyQa6xDR8an999G6/gA) to the stencil code and a python environment where you can write your solution. ### Length of Triples **Task** Design a program called max_triple_length that consumes a list of strings and produces the length of the longest concatenation of three consecutive elements. **Assume the input contains at least three strings.** [Here is a link ](https://tio.run/##dY4xC8JADEb3@xWfOKib4lZwc3dxD4eX2sA1V@5StL@@tha6iGOSx8vrBmuSnscxcI3Wv8mydJEpsj6t2bcDRSl2qByALe63661CLTFCFNZIQd3rwyQp9l4DXlmM4XVAw7HjvJ7LRHvDkHooc4Clw6zMbH1WHJ2b5FxM9Imtc3OMTSP9Fi0pa4sPAW3K/MXx8IXL5gv4UjgbTrhccHJOahCpb5lo3uxoUosS7Rbdv2fj@AE) to the stencil code and python environment where you can write your solution. **Note:** Both recursion and `map()` may be necessary for this problem. Using a helper function may be useful. Example: `max_triple_length(["a", "bb", "c", "dd"])` is 5  ### Shopping Discount An online clothing store applies discounts during checkout. A shopping cart is a list of the items being purchased. Each item has a name (a string like “shoes”) and a price (a real number like 12.50). In Pyret, we can represent data **Task:** Design a program called `checkout` that consumes a shopping cart and produces the total cost of the cart after applying the following two discounts: * if the cart contains at least 100 worth of shoes, take 20% off the cost of all shoes (match only items whose exact name is "shoes") * if the cart contains at least two hats, take 10 off the total of the cart (match only items whose exact name is "hat") * Assume the cart is represented as follows: `[(name, cost),...]` [Here is a link ](https://tio.run/##XY2xCsJAEET7@4oRC02n2AXS2aexX5a7DTlM9uRug@Tro4mQwm6Yecx7zdYnvS1LkA6@F/9Mk509Z6tqB@CIR3tva3RxGBAV1seCblJvMSnOrAHvHE3AOqOX4SV5n8uXZsOcJqhIgKVqvcxiU1Zcvtm5VWtSjHb3z7uLOQSMKctGwXORctgALkWy4YqmwdW52IFIeRSitTkRjRyV6PS7@3Msywc) to the stencil code and python environment where you can write your solution. Example: `checkout([("shoes", 25), ("bag", 50), ("shoes", 85), ("hat",15)]) = 153` **Note**: In python `filter(some_function, some_list)` returns a filter object. `list(filter_object)` converts it to a list. ### Distinct List Design a program that takes in a list and produces a list of its unique elements [Here is a link ](https://tio.run/##Xc0xC8JADIbh/X7FJw7qZnET3Ny7uIfDS2mgzZVLivTX17ZCB9fk5XuGydust3lO3CCJuejbz4Xtcg8AjnjVz/qORroOovBWDM24NJIV56gJnyLOiDqh5W7gsr9tqaNjyiOUOcHzZZ0s7GNRXENYSWdz2t0fuqsxJfS58FbhHY3tsAXRjIujwuOBKoQgDYg09ky0nk5EfRQlOv32/pB5/gI) to the stencil code and python environment where you can write your solution. Example: `distinct([1, 1, 2, 2, 3, 3, 4, 4])` is `[1, 2, 3, 4]`