Practice Problems
Throughout the year we will be posting practice problems to this page. The practice problems will range in diffculty from really easy (finger exercises to get you used to basic Racket concepts) to really hard (extra-curricular functions that you will never be held responsible for in this class). So if you are confused about Racket syntax, recursion, or higher-order functions, come to this page. If you are bored with CS19 and want to delve even deeper into the inner-workings of Racket, come to this page. It will be updated throughout the year, so keep checking back.
Simple Functions and Conditionals
Relevant as of 9/8
1. The local supermarket needs a program that can compute the value of a bag of coins. Define the program sum-coins. It consumes four numbers: the number of pennies, nickels, dimes, and quarters in the bag; it produces the amount of money in the bag.
2. An old-style movie theater has a simple profit function. Each customer pays $5 per ticket. Every performance costs the theater $20, plus $.50 per attendee. Develop the function total-profit. It consumes the number of attendees (of a show) and produces how much income the attendees produce.
3. Develop the function tax, which consumes the gross pay and produces the amount of tax owed. For a gross pay of $240 or less, the tax is 0%; for over $240 and $480 or less, the tax rate is 15%; and for any pay over $480, the tax rate is 28%.
4. Write the program discount, which takes the name of an organization that someone belongs to and produces the discount (a percentage) that the person should receive on a purchase. Members of AAA get %10, members of ACM or IEEE get %15, and members of UPE get %20. All other organizations get no discount.
Use discount to write purchase, which takes the price of an item and the name of an organization and produces the amount owed after the discount is applied.
User-defined datatypes
Relevant as of 9/10
1. Define a type for a grade record, which contains a midterm exam grade (non-negative number), final exam grade (non-negative number), and course grade (symbol or false, using the latter if no grade has been assigned yet).
2. Write a function assign-grade that takes a grade record and produces a grade record. The produced grade record has the same exam grades as the original, but has computed the course grade from the exam grades. The course grade is A for an average above 85, B for an average between 70 and 84, C for an average between 55 and 69, and NR otherwise.
3. Define a type for a student record, which contains a student's name, class year, and a grade record (use whatever type you like for the class year).
4. Write a function new-student which consumes a student name and class year and produces a student record with the given name and class year, both exam grades initialized to 0 and the course grade initialized to false.
5. Define a type for a student, where a student can be either an undergraduate, graduate, or non-degree student. Each contains the number of courses they have taken. Undergraduates have an advisor (indicated by name) and graduates have a department and which degree they are pursuing (MS or PhD).
6. Write a function finished? which consumes a student and produces a boolean indicating whether the student has enough courses to graduate. Undergraduates need 45 courses, graduates need 11 for an MS and 60 for a PhD. Non-degree students are always finished.
Lists
Relevant as of 9/15
1. Write a function eliminate-large that consumes a list of numbers and produces a lis of all numbers from the original list that are larger than 10.
2. Write a function elim-by-pred that consumes a predicate (function that returns boolean) on numbers and a list of numbers and produces the list of all numbers for which the given function returns false.
3. Write a function average that consumes a list of numbers and produces its average. Return an error message if the list is empty.
4. Write a function suffixes that consumes a list L (containing anything) and produces a list of all the suffixes of L. For example, (suffixes '(a b c d)) should produce ((a b c d) (b c d) (c d) (d) ()).
Trees
Relevant as of 9/17
1. Develop a datatype for family trees, where a family tree is either unknown or a person, where a person has a name (string), eye color (symbol), mother (family tree) and father (family tree).
2. Write a function count-persons that consumes a family tree and produces the total number of people in that tree.
3. Write a function count-gens that consumes a family tree and produces the number of generations in that tree.
4. Write a function eye-colors that consumes a family tree and produces a list of all eye colors that appear in the tree. The list may contain duplicates.
Hint: use append which consumes any number of lists and concatenates them.
Higher Order Functions
Relevant as of 10/15
1) Write a function remove-below-ten that consumes a list of numbers and produces a list with all the numbers below ten removed
2) Write a function add1-to-all that consumes a list of numbers and produces a list of the same numbers but with one added to each of them
3) Write a function say-hello-to-all that consumes a list of strings and produces a list of strings with the string "Hello, " added to the front of each.
4a) Create a struct Person that contains a name and age (name is a string and age is a non-negative integer).
4b) Write a function that takes a list of people and sorts them from oldest to youngest. Now, youngest to oldest.
4c) Write a function that takes a list of people and sorts them alphabetically by name.
5) Write a function that accepts a list of Persons and sums the ages in the list.
6a) You are planning a party and want to invite a group of Persons. Write a function that accepts a list of Persons and determines whether you can serve alcohol at the party (are all Persons in the list at least 21?)
6b) You realize you don't actually care if everyone is at least 21, because all you need is at least one person to be 21 so that that person can supply the alcohol. Write a function that accepts a list of Persons and determines if there is at least one person above the age of 21.
JAVA PROGRAMMERS STOP HERE!
Never relevant, but extra awesome
1a. Write the function compose2, which takes two functions and returns a function that is their composition. eg. ((compose2 first rest) '(a b c d)) --> 'b
1b. What is the type signature for compose2?
1c. Write the function compose3, which takes three functions f, g, h and returns their composition f o g o h. Write down its type signature. This should be trivial after parts a and b.
1d. Write the function compose-list, which takes a list of functions, each of one argument, and produces a single function that is their composition.
eg. (compose-list (list add1 sub1 (lambda (x) (* x 3))))
1e. If your answer to part d was a recursive function, rewrite using foldr or foldl; if you used one of the HOFs, rewrite it as a recursive function.
1f. (skip on first pass through this set of exercises) The type of compose-list, in the most general situation, is pretty interesting. Describe the type of compose-list (we are not asking you for a Typed Racket contract here).
2a. Read the documentation for apply. Try simple things like (apply string-append (list "ab" "cd" "ef"))
2b. A standard function in functional programming is concatMap. It takes a function f and a list l, and applies the function to each element in l. The function f returns a list for each element; concatMap then produces one final list that consists of all the results appended.
eg. (concatMap string->list (list "abcd" "efgh" "hijk")). Compare this to (map string->list ...) and see for yourself what concatMap does.
2c. What is the type of concatMap?
2d. Implement concatMap in three different ways: as a straight-up recursive function; using a fold and a map; using apply and map. Feel free to use the standard scheme function append (look it up!)
2e. Racket map is different from other brands of map you may have encountered. It takes a single function of any number of arguments (say n), and then n lists. It applies the function to the first of each list (there are n lists, and the function takes n arguments, so it all works out), and then to the second, and so on. Read the documentation for map, and describe its type signature in a few sentences.
2f. (skip on first pass) Use apply and map to solve the following programming puzzle. You are to write a function thatg transposes a matrix. The matrix is given as a (Listof (Listof Integer)), like so: '((1 2 3) (4 5 6) (7 8 9)). Its transposition is: '((1 4 7) (2 5 8) (3 6 9)). First write the function as straight-up recursion; once you're comfortable with what's going on here, try your hand at this:
(define (transpose matrix)
(_________ ___________ ___________ ________))
where each blank represents ONE WORD (ie. scheme identifier like "string->list", "append", or anything else like that). In particular, you may not type any parentheses. Your biggest hint should come from traffic analysis (WW2 term for "context") ie. this is a set of exercises about apply and map.
3a. Some functional languages only have functions of one argument. How does one get by in a world of only single argument functions? Well, things like "+", which intuitively take two arguments, actually take one argument and return a function of one argument. So, for example, in a hypothetical world where Racket/Racket works this way, (+ 1) would evaluate to a function; let's call it p1. p1 is a function that always takes one argument, and returns a number one greater. Similarly (* 3) would be a function that multiplies by 3. Your job in part a is to grok this concept, and look up currying on wikipedia. After that, write the function +/curried and play around with it. One way to think about this is to think of functions as algebraic expressions over their arguments (like a polynomial over x, y and z). Each time you apply it to an argument, you "fill in" for that argument. The result may or may not be a final answer, depending on whether all the arguments have been "filled in".
3b. Deconstruct (map (+ 1)). Since map ordinarily takes two arguments, by applying it to just one we clearly get a function back. This is a function that itself will take one argument, and produce the result that we would ordinarily expect from (map f l). Write a function map/curried that takes one argument (a function). Verify that it works as discussed above; try things like ((map/curried (+/curried 1)) '(1 2 3))
3c. Write a function call curry2 that curries functions of two arguments ie. turns it into a function, that returns a function of one arg. What is the type of curry2?
3d. Lambdas can take a variable number of arguments. Here's how this work: normally, you'd write (lambda (arg) ...). If you say (lambda args ...), then args is a list containing all the arguments passed in. Experiment with this. Write a function that mimics the builtin + (use folds).
3e. We're not going to go all the way here with a full-fledged currier -- one that takes an arbitrary functions, and curries it all the way so that each application of the function returns a function of one argument, that takes the computation one step further. A much simpler thing to write is what I will call peel: a function that curries a function in its first argument. It takes a function, and returns a function of one argument. This function, in turn, is a function of one less argument than what we started off with. Functions are just like onions, they make you cry.
Programming with