Due date and time: Friday, December 7, 11:59pm
This project is to be done in pairs using the "pair programming" technique
Introduction
For this project, you're being asked to write eleven Racket functions according to the given specifications. This will give you the opportunity to practice functional programming and, in addition, learn more about how to approach and solve problems using recursion, a skill that will continue to benefit you in ICS 23 / CSE 23 and beyond, even if you don't ever write another line of Racket code again. Functional programming is something you're likely to see again in your coursework if you take a course in programming languages (e.g., CompSci 141 / CSE 141), and functional programming features are gradually beginning to work their way into more mainstream programming languages, for a variety of reasons, so knowing something about it will make you more prepared to keep up with the inevitable changes in programming languages over time.
Choosing a partner
Pair programming is again required on this project, so you'll need to choose a partner from among the people enrolled in your lab section, different from the people with whom you've partnered previously. Remember, too, that you are required to partner with someone who is enrolled in your lab section.
If you're having trouble finding a partner, notify your TA, so that you can be assisted in finding one. If you have not found a partner and notified your TA of the pairing by the end of your lab section meeting on Wednesday, November 28, we reserve the right to assign you a partner, in which case we will notify you via email of your partnership arrangement. Once your TA has selected a partner for you in this fashion, we will not allow you to switch to another one, so the best way to control your destiny is to choose a partner yourself.
You will not receive credit on this assignment if you work on it alone without the prior consent of the instructor. (Please note that "prior consent" does not include approaching us the day the project is due, having completed it on your own, and telling us that you haven't been able to find a partner.)
Using DrRacket
DrRacket is an environment for writing and running programs written in a variety of similar-looking programming languages collectively called Racket, which are predominantly focused on a style of programming called functional programming. (These languages include a well-known language called Scheme, on which our particular dialect of Racket is based; if you've use Scheme before, you will discover some differences between full, standard Scheme and our chosen subset, but you should be able to adapt quickly.)
DrRacket is built primarily for use in teaching and learning programming, though it does support a surprising array of "real-world" functionality, as well. It runs on all versions of Windows, Mac OS X, and various flavors of Unix and Linux. DrRacket is already installed on the machines in the lab, and it can be downloaded free for your use at racket-lang.org. The latest version, as of this writing, is 5.3, though new versions come out somewhat regularly; the explanation below assumes that you're using that version. (Previous versions are essentially the same.)
Installation of DrRacket on Windows is a snap. (I haven't installed it on other operating systems, but I presume it's just as simple on the others.) Just execute the setup program and it will take care of everything. Once the installer is finished, you'll find a folder called Racket in the Programs folder on your Start menu. Select DrRacket from that menu, and off you go.
When you first execute DrRacket, you'll be prompted to choose a language from a list. Remember that DrRacket supports a variety of different languages, each including a different combination of libraries and features. (If you're not prompted to select a language, you can also select one at any time by going to the Language menu and selecting Choose Language....) On the list of languages, under Teaching Languages, click How to Design Programs and then Advanced Student, then click OK. Finally, click the Run button near the top-right corner of the main Racket window. Now you should be ready to roll!
Below is a screenshot of DrRacket in action.
The bottom half of the DrRacket window is the interpreter. Simply type an expression into the interpreter and you'll get back an answer, just like we talked about in lecture.
In the top half of the window, you can write Racket code and save it into a file. This is where you'll write the functions and unit tests that you need to write for this project. When you make a change to your code and then wish to test it in the interpreter, click the Run button on the toolbar. This causes the interpreter to be restarted and all of the code in the top half of the window to be loaded (as though you had typed it all into the interpreter), and also runs all unit tests. So, in the example above, after writing the square function in the top half of the window, along with tests that verify its correctness, I clicked the Run button, and was told that all tests had passed, and was subsequently able to call the square function in the interpreter. Any output that's generated by any expressions will be printed each time you say Run. (Don't forget to save your file periodically, so that you don't accidentally lose your work.)
The project
Below is the set of Racket functions that you are required to write for this project.
In general, you are not permitted to make assumptions about the arguments to each function other than the assumptions listed in the description of each function. For example, unless explicitly stated, you may not assume that all lists will be simple (a simple list is one with no sublists).
Along with each function, you are required to write unit tests as we described in lecture, using Racket's built-in testing functions.
The tools at your disposal
Be sure that your code works in DrRacket with the Advanced Student language level selected; that's how we'll be grading your work. Beyond that, we're also staying within an even more restricted subset of Racket. You may only use the following predefined Racket functions or constructs in your solution:
define lambda cond else empty empty? first rest cons list
list? = equal? and or not + - * / < <= > >=
You may also use these predefined test functions when unit testing your solutions:
check-expect check-within check-error
(You may not need everything listed above, but those are the only ones that you're eligible to use.) If you'd like to use any other predefined functions, you'll need to write them yourself, in terms of what's listed above.
Decomposing problems into smaller ones
Some of the functions below cannot be written easily without other "helper" functions. Turn in all of your helper functions along with the ones you are to write. You may reuse helper functions in more than one of your solutions if you'd like, though it isn't required. Similarly, you may call your solution to one of your functions in your solution to another.
A word about notation
The Advanced Student language level in DrRacket provides two equivalent ways of describing a list: using the list construct or a short-hand version consisting only of the lists elements surrounded by parentheses. For example, a list containing the numbers 1, 2, 3, 4, and 5 can be written in one of two ways:
(list 1 2 3 4 5)
'(1 2 3 4 5)
These two notations can be a little confusing, because they sometimes require quoting in different places. For example, a list of symbols x, y, and z would look like this in each of the supported styles:
(list 'x 'y 'z)
'(x y z)
For your work, either of these styles is fine when writing your functions. When using the Advanced Student language level, as we will be in this project, the list construct is used to describe lists returned as output.
The functions
Here are the eleven functions you're being asked to write. Each includes a brief set of examples that shows what its output should be in a few cases; note that these examples are not intended to be a complete set of tests for each function, so you may want to develop a few extra examples. (Remember to pay special attention to the base case for each function, which is not always listed in the examples, but whose answer you should be able to deduce from the description of the problem.)
(fourth-element L)
The fourth-element function takes a list L and returns its fourth element. Of course, not all lists have four or more elements; if L is a list that doesn't, the empty list should be returned. L is not necessarily simple, but you shouldn't handle sublists differently from other elements (i.e., if the fourth element is a sublist, return the whole sublist).
Examples:
(fourth-element (list 'a 'b 'c 'd 'e)) => d
(fourth-element (list 'x (list 'y 'z) 'w 'h 'j)) => h
(fourth-element (list (list 'a 'b) (list 'c 'd) (list 'e 'f) (list 'g 'h) (list 'i 'j)) => (list 'g 'h)
(fourth-element (list 'a 'b 'c)) => empty
(list-length L)
The list-length function takes a list L and returns the number of elements in the list.
Examples:
(list-length (list 'a 'b 'c)) => 3
(list-length (list 'a (list 'b 'c) 'd 'e 'f)) => 5
(count-matches S L)
The count-matches function takes a symbol S and a simple list L of symbols and returns the number of times that S occurs in L.
Examples:
(count-matches 'f (list 'a 'b 'c 'd 'e 'f 'g)) => 1
(count-matches 'b (list 'a 'b 'a 'b 'a 'b 'a)) => 3
(count-matches 'x (list 'a 'b 'c)) => 0
(my-append L1 L2)
The my-append function takes two lists, L1 and L2, and returns the concatenation of L1 and L2. ("Concatenation" means to stick one on the end of the other.) Note that concatenation is not the same thing as what "cons" does to two lists.
Examples:
(my-append (list 'a 'b) (list 'c 'd)) => (list 'a 'b 'c 'd)
(my-append empty (list 'a 'b)) => (list 'a 'b)
(my-append (list 'a 'b) empty) => (list 'a 'b)
(is-increasing? L)
The is-increasing? function takes a simple list L of numbers and returns true if the numbers in the list are increasing as you read them from beginning to end, and false if they aren't. We'll define "increasing" according to the mathemtical definition of the word, where the numbers are increasing so long as they never decrease. (This is as opposed to what you might call "strictly increasing," where every number has to be bigger than the previous one.) As special cases, we'll consider one-element and empty lists to be increasing.
Examples:
(is-increasing? (list 1 2 3)) => true
(is-increasing? (list 3 2 1)) => false
(is-increasing? (list 1 2 2 3 4 4 5)) => true
(is-increasing? (list 1)) => true
(is-increasing? empty) => true
(remove-duplicates L)
The remove-duplicates function takes a simple list L and returns a new list with all of the duplicate objects in L removed.
Examples:
(remove-duplicates (list 1 2 3)) => (list 1 2 3)
(remove-duplicates (list 1 2 1 4)) => (list 2 1 4) -or- (list 1 2 4)
(remove-duplicates (list 3 3 3 3 3)) => (list 3)
(calc-running-sums L)
The calc-running-sums function takes a simple list L of numbers and returns a list containing the running sums from L. The nth element in the returned list is the sum of the first n elements in L.
Examples:
(calc-running-sums (list 1)) => (list 1)
(calc-running-sums (list 2 2 2 2 2)) => (list 2 4 6 8 10)
(calc-running-sums (list 2 5 8)) => (list 2 7 15)
(recursive-sum L)
The recursive-sum function takes a list L of numbers and returns the sum of all the numbers in the list. L may have sublists, but all of the atoms in the list will be numbers. The sum of an empty list is 0.
Examples:
(recursive-sum empty) => 0
(recursive-sum (list 1 2 3)) => 6
(recursive-sum (list 1 1 1 1)) => 4
(recursive-sum (list 1 (list 2 3) 4)) => 10
(calc-depth L)
The calc-depth function takes a list L and returns its depth. The depth of a list is defined as the maximum level of "nesting" of a list. A list with no sublists has a depth of 1; a list with sublists that don't have sublists has a depth of 2; a list with sublists that have sublists that don't have sublists has a depth of 3; and so on.
Examples:
(calc-depth (list 1 2 3)) => 1
(calc-depth (list 1 (list 2) 3)) => 2
(calc-depth (list 1 (list 2 (list 3) 4) 5)) => 3
(calc-depth (list 1 (list 2) 3 (list 4 (list 5)))) => 3
(deep-reverse L)
The deep-reverse function takes a list L and returns the deep reversal of L. The deep reversal of L is a list R that contains all of the elements of L in reverse order. Further, for each element L' in L that is a list, the corresponding element in R is the deep reversal of L'.
Examples:
(deep-reverse (list 'a 'b 'c)) => (list 'c 'b 'a)
(deep-reverse (list (list 'a 'b 'c) 'd (list (list 'e 'f) 'g))) => (list (list 'g (list 'f 'e)) 'd (list 'c 'b 'a))
(filter-items F L)
The filter-items function takes a function F (which takes one argument and returns a boolean result) and a list L. The job of filter-items is to call F on each of the elements of L, returning a list of all the elements in L for which F returned true, while leaving out all the elements in L for which F returned false. This is a pretty powerful function that can solve a wide variety of problems. (In general, we say that higher-order functions are those that take other functions as arguments. Why they're called "higher-order," and why they're so powerful, is because you can send an arbitrary function to configure them, so that they can solve problems that you haven't even conceived of yet.)
The examples below make use of a few predefined Racket functions, to show how versatile filter-items will be when you're done with it. Feel free to use these functions in your tests for filter-items, even though they're not on the list of functions you can use in your solutions:
- positive?, which returns true if its argument is a positive number and false if not
- odd?, which returns true if its argument is an odd number and false if not
- string-length, which takes a string as an argument and returns the number of characters in the string
Examples:
(filter-items positive? (list 1 -3 2 -4 3 -5 4 -6)) => (list 1 2 3 4)
(filter-items odd? (list 1 2 3 4 5 6)) => (list 1 3 5)
(filter-items is-increasing? (list (list 1 4) (list 4 3 2) (list 5 6)) => (list (list 1 4) (list 5 6))
(filter-items (lambda (s)
(<= (string-length s) 4))
(list "Alex" "is" "happy" "today")) => (list "Alex" "is")
The last example is interesting, too. A lambda expression builds and returns a function. You don't have to give that function a name in order to use it, though we often do. In this case, we're saying "Call filter-items, passing it a newly-built function that takes a string and returns true if its length is no more than 4, along with a list of some strings." We expect to get back a list of all the strings in the original list whose lengths are no more than 4.
Grading
This project will be graded on a 33-point scale, unlike the previous projects have been. (Please note, though, that this project will not weigh differently on your final grade than the others; your score on this project will be scaled proportionally to match the others.) The 33 points will be broken down differently than the points available in the other projects. Each of the eleven Racket functions will be worth three points and will be scored according to the following rubric:
- 2 points for Correctness and quality of solution:
- To earn a 2, the function must return the correct value (as specified) in all cases. We may test your functions on cases other than the examples listed, so make sure that you test your functions thoroughly.
- To earn a 1, the function must be correct in some but not all cases. The function's code must also constitute an attempt to actually solve the problem given. To be clearer about this, the following two situations will yield a score of 0:
- Your function works only on the base case (e.g., the empty list).
- Your function "accidentally" works on one of the cases, but doesn't constitute an attempted solution to the problem given (e.g., if your recursive-sum function always returns 3, and that happens to be the answer for one of our test cases).
- 1 point for Testing, which means that you used DrRacket's built-in test functions like check-expect to demonstrate that your function works in a variety of cases. To get 1 point, you must include interesting cases other than the ones listed in the project write-up.
- Note that Racket is a much deeper, much more full-featured programming language than we've considered in class. (For example, there are predefined functions in Racket that solve some of the problems that I've assigned you.) Still, because we're interested in learning how to solve problems in a particular way, we're sticking with only a small subset of Racket. You are forbidden from using predefined Racket functions or constructs that are not on the list of accepted functions and constructs listed at the top of this project write-up. Any of your functions that uses anything forbidden will receive 0 points. (If you're not sure if one of your solutions breaks this rule, please ask us ahead of time; this is not intended to be a "gotcha," but it is intended to force you to attack your problems in a certain way.)
Style and other issues will be de-emphasized, since we have not spent time discussing these issues with respect to Racket.
Deliverables
Put all of your solutions into a single file called project6.rkt. Submit this file and no others. We must be able to read this file directly into the DrRacket environment to test it, so don't write the procedures in Microsoft Word or another format.
Please include a comment at the top of the file that lists the names and student IDs of both you and your partner. Comments in Racket begin with a semicolon character — though, by convention, we often use two of them in a row, so they're easier to see. Everything that follows a semicolon on any line is ignored by the Racket interpreter.
Follow this link for a discussion of how to submit your project.
Additional challenge
For those of you who are interested in further understanding how functional programming is different from the object-oriented programming you're accustomed to — particularly, how giving up variables changes how we approach problems, but doesn't make them impossible to approach — consider the problem of implementing a queue in Racket, using the tools we know about thus far.
A first attempt: queue as list
One approach would be to implement a queue as a list, with the following functions:
- make-queue, which takes no parameters and returns an empty queue (in this case, an empty list).
- queue-enqueue, which takes a queue and a new element and returns a queue with the new element added to the back (in this case, added to the end of the list).
- queue-dequeue, which takes a queue and returns a queue with the front element removed (in this case, the first list element is removed).
- queue-front, which takes a queue and returns the element at the front (in this case, the first list element).
- queue-empty?, which takes a queue and returns true if it's empty and false if not (in this case, we can check if the list is empty).
Once you had these functions, you'd no longer need to know how you implemented the queue; they collectively play the same role as an interface in Java, hiding the details of the queue's implementation. (Implemted this way in Racket, the details aren't quite hidden, but you can safely ignore them, while using only these five functions to manipulate a queue.)
Try implementing these functions, then read on.
Analysis of our first attempt
Okay, now that you've implemented the functions, consider the O-notation for them, understanding that lists in Racket behave essentially like singly-linked lists with head references.
- make-queue is O(1), because all it does is return an empty list
- queue-enqueue is O(n), because adding to the end of a list takes linear time
- queue-dequeue is O(1), because removing the first element of a list takes constant time
- queue-front is O(1), because accessing the first element of a list takes constant times
- queue-empty? is O(1), because checking if a list is empty only requires checking the head reference, which can be done in constant time
A better approach: using two lists instead
The issue that's keeping our first approach from being efficient enough for many purposes is that, in Racket, lists are the equivalent of singly-linked lists with head references. Accessing the end of these lists — which we need to be able to do when we enqueue elements — is expensive. Unlike in Java, though, we can't just add a tail reference in functional Racket. There is, however, a clever approach that is O(1) on the average (over the long haul). The analysis is a bit deep — it uses a technique called amortized analysis, which you'll learn more about in ICS 23 / CSE 23 — but I can give you the rough idea here.
Instead of using just one list, our queues will be made up of two lists:
- A list of the first i elements in the queue, beginning with the front element and continuing forward.
- A list of the last j elements in the queue, beginning with the last element and continuing backward.
We can implement a queue, then, as a list containing two lists. For example, the implementation-level view of a queue containing the elements a, b, c, d, e, f might be any of these (or one a few other possibilities):
(list (list 'a 'b 'c) (list 'f 'e 'd))
(list (list 'a) (list 'f 'e 'd 'b 'c))
(list (list 'a 'b 'c 'd 'e) (list 'f))
Now, what's the point of splitting the queue into two lists like this? Think about how each function could be implemented now:
- make-queue returns a list of two empty lists.
- queue-enqueue takes a queue and a new element and returns a new queue with the following properties:
- The first list is unchanged
- The second list has the new element added to the front.
- queue-dequeue takes a queue and returns a new queue with the front element removed. There are two possibilities:
- If the first list has elements in it, the first element in the first list is removed and the second list is unchanged.
- If the first list is empty, make the first list be the reverse of the original second list (with the first element removed) and make the second list be empty.
- queue-front takes a queue and returns the front element. There are two possibilities:
- If the first list has elements in it, the first element of the first list is removed.
- If the first list is empty, return the last item from the second list.
- queue-empty? takes a queue and returns true if both of its lists are empty, false otherwise.
Try writing these functions, then read on.
A brief analysis of our second approach
Let's consider again the O-notation of each operation.
- make-queue is O(1), because two empty lists can be created in constant time.
- queue-enqueue is O(1), because we can add an element to the front of the second list in constant time.
- queue-dequeue is O(n) in the worst case, because it requires reversing the second list. The trick here, though, is that it won't happen very often. And the longer it takes to do — the longer the second list is — the longer it will be before we have to do it again, because we'll have a longer first list when we're done. On the average, over the long haul, the average time spent performing a dequeue will be a constant. (This analysis is similar to why the add() method that adds an element to the end of an ArrayList takes constant time on the average, even though it sometimes takes longer.)
- queue-front is O(n) in the worst case, but this only occurs when the first list is empty. Assuming that we don't ask for the front element any more often than we dequeue an element, the expensive calls to queue-front won't happen very often, and will happen decreasingly often the more expensive they are. (If you're going to need to call queue-front many times between queue-dequeues, there are ways to mitigate this problem.)
- queue-empty? is O(1), because it takes constant time to check if two lists are empty.
On the face of it, this analysis seems worse than what we started with — there are now two operations that can take linear time, while we had only one such operation before. The difference here is that, in our first attempt, every call to queue-enqueue takes linear time; in our second attempt, only occasional calls to queue-dequeue or queue-front are linear, and the rest are constant. So this really does turn out to be a truly better approach.
- A variety of small updates by Alex Thornton, Winter 2012.
- Some additional information and a testing requirement was added by Alex Thornton, Fall 2008
- Originally written by Alex Thornton (with a fair amount of influence from "Basic Instructions," by Alex Thornton), Winter 2007