Homework 2: Lists and Recursion

The goals for this assignment are increasing your skills with

• Writing Racket functions
• Using recursion with flat lists
• Using lists to structure data

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

You may use the solution to any exercise as a helper function in subsequent exercises and you may also write stand-alone helper functions.

The start of each file should be

#lang racket
; Your name(s) here.

Preliminaries

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 from the previous homework.

Be sure to ask any questions on Piazza.

Submission

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

Your repository should contain the following files

• hw2.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. Lists as structures

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. If you’ve forgotten how to write tests, consult homework 1.

1. Write a function merge that merges two sorted lists of numbers onto one sorted list, the way merge sort works.
   • (merge '(1 4 5) '(2 3 4 6)) returns '(1 2 3 4 4 5 6) Make sure you write some additional tests beyond the two example tests in tests.rkt.
2. Write a sort function for lists of numbers. Don’t get the idea from (1) that you should do merge sort. Try insertion sort.
   • (sort '(5 1 8 3 7)) returns '(1 3 5 7 8)
3. Write the function (contains-sublist? sublist biglist) that determines if biglist contains a particular sublist.
   • (contains-sublist? '(2 3 4) '(1 2 3 4 5)) returns #t
   • (contains-sublist? '(2 3 4) '(1 2 5 3 4)) returns #f
4. Write the function (remove-sublist sublist biglist) that removes the first occurrence of the sublist from the biglist
   • (remove-sublist '(2 3 4) '(1 2 3 4 5)) returns '(1 5)
   • (remove-sublist '(2 3 4) '(1 2 5 3 4)) returns '(1 2 5 3 4)

If you haven’t already done so, 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 hw2.rkt tests.rkt
$ git commit
$ git push

Part 2. Association lists

Flat lists aren’t a very good way to store data. An obvious improvement is to have the list consist of elements, each of which is itself a list, representing the data for one individual. For example, we might make a phone-book as a list of name, phone number pairs. Such a structure is called an association list. For example,

(define phone-book
  '((barbara 775-1234)
    (luke 774-2839)
    (nick 775-0912)
    (valerie 775-9043)))

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. Racket has a standard library function assoc which is designed to work with association lists. For this assignment, do not use it in your implementations.

5. Write the function (phone-number person phone-book) that returns the phone number of the given person, or the symbol 'disconnected if there is no entry for the person.
   • With the phone book defined above (phone-number 'nick phone-book) returns '775-0912
6. Write the function (person phone-number phone-book) that returns the name of the person with the given phone number
   • So (person '775-0912 phone-book) returns 'nick

Part 3. Other structured 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. Write the function (deepen lst) that wraps a pair of parentheses around each top-level element in lst.
   • (deepen '(a b c)) returns '((a) (b) (c))
   • (deepen '(a (b (c d)) e)) returns '((a) ((b (c d))) (e))
8. Write function (eval-bin lst) that takes a flat list of 1s and 0s, and finds the base-10 value of the number represented by this vector.
   • (eval-bin '(1 0 1 1)) returns 11
   • (eval-bin '(1 1 0) returns 6 [Hint: if you read the digits from left to right, at each step you double the previous value and add the new digit. For example, with '(1 0 1 1) start with value 0. Double it and add 1 to get the value 1 for '(1). Double that and add 0 to get the value 2 for '(1 0). Double that and add 1 to get value 5 for '(1 0 1). Double that and add 1 to get 11 for '(1 0 1 1)]
9. Write the function (sub old new lst) that replaces each instance of old in lst with new.
   • (sub 'a 'x '(a b r a c a d a b r a)) returns '(x b r x c x d x b r x)
10. Write the function (subs old-lst new-lst lst) that takes a list of values to swap out, old-lst, and a list of values to replace them with, new-lst, and performs these changes on lst. You can assume that old-lst and new-lst have the same length.
    • (subs '(b) '(m) '(b o b)) returns '(m o m)
    • (subs '(b o) '(m u) '(b o b)) returns '(m u m)

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 39 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 hw2.rkt tests.rkt
$ git commit
$ git push