Assignment VIII: Solution




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.
Solution. a matrix is a list of its rows, and a row is a list of integers. Therefore the type expression for a row is (int list), and a matrix is an (int list) list.
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.
Solution: in both cases we have 4 template arguments or generic parameters: two types, a function, and a value.
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?
Answer: The ML version, and the version given above, allows the final type to be distinct from the type of the list elements. The APL version requires both of these to be identical.
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.
Solution: Map takes a list and produces a list, applying the given function to each element of the list. The function domain must be the element type of the input list, the function result can have any type. Therefore:
   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.
Solution:
(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)