Lab 2: Working with let and lists

This lab is due at the beginning of your next lab period. It should be submitted as "lab02" and contain a single file called "`lab.scm`". See the "submit" link on the left menu for details. You are highly encouraged to submit whatever you have done by the end of this lab. Remember that duplicate submissions are fine; I will just grade the latest one.

## Symbols

Recall that a symbol is just a quoted identifier, such as `'si413`, or `'wombats`. We can use the function `symbol?` to find out whether something is a symbol, and `symbol=?` to compare two symbols.

### Exercises

For these exercises, use the following exchange rates:
```  1 US dollar = .6932 Euros (euro)
1 US dollar = 76.733 Japanese Yen (yen)
```
1. Create a function `(to-usdollar amt cur)` that takes an amount of money `amt` in some foreign currency `cur` and returns that amount in US dollars. The parameter `cur` will be one of the symbols `'euro`, `'yen`, `'cad`, or `'usdollar`.
So for instance `(to-usdollar 500 'yen)` produces 500/76.733, which comes out to `6.516101286278394`.
2. Create a function `(from-usdollar amt cur)` that does the opposite: takes an amount in US Dollars and converts it to the named currency.
If you're clever, you can write a helper function for this problem and the previous one that will avoid your having to enter the conversion rates twice.
3. Create a function `(convert amt fromCur toCur)` that takes an amount in currency `fromCur` and converts it to crrency `toCur`. Use your functions from parts 1 and 2 and life will be easy!

## Lists

Recall "big 4" of list processing:

• `null`: the name for an empty list.
• `(cons a L)`: Take an item `a` and a list `L` and return the new list with `a` inserted in the front of `L`.
• `(car L)`: Returns the first item in `L`.
• `(cdr L)`: Returns the list containing all the items in `L` after the first item.

If you're faced with nested lists, you sometimes need cars of cdrs, and cdrs of cars, and so forth. The shortcut for a bunch of these in a row is `cXXXr`, where each `X` is either `a` or `d`, corresponding to `car` and `cdr`:

```> (define L '((4 a) (3 x) (3 11 4)))
> (car (cdr L))
(3 x)
(3 x)
> (car (cdr (car (cdr L))))
x
x
```

There are two more extremely useful shortcuts:

• `list`: Takes an arbitrary number of items and makes a single list containing them.
• `append`: Takes an arbitrary number of lists and makes a single list containing all their items.
It is important to understand the difference between these two! Here are sample implementations of each (with only two arguments):

```(define (my-list a b)
(cons a (cons b null)))

(define (my-append L1 L2)
(if (null? L1)
L2
(cons (car L1)
(my-append (cdr L1) L2))))
```

Make sure you understand what is going on here. In particular, notice that `my-append` is recursively processing `L1` and producing a new list.

The "recursive processing" part means that we check when `L1` is empty, and when it is, we have the "base case" and just return `L2`. When `L1` is not empty, we break it down with `car` and `cdr` and make a recursive call on `(cdr L1)`.

The "producing a new list" part means that in the base case we return a list (in this case `L2`; often the list returned in the base case is just `null`). And in the recursive case, we add on to the list returned by the recursive call, using `cons`.

All the exercises below either recursively process a list, or create a new list, or both. Keep in mind what is going, and you should see some of the ingredients above cropping up over and over again.

### Exercises

1. List of Squares
Write a function `squares` that takes integers i and j and returns list of the squares i^2, (i+1)^2, ..., (j-1)^2, j^2.
```> (squares 2 12)
(4 9 16 25 36 49 64 81 100 121 144)
```
2. Nested Lists Pick Aparts
Copy the definition of the following nested list `L` into your definitions window:
```(define L '((a x 2) (('the) b c) (z 12)))
```
Now, write expressions to pick apart L to get the following values (save each of these in your definition file -- put a comment next to each one explaining what it is):
1. the `a` in L
2. the `'the` in L
3. the `12` in L
3. Count cash!
Write a function called `sum-cash` that returns the value in US dollars of a collection of amounts of different currencies (same currencies as above). The amounts will be given in a list L, such that each element of L is itself a list, whose first element is an amount and whose second element is a currency name. So, for example,
```( (12.20 usdollar) (340 yen) (8.50 euro) )
```
as an arguement to `sum-cash` would mean adding 12.20 dollars, 340 yen and 8.50 euros, and giving the total in dollars. Here's an example:
```> (sum-cash '((12.20 usdollar) (340 yen) (8.50 euro)))
28.892922331103236
```
Write a function called `std-dev` that takes a list of numbers and returns their standard deviation. (Recall: std dev of x1, x2, ..., xn is
```     __________________________________________
/
/(x1 - u)^2 + (x2 - u)^2 + ... + (xn - u)^2
/ ------------------------------------------
\/               n - 1
```
... where u is the average of x1, x2, ..., xn. When you write this function, use top-down design. In scheme this means writing the std-dev function using functions you wish were already defined, then going back and defining them later. It can be useful to quote these function calls before you implement them, so you can even do top-down testing!
Example:
```> (std-dev '(34 18 25 23 29 11 28 24 27 29))
6.460134157533676
```

## Let

The `let` construct in Scheme allows you to give a name to a common subexpression. For example, consider the expression

```(33 * (501 - 33)) / ( 1 - (33 * (501 - 33)))
```
The natural way to code this in Scheme is probably
```(/ (- (* 33 501) 33) (- 1 (- (* 33 501) 33)))
```
But you could say "let a = 33 * (501 - 33), and return a / (1 - a)". That's essentially what `let` allows you to do.
```(let ((a (- (* 32 501) 33))) (/ a (- 1 a)))
```

Essentially, `let` is the Scheme way of getting local variable functionality. What you've got is the `let` keyword, followed by a list of variable-name/value pairs, followed by an expression (presumably using the new names) that provides the value of the whole `let` expression. For example:

```> (let  ((a 2) (b 4) (c 6))
(+ a b c)
)
12
```

There is power in using `let` in functions. Suppose I want to define a function called `shifted-cube`, which computes (x + 1)^3 for a value x.

```> (define (shifted-cube x) (let ((a (+ x 1))) (* a a a)))
> (shifted-cube 2)
27
```

### Exercises:

1. Using what you just learned, write a function called `test-sin` that computes 1/(sin(x)^2 + 1) + sqrt(sin(x)^2 + 1) - (sin(x)^2 + 1)^2
2. Write a function `dist` that computes the difference (in inches) between two lengths (given in feet and inches). Example:
```> (dist 3 7 2 11) ;;; difference between 3'7'' and 2'11''
8
```
Write this function using a `let` expression to create values `L1` and `L2` for the lengths in inches of the input feet-and-inches lengths.

## Functions as parameters to other functions

As you have perhaps noticed, you never actually tell scheme what the type of a function parameter is. Thus, if I define some function (f x y), there's nothing to stop me from calling it like this: (f sqrt 16). In other words, there's nothing to stop me from passing f a function as one of its arguments. Does this make sense? It depends what f does with the parameter x. If it uses it like a function, then it makes sense:

```> (define (f x y) (* y (x y)))
> (f sqrt 4)
8
```
What happened here? Well since x is sqrt and y is 4, f evaluates to `(* 4 (sqrt 4))` which is 8. So f is the "apply function x to argument y and then multiply by y" function. Passing functions to functions like this is very powerful. This is part of what we mean when we say that "functions are first class objects" in a functional language.

### Exercises:

1. Finite difference.
Given a function g(x), the finite difference of g(x) at x=n is g(n + 1) - g(n). Define a function `(fd-at g n)` that takes a function g and a value n and returns the finite difference of g at n. For example:
```> (define (f x) (* x x))
> (fd-at f 3)
7
```

## Functions and lists: map and apply

The function map is a really useful function that takes functions as arguments. The expression `(map f L)` applies the function f to each element of the list L and puts the results together in a list. For example:

```> (map abs '(-4 12 -3 -8 11 0))
(4 12 3 8 11 0)
```

If you have a function with k arguments, then you give map k lists, and it will take the first argument from list1, the second from list2, etc.

```> (map * '(2 3 4) '(6 5 4))
(12 15 16)
```

Another useful function of this type is apply. The expression `(apply f L)` calls the function `f` with arguments the elements of `L`. Here are some examples:

```> (apply max '(4 6 2)) ; same as (max 4 6 2)
6
> (apply - '(3 7))     ; same as (- 3 7)
-4
```

Combining map and apply can be very interesting.

```> (define (sqr x) (* x x))
> (map sqr '(1 2 3 4 5 6 7 8 9 10))
(1 4 9 16 25 36 49 64 81 100)
> (apply + (map sqr '(1 2 3 4 5 6 7 8 9 10)))
385
```

Yet another useful function-that-takes-a-function is filter. The expression `(filter f? L)` applies the predicate function `f?` to each element in the list `L`, and returns the list containing only the elements for which the predicate returns true. For example:

```> (filter number? '(a b 2 #t + 4))
(2 4)
```

### Exercises

For these, you will probably want to use this function:

```;;Returns a list containing integers a, a+1, ..., b.
(define (range a b)
(if (> a b)
null
(cons a (range (+ a 1) b))))
```
1. Compute the product of the square roots of the integers from 1 through 10. (Just put this expression in your Scheme file; you don't need to define a function for it)
2. Compute a list of all integers between 1 and 1000 that are divisible by 3 and are perfect squares. (Again, just put this expression in your Scheme file.)
Hint: you should make some helper functions that are predicates. The built-in function `sqr` might also be useful.
3. Make the following definition for P1:
```(define P1 '((3 5) (9 2) (11 6) (8 8) (4 6)))
```
P1 represents a polygon whose vertex coordinates are given by the pairs in P1. Write a function `(translate p d)` that takes a polygon (in the sense of P1, i.e., a list of coordinate pairs) and an offset d (represented by a pair, the x offset and the y offset) and translates the given polygon by the given offset.
```> (define P1 '((3 5) (9 2) (11 6) (8 8) (4 6)))
> (translate P1 '(1 2))
((4 7) (10 4) (12 8) (9 10) (5 8))
>
```
Depending on your approach, the following function might be useful to you:
```(define (repeat x k) ;Creates a list of k copies of x
(if (= k 0) '() (cons x (repeat x (- k 1)))))
```