Homework 1: The Basics

In this assignment you will create programs which put to use some of the week’s topics. You’ll also be introduced to some useful new ways of thinking about Scheme code. By the end of the assignment, you should be comfortable with

• The DrRacket interpreter
• Writing Racket functions
• Using recursion with lists
• Writing tests for Racket functions

Your implementations of the following functions should all be placed in a single Racket file named hw1.rkt. The corresponding tests for each function should be in a second Racket file named tests.rkt.

The start of each file should be

#lang racket
; Your name(s) here.

Preliminaries

First, download and install Racket. Select the Racket (not Minimal Racket) distribution for your platform (almost certainly the 64-bit version for your operating system) and select the Regular variant.

If you don’t already have a GitHub account, make one. (As a student, you can get additional GitHub benefits such as unlimited private repositories here, but you don’t need to for this course. All of your repositories will be private to you, your partner (if you have one), and course instructors.)

You’ll need Git installed in order to download and submit assignments. On macOS, Git is included with Xcode which can be installed from the App Store. On Linux, Git can be installed using your distribution’s package manager. You can install any of the many other Git tools instead, including GitHub Desktop on macOS and Windows.

Click on the assignment link. If you’re working with a partner, one partner should create a new team. The second partner should click the link and choose the appropriate team. (Please don’t choose the wrong team, there’s a maximum of two people and if you join the wrong one, you’ll prevent the correct person from joining.)

Once you have accepted the assignment and created/joined a team, you can clone the repository on your computer by following the instruction and begin working. But before you do, read the entire assignment and be sure to check out the expected coding style.

Be sure to ask any questions on Piazza.

Coding style

For all of the Racket code you write, you should follow the standard conventions. In particular,

1. You should let DrRacket indent your code. You can re-indent a line of code at any time by pressing tab. The Racket menu contains a Reindent All item which you can use to reindent the entire file.
2. Closing parentheses and brackets should not appear on lines by themselves (as you might do with } in C or Java). For example, a function to compute the arithmetic mean of two numbers might be written as

   (define (mean x y)
     (/ (+ x y) 2))
   

   or

   (define (mean x y)
     (/ (+ x y)
        2))
   

   but not as

   (define (mean x y)
     (/ (+ x y)
        2
     )
   )
   

Submission

To submit your homework, you must commit and push to GitHub before the deadline.

Your repository should contain the following files

• hw1.rkt
• tests.rkt

It may also a .gitignore file which tells Git to ignore files matching patterns in your working directory.

Any additional files you have added to your repository should be removed from the master branch. (You’re free to make other branches, if you desire, but make sure master contains the version of the code you want graded.)

Make sure you put your name (and your partner’s name if you’re working with one) as a comment at the top of each file.

Part 1. List of Atoms

1. (8 points) Some versions of Scheme have a primitive function atom? that returns #t if its argument is an atom and #f if it isn’t; this isn’t built into Racket. Since Racket has primitive functions pair? and null? that returns #t if their argument is a a cons pair (such as a nonempty list) or null, respectively, we can easily write atom?. Every expression is an atom, a pair, or null. Use this to define function atom? in hw1.rkt. Here is some test data:
   • (atom? 3) returns #t
   • (atom? #f) returns #t
   • (atom? '(1 2)) returns #f
   • (atom? null) returns #f
   • (atom? (cons 5 10)) returns #f

   Now, it’s time to write tests to make sure your atom? works correctly. Look in tests.rkt for example tests. For each function, we define a test suite (using define as normal)

   (test-suite name test...)
   

   where name is the name of the test suite and it’s followed by any number of tests.

   We can create a test which tests whether an expression returns #t or #f using test-true or test-false.

   • (test-true test-name exp)
   • (test-false test-name exp)

   At the bottom of tests.rkt, there’s a definition for an all-tests test suite which, when we’re finished will consist of all of the test suites for the functions you’re writing. And finally (run-tests all-tests). After you’ve written the tests, click the Run button and you should see a message telling you all your tests have passed or that some have failed.

   2 success(es) 1 failure(s) 0 error(s) 3 test(s) run
   

2. (8 points) Write a function list-of-atom? that takes an argument and returns #t if the argument is either an empty list or a list where every element is an atom.

   Define a new test suite to test list-of-atom? in tests.rkt.

   (define list-of-atom?-tests
     (test-suite
      "list-of-atoms?"
      (test-true "Empty list"
                 (list-of-atom? empty))))
   

   Add more tests to this test suite. Try to think of all the possible edge cases (e.g., empty lists and lists containing a single element). Make sure to test both positive and negative instances.

   Add your new test suite to the all-tests test suite.

   (define all-tests
     (test-suite
      "All tests"
      atom?-tests
      list-of-atom?-tests))
   

   Click the Run button to make sure all your tests pass. After running the tests, you can run (test/gui all-tests) in the interpreter to get a graphical version of the output. Give this a try. I found it helpful when I had many failing tests.

3. (8 points) Write a function not-list-of-atom? that returns #t if its argument is not a list of atoms. Of course, you could write this as

   (define (not-list-of-atom? lst)
     (not (list-of-atom? lst)))
   

   but don’t do that. Instead, write it directly using cond.

   Define a new test suite not-list-of-atom?-tests with appropriate tests. Make sure to add that test suite to all-tests.

4. (8 points) Write the function list-of-int? that returns #t if its argument is the empty list or if it’s a list where every element is an integer. You can use integer? to test if something is an integer. Write appropriate tests.

5. (8 points) Compare functions list-of-atom? and list-of-int?. The structures of these functions should look very similar. Write a function list-of-same? that takes two arguments: a predicate (like atom? or integer? or list?) and a list and returns #t if the list is empty or if every element in it satisfies the predicate.

   For example, (list-of-same? atom? lst) should behave the same as (list-of-atom? lst) and (list-of-same? integer? lst) should be the same as (list-of-int? lst).

   Write tests.

6. (9 points) Write a function make-list-of-same that only takes one argument, a predicate, and returns a function. The returned function must take an argument and return #t if its argument is the empty list or a list for which the predicate returns #t on every element in the list.

   Thus, (make-list-of-same atom?) is the same as list-of-atom? and (make-list-of-same integer?) is the same as list-of-integer?.

   (This process of taking a function of two arguments, list-of-same?, and rewriting it as a function of one argument that returns another function of one argument is called currying the original function. It’s named after Haskell Curry, an American mathematician who worked on the foundations of logic and programming languages.)

   Write tests.

Congratulations, you’ve completed the first part! If you haven’t already done so recently, now would be a great time to commit all of your code and push it to GitHub. Recall that you need to first add the files, commit them, and then push.

$ git add hw1.rkt tests.rkt
$ git commit
$ git push

Part 2. Operations on lists.

For each function, write the function and a test suite and add the test suite to the all-tests test suite. You might want to write the tests first.

7. (9 points) Write (all-members lst1 lst2) which returns #t if every member of lst1 is also a member of lst2 and #f otherwise. Use equal? to perform the comparison.
   • (all-members '(a c x) '(a b x c x d)) returns #t
   • (all-members '(a c x) '(a b c)) returns #f
   • (all-members '(a) empty) returns #f
   • (all-members empty empty) returns #t
8. (9 points) Write (remove-second x lst) which removes the second occurrence of x from lst, if there is one. Use equal? to perform the comparison.
   • (remove-second 'x '(a b x c x d)) returns '(a b x c d)
   • (remove-second 'x '(a b x c x d x e)) returns '(a b x c d x e)
   • (remove-second 'x '(a b x c) )) returns '(a b x c)

   To write tests for functions which don’t return #t or #f, use

   (test-equal? name actual expected)
   

   which defines a test with the given name which passes if actual is equal? to expected. For example, you might have the tests

   (test-equal? "Empty list"
                (remove-second 'x empty)
                empty)
   (test-equal? "Singleton, matching"
                (remove-second 'x '(x))
                '(x))
   

9. (9 points) Write (remove-pair x lst) which removes every occurrence of two consecutive instances of x in lst.
   • (remove-pair 'a '(a a b b c c a b c a a)) returns '(b b c c a b c)
   • (remove-pair 'a '(a b c a b c a)) returns '(a b c a b c a)
   • (remove-pair 'b (a b b b a)) returns '(a b a)
   • (remove-pair 'b (a b b b b a )) returns '(a a)
10. (8 points) Write (duplicate n exp) which builds a list containing n copies of object exp.
    • (duplicate 3 'x) returns '(x x x)
    • (duplicate 0 'y) returns empty
    • (duplicate 3 '(a b c)) returns ((a b c) (a b c) (a b c))
11. (8 points) Write (maximum lst) where lst is a nonempty list of numbers. It should return the largest value in lst.
    • (largest '(4 6 3 4 5 1 2)) returns 6
12. (8 points) Write (index-of lst x) which returns the 0-based index of the first occurrence of x in lst (use equal? to compare elements). If x is not in the list, return #f. (Notice that in this function, the list is the first parameter. That’s because this is a standard list function. Of course, here, you are writing the implementation (and tests).
    • (index-of '(x y z z y) 'x) returns 0
    • (index-of '(x y z z y) 'y) returns 1
    • (index-of '(x y z z y) 'a) returns #f
    • (index-of empty 'x) returns #f

Finishing up

Make sure you wrote tests of all of these, the test suite for each function is included in the all-tests test suite, and your tests pass. For reference, my solution involves 66 tests in total and when I run (test/gui all-tests), I get this.

Once you have finished (or better yet, frequently as you’re working), you need to push your code to GitHub since this is what we’ll use for grading. So double check that you’ve included your name and the name of your partner (if you’re working with a partner) in both files and git add/commit/push.

$ git add hw1.rkt tests.rkt
$ git commit
$ git push