Homework 2: More on Lists

Due: Friday, September 27 at 23:59
First Commit: Monday, September 23 at 23:59

The goals for this assignment are increasing your skills with:

• Writing Racket functions
• Using recursion with flat lists

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 with a new name (hint: include hw2 in the name). The second partner should click the link and choose the appropriate team. It’s extremely helpful for the graders if you include your name and your partner’s name in the team name. Unfortunately, you cannot use the same team name for multiple assignments.

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 in Racket Fundamentals.

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
• HONORCODE.md

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 main branch. (You’re free to make other branches, if you desire, but make sure main 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.

When writing tests, make sure you test different conditions (think back to what made good basic tests for remove-numbers from class and length from HW0). When testing has-sublist? and delete-sublist? make sure you test the case where the sublist is in the biglist and when it isn’t. Each function should have at least three tests.

1. Write a function merge that merges two sorted lists of numbers into one sorted list.
   • (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. Do not do merge sort just because of question 1! Implementing insertion sort, or an approach where you find the min element in the unsorted part of the list and add it to the sorted part of the list, is a good idea. You are welcome to use the built-in min procedure in Racket for this problem.
   • (sort '(5 1 8 3 7)) returns '(1 3 5 7 8)
3. Write the function (has-sublist? sublist biglist) that determines if biglist contains a particular sublist.
   • (has-sublist? '(2 3 4) '(1 2 3 4 5)) returns #t
   • (has-sublist? '(2 3 4) '(1 2 5 3 4)) returns #f
4. Write the function (delete-sublist sublist biglist) that removes the first occurrence of the sublist from the biglist.
   • (delete-sublist '(2 3 4) '(1 2 3 4 5)) returns '(1 5)
   • (delete-sublist '(2 3 4) '(1 2 5 3 4)) returns '(1 2 5 3 4)
   • (delete-sublist '(x y z) '(e f x y a b x y z)) returns '(e f x y a b)

   When solving delete-sublist, it is highly recommended to (a) use helper functions and (b) consider checking whether a sequence in biglist is actually equal to sublist or simply a prefix of sublist (see the last test above). Also writing more than 3 tests is likely instructive. This is likely the hardest problem on the homework - come back to it and work on it incrementally!

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 HONORCODE.md
$ git commit
$ git push

Part 2. 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.

1. Write the function (nest lst) that wraps a pair of parentheses around each top-level element in lst.
   • (nest '(a b c)) returns '((a) (b) (c))
   • (nest '(a (b (c d)) e)) returns '((a) ((b (c d))) (e))
2. 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

   A reminder that typically in Racket we work from the left of the list to right. So in the case of parsing binary, if you read the digits from left to right, at each step you can double the previous value and add the new digit. For instance, (eval-bin '(1 1 0)) should return 6. You can 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).

3. Write the function (exchange old new lst) that replaces each instance of old in lst with new.
   • (exchange '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)
4. Write the function (all-exchange 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.
   • (all-exchange '(b) '(m) '(b o b)) returns '(m o m)
   • (all-exchange'(b o) '(m u) '(b o b)) returns '(m u m)

Common Questions

• Should we skip around the different parts if we find ourselves stuck on one question? Yes! The problems within parts can build on each other, but the parts are all separate. I would recommend keeping track of which problems you’ve complete though to make sure you don’t miss any.
• Do I need to use higher order functions here? Need, no! This is another assignment have us test out Racket. Homework 3 will ask us to use higher order methods directly.

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. A reminder you are expected to have at least 3 tests per problem, but more are just fine!

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 HONORCODE.md
$ git commit
$ git push