Homework 3: Structure, Structure, Structure

Due: Friday, October 4 at 23:59
First Commit: Monday, September 30 at 23:59

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 I reserve the right to deduct points for non-higher order solutions.

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. The same partnership and team making procedures apply as previous assignments!

If you need a reminder of the procedures, 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. 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. You can append the homework number to your team name if you wish. (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

• hw3.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. 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. Make sure you write at least three tests for each function. Make sure you test different cases!

This could be a good opportunity for you to test out test-driven development: what would it look like to write the tests first before the implementation?

The questions in this assignment are based on mathematical functions about matrices and vectors. The assignment should (hopefully) give you enough context to understand the concepts without having encountered this material in previous classes. Please reach out if you need help understanding what the specification is asking you to do!

I expect you to try to use map and/or apply for each of your solutions.

Note that the procedures are each very short when you use higher-order functions – that’s the goal of the assignment!

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). Assume that the input to firsts and rests is a list of lists that are nonempty.
   • (firsts '((a b c) (d e f) (g h i))) returns '(a d g)
   • (firsts (list '((a b) (c) (d e)) '(m q f) '(d e f))) returns '((a b) m d)
   • (rests '((a b c) (d e f) (g h i))) returns '((b c) (e f) (h i))
2. Write (vec-add 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-add '(1 2 3) '(4 5 6)) returns '(5 7 9)
   • (vec-add 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
     • Note that $1\cdot4+2\cdot 5+3\cdot6 = 32$
   • (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-mul mat vec) where you can assume that 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-mul '((1 4 7) (2 5 8) (3 6 9)) '(1 2 3)) returns '(30 36 42)
   • (mat-vec-mul '((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}$ and the transpose of $\begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 0 \end{pmatrix}$ is $\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0\\ \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))
   • (transpose '()) returns '()

6. Now that we have a way to multiple a matrix by a vector, let’s implement multiplying a matrix by another matrix! In general, matrix multiplication is done by taking 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-mul lhs rhs) that returns the product of matrices lhs and 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-mul '((1 0 1) (2 1 1)) '((1 2) (1 0) (1 1))) returns ((2 3) (4 5)).

If you haven’t already done so recently, 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. If you’re using Github Desktop, go through the similar steps!

$ git add hw3.rkt tests.rkt HONORCODE.md
$ git commit
$ git push

Part 2. Functions that operate on non-flat lists

As with Part 1, write three tests for each of these functions in addition to implementing them. As a debugging tactic, I would recommend writing out input and output types for different procedures and arguments to map and/or apply on paper. Parentheses in higher-order functions have a big impact on the outcome.

1. Write (flatten lst) that takes a (not necessarily flat) list lst and returns a flat list with the same elements, in the same order. Hint!: append, as opposed to cons, might be helpful here and is permitted.
   • (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)
2. Consider a list, not necessarily flat, of numbers such as '((1 (2)) (((4))) 5). Use map and/or apply to write a procedure (sum lst) that sums all of the numbers in such a list.
   • (sum '((1 (2)) (((4))) 5)) returns 12
3. Again consider a general list of numbers and a function f of one argument. Use map and/or apply to write a procedure (gen-map 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.
   • (gen-map add1 '(3 (4 5))) returns '(4 (5 6))

Frequently Asked Questions

• Can we use flatten in subsequent problems? Yes, feel free to use it wherever it is useful to you.
• For implementing gen-map what kind of inputs can we assume? The goal of gen-map is to “treat” the non-flat lists in some sense as flat lists. So assume that you’re thinking about computation on the elements of the list, not the sublists.

Finishing up

Make sure you wrote tests for eery procedure, 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 hw3.rkt tests.rkt HONORCODE.md
$ git commit
$ git push