# Exercises #2

These exercises make use of some of the functions from Exercise #1.
1. Rewrite the `change` function (Exercise 1.3) to work for any set of coins (or notes) for any decimal currency. The coin values should be passed to `change` as a variable number of arguments which are the coin values in units (e.g., a quarter would be represented as 25) in any order. The first arg is still the number to make change for.
```# change :: num X num ... -> [num]
proc change {n args} {...}
change 75 25 10 5 1
=> 3 0 0 0
change 75 10 25 1 5
=> 3 0 0 0
change 75 50 25 10 5 1
=> 1 1 0 0 0```
2. Rewrite the `iota` function (Exercise 1.4) to take an optional second argument which is an increment to separate the integer values. The default increment is 1. `iota` always returns a list whose length is equal to its first argument.
```# iota :: num X num ... -> [num]
proc iota {n {inc 1}} {...}
iota 10
=> 0 1 2 3 4 5 6 7 8 9
iota 10 3
=> 0 3 6 9 12 15 18 21 24 27
megatcl>iota 3 2
0 2 4
megatcl>iota 3 4
0 4 8
megatcl>```
3. Write `map`, a function that abstracts `incrlist` (Exercise 1.5) and `strlenlist` (Exercise 1.6). `map` takes two arguments: f, a restricted class of Tcl script; and L, a list. `map` applies f to each element of L, returning a list of the results. The result list will always be the same length as L.

The types of L and the result need not match. This means that `map` is conceptually polymorphic. Of course, since all Tcl values are strings, you could also say that the two lists are always lists of strings, but this is often less useful than thinking about the semantics of the strings.

f needs to be a Tcl script of one argument.

```# map :: (alpha -> beta) X [alpha] -> [beta]
proc map {f L} {...}
map I [iota 10]
=> 0 1 2 3 4 5 6 7 8 9
map {K 1} [iota 10]
=> 1 1 1 1 1 1 1 1 1 1
map {expr 10 +} [iota 10]
=> 10 11 12 13 14 15 16 17 18 19```
4. Write `incrlist` and `strlenlist` in terms of `map`.
5. Write `foldl`, a function that abstracts `sumlist` (Exercise 1.7), `multlist` (Exercise 1.8) and `catlist` (Exercise 1.9). `foldl` takes three arguments:
f
A binary function
id
The identity element for f
L
A list

`foldl` applies f pairwise to all the elements of L, left associatively. It's as if f were inserted between each element of L, parenthesized left-associatively:

```proc + {a b} {expr \$a + \$b}
foldl + 0 [list 1 2 3 4]
== (((1+2)+3)+4)
=> 10```
Why is the identity element necessary? Consider the case of a list of length one:
```foldl + 0 [list 1]
== (..+1)```
The problem is, we don't have two values for our binary `+` operator. The identity element gives us a value to use at the left end of the expression; it needs to be the identity for f so that it doesn't otherwise change the result:
```foldl + 0 [list 1 2 3 4]
== ((((0+1)+2)+3)+4)
=> 10
proc * {a b} {expr \$a * \$b}
foldl * 1 [list 1 2 3 4]
== ((((1*1)*2)*3)*4)
=> 24```

If L is a list of integers, then f should be a function of two integers; it can return any type of value. If L is a list of strings, then f should be a function of two strings; it can return any type of value. If L is a list of variable names, then f should be a function of two variable names; it can return any type of value.

Another way of describing f is to say that if L is a list of elements of type alpha, then f must be a function of type (alpha `X` alpha -> beta). We don't care about the type of f's return value except to say that it may (but is not required to be) different from alpha.

```# foldl :: (alpha X alpha -> beta) X beta X [alpha] -> beta
proc foldl {f id L} {...}```

Do you understand why `foldl` needs a parameter for the identity element?

6. Implement `sumlist`, `multlist` and `catlist` in terms of `foldl`.
7. Write the function `zip`, which takes three arguments:
f
A binary function
a
A list
b
Another list

`zip` applies f pairwise to corresponding elements of a and b, returning a list of the results.

If a is a list of integers, and b is a list of strings, then f should be a function that takes an integer as its first argument and a string as its second argument. It can return any type of value.

```# zip :: (alpha X beta -> gamma) X [alpha] X [beta] -> [gamma]
proc zip {f a b} {...}
proc + {a b} {expr \$a + \$b}
zip + [iota 10] [iota 10]
=> 0 2 4 6 8 10 12 14 16 18
zip list [list A B C D] [list 1 2 3 4]
=> {A 1} {B 2} {C 3} {D 4}```
8. Write the command `vardefault`, which takes two arguments, the name of a variable, and a default value. If the variable is defined in the calling scope, `vardefault` returns the variable's value. If it is not defined, `vardefault` returns the default value.
```proc vardefault {var default} {...}
set x 45
vardefault x 0
=> 45
proc foo {} {
vardefault x 0
}
foo
=> 0```

To write this function, you'll need to use `upvar` to achieve call by name, and you'll need a way to test whether or not a variable is defined (use `info exists`).

Keith Waclena
The University of Chicago Library