Assignment 1: Learning Racket

In all of the following questions, do not use any functions that end with ! (i.e. no modifying functions), and don’t use any loops (just recursion, or higher-order functions like map, filter, or fold).

Please put all your code for this assignment into a single Racket file named a1.rkt, and submit it online in Canvas when you’re ready.

Warm Up

Implement each of the following functions. You can assume that the input for each function is always the correct type, so you don’t need to do any extra error-checking.

The my- functions are similar to functions that are already in Racket — don’t use those functions in your implementation!

1. (my-length lst) returns the number of elements in a list, e.g.:

   > (my-length '())
   0
   > (my-length '(a 1 (2 7)))
   3
   

2. (onion n) returns a list with n copies of the empty list embedded in it, e.g.:

   > (onion 0)
   '()
   > (onion 1)
   '(())
   > (onion 2)
   '((()))
   > (onion 3)
   '(((())))
   > (onion 10)
   '((((((((((()))))))))))
   

   If n is less than 0, then call error with a helpful message, e.g.:

   > (onion -2)
   . . onion: n negative
   

3. (my-last lst) returns the last element of a list, e.g.:

   > (my-last '(a b c d))
   'd
   

   If lst is empty, then call the error function with a helpful error message, e.g.:

   > (my-last '())
   . . my-last: empty list
   

4. (double-up lst) returns a new list that contains all the elements on lst repeat, e.g.:

   > (double-up '(a 2 (c d)))
   '(a a 2 2 (c d) (c d))
   

5. (swap-ends lst) returns a new list that is the same as lst, except the first element and last element have been swapped. All the other elements are the same. For example:

   > (swap-ends '(a b))
   '(b a)
   > (swap-ends '(a b c))
   '(c b a)
   > (swap-ends '(a b c d))
   '(d b c a)
   

6. (softmax lst) returns a new list that is the standard (unit) softmax of lst. Assume lst is a non-empty list of numbers (which can be positive, negative, or 0). The numbers in the list returned by (softmax lst) are all in the range [0,1], and sum to 1.

   For example:

   > (softmax '(-1 2 3))
   '(0.013212886953789414 0.26538792877224193 0.7213991842739685)
   > (softmax '(8 7 -2))
   '(0.7310343155951328 0.26893249549828524 3.318890658198522e-005)
   

   Note that exp is a standard Racket function.

7. (is-relation? lst) returns #t if, and only if, lst is a non-empty list of lists of the form (a b), where both a and b are integers. None of the pairs should be repeated.

   For example:

   > (is-relation? '((2 4)))
   #t
   > (is-relation? '((6 2) (8 1) (2 2) (1 8)))
   #t
   
   > (is-relation? '((2 4) (1 5) (2 4)))
   #f
   > (is-relation? '((6.1 1) (1 5)))
   #f
   > (is-relation? '((6 1) (1 2 5)))
   #f
   > (is-relation? '())
   #f
   > (is-relation? "a, b")
   #f
   

8. (is-function? lst) returns #t if, and only if, lst is a relation, and all of its first elements are unique and all of its second elements are unique.

   For example:

   > (is-function? '((2 4) (3 1) (1 8) (6 2)))
   #t
   > (is-function? '((2 4) (1 5) (2 5)))
   #f
   > (is-function? '((2 4) (3 1) (2 8)))
   #f
   > (is-function? 'cat)
   #f
   

Atom Counting

An atom is either a number or a symbol. Write the following Racket functions:

1. (atom? x) returns #t if x is an atom, and #f otherwise. For example:

   > (atom? 3)
   #t
   > (atom? 'cat)
   #t
   > (atom? "house")
   #f
   > (atom? '(a b))
   #f
   

2. (count-atoms1 lst) returns the number of atoms in the lst, not counting atoms that are in sub-lists. For example:

   > (count-atoms1 '())
   0
   > (count-atoms1 '(a 2 (c d) "a" 4))
   3
   > (count-atoms1 '(a 2 b c 3))
   5
   > (count-atoms1 '((a) 2 "b" c 3))
   

   Implement count-atoms1 using basic recursion (and no higher-order functions, such as map, fold, or filter).

3. Re-do question 2 above, but this time call the function count-atoms2 and don’t use recursion. Instead, implement using only higher-order functions, such as map, fold, or filter

4. Write a function called (check f suite) to help test if count-atoms1 and count-atoms2 are correct. Here, f is an atom counting function (i.e. count-atoms1 or count-atoms2), and suite is a list of (input expected-output) tests cases, e.g.:

   (define test-suite
     '((() 0)
       ((a) 1)
       ((2) 1)
       (("a") 0)
       ((a b) 2)
       ((3 1) 2)
       ((a 2) 2)
       (("a" b) 1)
       ((1 2 3 4) 4)
       ((a b c d) 4)
       ((1 a 2 3 b c) 6)
       ((1 a () 2 3 "m" b c (4 s 2)) 6)))
   

   If f passes all the tests in suite, then (check f suite) returns the string "all tests passed". Otherwise, if any tests fail, it returns a list of strings, where each string is a nicely formatted message that describes which test case failed.

   For example, suppose count-atoms1 is correctly implemented. Then:

   > (check count-atoms1 test-suite)
   "all tests passed"
   

   Suppose count-atoms-bad is an incorrectly implemented atom counting function. It’s output should look something like this:

   > (check count-atoms-bad test-suite)
   '("fail: (f '(a)) returned 0; expected 1"
     "fail: (f '(2)) returned 0; expected 1"
     "fail: (f '(a)) returned 1; expected 0"
     "fail: (f '(a b)) returned 1; expected 2"
     "fail: (f '(3 1)) returned 1; expected 2"
     "fail: (f '(a 2)) returned 1; expected 2"
     "fail: (f '(a b)) returned 2; expected 1"
     "fail: (f '(1 2 3 4)) returned 3; expected 4"
     "fail: (f '(a b c d)) returned 3; expected 4"
     "fail: (f '(1 a 2 3 b c)) returned 5; expected 6"
     "fail: (f '(1 a () 2 3 m b c (4 s 2))) returned 5; expected 6")
   

   Of course, the actual strings that get printed will depend upon the particular errors in count-atoms-bad, so these results aren’t unique.

   Note that all failed test cases are included, and that the strings are formatted in a way that is easy for a human to understand.

   When check is done, make sure to use it to actually test count-atoms1 and count-atoms2.

   Hint: the format function is a good way to make formatted strings.