Homework 3: Structured Lists

The goal for this assignment is to practice using map and apply.

Use map and apply wherever you can to implement the functions. If you can’t see how to use map or apply, I’ll accept other ways of implementing the functions, but do make an effort to use the higher-order functions.

Your implementations of the following functions should all be placed in a single Racket file named hw3.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 first 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

• hw3.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. Vectors and matrices as 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. If you’ve forgotten how to write tests, consult homework 1.

Try to use map and/or apply for each of your solutions. (The procedures are each very short when you do.)

1. Write (firsts lsts) and (rests lsts). For both of these, lsts is a list of lists. (firsts lsts) returns a new list with the first element (the first of each list) of each element of lsts. (rests lsts) returns a new list with the remainder of each list (the rest of each list).
   • (firsts '((a b c) (d e f) (g h i))) returns '(a d g)
   • (rests '((a b c) (d e f) (g h i))) returns '((b c) (e f) (h i))
2. Write (vec-+ vec1 vec2) where vec1 and vec2 are vectors (lists of numbers) with the same length. This returns the vector containing the sums of the corresponding elements of vec1 and vec2.
   • (vec-+ '(1 2 3) '(4 5 6)) returns '(5 7 9)
   • (vec-+ empty empty) returns empty
3. Write (dot-product vec1 vec2) where vec1 and vec2 are again vectors with the same length. This returns the dot product of the two vectors. That is, it’s the sum of product of corresponding elements in the two vectors.
   • (dot-product '(1 2 3) '(4 5 6)) returns 32 (which is $1\cdot4+2\cdot 5+3\cdot6$)
   • (dot-product empty empty) returns 0
4. We can represent a matrix by a list of vectors where each vector has the same length and represents one row of the matrix. For example

   '((1 4 7)
     (2 5 8)
     (3 6 9))
   

   represents the matrix $\begin{pmatrix} 1 & 4 & 7\\ 2 & 5 & 8\\ 3 & 6 & 9 \end{pmatrix}.$

   Write (mat-vec-* mat vec) where the length of vec is the same as the length of each row of mat. This returns a vector containing the dot product of vec with each row of mat.

   • (mat-vec-* '((1 4 7) (2 5 8) (3 6 9)) '(1 2 3)) returns '(30 36 42)
   • (mat-vec-* '((2 3 4) (1 1 1)) '(1 0 1)) returns '(6 2)

5. The transpose of a matrix interchanges its rows and columns. I.e., the first row of the matrix is the first column of the transpose, the second row of the matrix is the second column of the transpose and so forth. For example, the transpose of $\begin{pmatrix} 1 & 3 & 5 \\ 2 & 4 & 6 \end{pmatrix}$ is $\begin{pmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{pmatrix}.$

   Write (transpose mat) which returns the transpose of the matrix mat. [Hint: Either use firsts and rests from question (1) or use map, apply, and list in a clever fashion. The clever solution is tricky, but running (map list '(1 2) '(3 4)) might give a clue.]

   • (transpose '((1 4 7) (2 5 8) (3 6 9))) returns '((1 2 3) (4 5 6) (7 8 9))
   • (transpose '((1 2 3) (4 5 6))) returns '((1 4) (2 5) (3 6))

6. You have probably seen matrix multiplication before. The entry of the $i$th row and $j$th column of the product is the dot product of the $i$th row of the first matrix and the $j$th column of the second matrix. For this to make sense, the lengths of the rows of the first matrix must be the same as the lengths of the columns of the second. For example, $\begin{pmatrix} 1 & 0 & 1\\ 2 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \\ 1 & 0 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} 2 & 3 \\ 4 & 5 \end{pmatrix}$

   Write (mat-mat-* lhs rhs) that returns the product of matrices $\mathit{lhs}\cdot\mathit{rhs}$. [Hint: You may wish to use a helper function that works with lhs and the transpose of rhs and use dot-product.]

   • (mat-mat-* '((1 0 1) (2 1 1)) '((1 2) (1 0) (1 1))) returns ((2 3) (4 5))

Part 2. Functions that operate on non-flat lists

As with Part 1, write tests for each of these functions in addition to implementing them.

7. Write (flatten lst) that takes a (not necessarily flat) list lst and returns a flat list with the same elements, in the same order.
   • (flatten '(x y z z y)) returns '(x y z z y)
   • (flatten '(a (x (y)) (((y)) y z))) returns '(a x y y y z)
8. Consider a list, not necessarily flat, of numbers such as '((1 (2)) (((4))) 5). Use map and apply to write a procedure (sum lst) that sums all of the numbers in such a list.
   • (sum '((1 (2)) (((4))) 5)) returns 12
9. Again consider a general list of numbers and a function f of one argument. Use map and apply to write a procedure (map-to f lst) that builds a new list with the same structure as lst but with f applied to each of the elements of lst to get the new values in the list.
   • (map-to add1 '(3 (4 5))) returns '(4 (5 6))
10. Write (element-of? a lst) that returns #t if a is an element of the (not necessarily flat) list lst and #f otherwise.
    • (element-of? 3 '(2 1 (4 2 (5 3) 1))) returns #t
    • (element-of? 'x '(a (b c (d)) e f)) 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 41 tests in total and when I run (test/gui all-tests), I get this.

Make sure you commit and push.