1. From text: problem 9.9, parts a and b. Write the type of expression for a matrix, and the type expressions for the function that adds two matrices and the function that computes the transpose of a matrix.

addition takes two matrices and returns a matrix, so its type expression is

(int list list * int list list) -> int list list

This assumes that the operation is always applied to a pair of arguments, i.e. we are not allowing for Currying.

The transpose takes a matrix into a matrix, so its type expression is int list list -> int list list

2. Consider the function Reduce, that we examined in class.

a) Write a C++ template with the same functionality.

Write an Ada generic function with the same capability.

template < class T, class Res_Type, Res_Type fun, Res_Type init> Res_Type reduce (T* Lis, int siz) { Res_Type result = init; for (i = 0; i < siz; i++) { result = fun (Lis [i], result); } int bunch[] = (1,2,3,4,5); int res = reduce < int, int, operator+, 0> (bunch, 5); // test it }Note that we chose to pass the size of the array to be reduced, as an explicit parameter in the function to be called. We could make this more elaborate by using some other container for the collection to be reduced, rather than just an array.

A non-recursive Ada version looks very similar:

generic type T is private; type Res_Type is private; type List is array (integer range <>) of T; with function Fun (X : T; Y : Res_Type) return Res_Type; Init : Res; function Reduce (L : List) return Res_Type; function Reduce (L : List) return Res_Type is begin Result : Res_Type := Init; for J in L'range loop Result := Fun (L (J), Result); end loop; return Result; end Reduce;

It is interesting to note that Reduce is an APL primitive, that applies to all homogeneous binary functions. +/V is the sum of the elements of V, */V is the product of the elements of V, etc. In what way is the APL version more restrictive than the ML version?

3. Consider the Map function, whose ML definition is as follows:

fun map f l = if null l then [] else f (hd l) :: (map f (tl l));

Write the type expression for this function.

map: fn = 'a -> 'b -> a' list -> 'b list

4. From text: problem 10.5, parts a) and b) (part c) is a slide from last lecture). Tail-recursive versions of familiar functions, using the programming trick known as an accumulator variable.

(define (sum lis) (iter-sum lis 0)) (define (iter-sum lis tot) (if (null? lis) tot (iter-sum (crd lis) (+ (car lis) tot))))This is tail-recursive, because the last operation performed by iter-sum is a call to itself.

Part b) is identical, of course. We might as well make this into a single function with a functional argument:

(define (iter-fold op lis tot) (if (null? lis) tot (iter-fold op (cdr lis) (op (car lis) tot)))) and then (define (sum lis) (iter-fold + lis 0) (define (prod lis) (iter-fold * lis 1)