Homework 1: Core Ideas

Due: Friday, September 20 at 23:59
First Commit: Monday, September 16 at 23:59

In this assignment you will continue your exploration of core Racket topics and you’ll be introduced to some new ways to think about Racket code.

The goals for this assignment are increasing your skills with:

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.

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 hw1 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. (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 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

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.

In Scope Operations

While we are learning about higher order functions this week, this assignment is not about higher order methods. You are discouraged from using them throughout. apply in particular is not allowed – work on practicing your “recursion only” skills!

Part 1: More Recognizers

This part of the assignment carries on our exploration of functions which return Boolean output from Homework 0.

1. (10 points) Compare the procedures all-atoms? and all-ints? that you wrote in Homework 0. The structures of these procedures should look very similar. Write a procedure all-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, (all-same? atom? lst) should behave the same as (all-atoms? lst) and (all-same? integer? lst) should be the same as (all-ints? lst).

Write at least three tests. Try using different predicates. Examples include number?, list?, (lambda (x) (> x 3)). Make sure to test cases that return #t and cases that return #f.

2. (10 points) Write a procedure make-all-same that only takes one argument, a predicate, and returns a procedure. The returned procedure 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-all-same atom?) is the same as all-atoms? and (make-all-same integer?) is the same as all-ints?.

This process of taking a procedure of two arguments, all-same?, and rewriting it as a procedure of one argument that returns another procedure of one argument is called currying the original procedure. This is a core tool for your functional programming toolbox!

Write at least three tests. How can you test it? Well,

((make-all-same integer?) '(25 'foo 18))

is #f, for example. Make sure to test cases that return #t and cases that return #f.

Part 2. Operations on lists

For each of the following problems, write the procedure and a test suite containing at least three tests and add the test suite to the all-tests test suite. You might want to try writing the tests first! Make sure to test your procedures under a variety of conditions like passing an empty list or a list of one element.

3. (10 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

4. (10 points) Write (delete-second x lst) which removes the second occurrence of x from lst, if there is one. Use equal? to perform the comparison. Note that remove is a Racket built-in method.

Write at least three tests for delete-second in tests.rkt.

5. (15 points) Specifying 'x over and over again in the examples above seems non-optimal! Currying allows us to define a procedure (delete-second-x lst) as follows:

(define (delete-second-x lst)
    ((curry-delete-second 'x) lst))

Then we can have “nicer” calls such as the following (delete-second-x '(a b x c x d)), which still returns '(a b x c d).

Write the general curry-delete-second procedure by adapting your delete-second implementation (the majority of the procedure should stay same!). Then define delete-second-x as above and add at least three tests for delete-second-x to tests.rkt.

6. (10 points) Write (delete-pair x lst) which removes every occurrence of two consecutive instances of x in lst.

Write at least three tests, as with previous problems.

7. (10 points) Write (copy n exp) which builds a list containing n copies of object exp.

  - (copy 3 'x) returns '(x x x)
  - (copy 0 'y) returns '()
  - (copy 3 '(a b c)) returns '((a b c) (a b c) (a b c))

8. (10 points) Write (max-value lst) where lst is a nonempty list of numbers. It should return the maximum value in lst. Write at least three tests, as with previous problems.

Common Questions

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.

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