# Homework 3: Structured Lists

**Due: 2020-09-24 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 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.)

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

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

- 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

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

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

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.

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

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

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

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