COP 4555 - Homework 3

Due Monday, February 28

Given vectors u = (u₁, u₂,..., u_n) and v = (v₁, v₂,..., v_n), the inner product of u and v is defined to be u₁*v₁ + u₂*v₂ + ... + u_n*v_n. Write an SML function inner that takes two vectors represented as int lists and returns their inner product:
```
  - inner [1,2,3] [4,5,6];
  val it = 32 : int
```
(Assume that the two lists have the same length.)
The transpose of a matrix M is the matrix obtained by reflecting M about its diagonal. For example, the transpose of
```
  / 1 2 3 \
  \ 4 5 6 /
```
is
```
  / 1 4 \
  | 2 5 |
  \ 3 6 /
```
An m-by-n matrix can be represented in SML as a list of m rows, each of which is a list of length n. For example, the first matrix above is represented as the list
```
  [[1,2,3],[4,5,6]]
```
Write an efficient SML function to compute the transpose of an m-by-n matrix:
```
  - transpose [[1,2,3],[4,5,6]];
  val it = [[1,4],[2,5],[3,6]] : int list list
```
Assume that all the rows in the matrix have the same length.
Hint: You can make very good use of map here.
Given an m-by-n matrix A and an n-by-p matrix B, the product of A and B is an m-by-p matrix whose entry in position (i,j) is the inner product of row i of A with column j of B. For example,
```
                / 0 1 \
  / 1 2 3 \  *  | 3 2 |  =  /  9 11 \
  \ 4 5 6 /     \ 1 2 /     \ 21 26 /
```
Write an SML function to do matrix multiplication:
```
  - multiply [[1,2,3],[4,5,6]] [[0,1],[3,2],[1,2]];
  val it = [[9,11],[21,26]] : int list list
```
Assume that the dimensions of the matrices are appropriate.
Hint: Use inner, transpose, and map.
Recall that an ML function that takes two arguments can be coded in either uncurried form (in which case it takes a pair as its input) or curried form (in which case it takes the first argument and returns a function that takes the second argument). In fact it is easy to convert from one form to the other in ML. To this end, define an ML function curry f that converts an uncurried function to a curried function, and an ML function uncurry f that does the opposite conversion. For example,
```
  - val cplus = curry op+;
  val cplus = fn : int -> int -> int
  - val plus3 = cplus 3;
  val plus3 = fn : int -> int
  - plus3 10;
  val it = 13 : int
```
What are the types of curry and uncurry?
An ML list can be thought of as representing a set, where the order of the elements in the list is irrelevant. Write an ML function powerset such that powerset set returns the set of all subsets of set. For example,
```
  - powerset [];
  stdIn:18.1-18.12 Warning: type vars not generalized because of
     value restriction are instantiated to dummy types (X1,X2,...)
  val it = [[]] : ?.X1 list list
  - powerset [1,2,3];
  val it = [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]] : int list list
```
Note that powerset [] is not a syntactic value, and hence is not allowed to be polymorphic under SML97's value restriction. Also note that it doesn't matter what order the elements of powerset [1,2,3] come out in.
The function twice can be defined either by
```
  - fun twice f = fn x => f (f x);
  val twice = fn : ('a -> 'a) -> 'a -> 'a
```
or, using SML function composition operator o, by
```
  - fun twice f = f o f;
  val twice = fn : ('a -> 'a) -> 'a -> 'a
```
If we also define
```
  - fun succ n = n+1;
  val succ = fn : int -> int
```
then we can form expressions like
```
  twice (twice (twice (twice succ)))
```
Less obviously, we can form expressions like
```
  twice twice twice twice succ
```
in which (by ML's conventions) the function applications are associated to the left. Figure out rules that give the values of these expressions, for any number of occurrences of twice. (Approach this problem experimentally.)

Back to

smithg@cs.fiu.edu