# 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*!

- 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 non-empty and of equal length.`(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))`

- 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`

- 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`

- 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)`

- 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`'()`

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

- 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)`

- 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`

- 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*The goal of`gen-map`

what kind of inputs can we assume?`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
```