Problem Set 2: More SML Programming

Due Thursday, February 17, 2005, 11:00 pm.

Instructions: You will do this problem set by modifying and submitting these source files: mlqueue.sml, expr.sml, and matrix.sml. You should submit each of these files separately via CMS. 

Note: for functions that are not implemented, you should see something of the  form:

    raise Fail "Not implemented"

You should remove this text and replace it with the body of the function.

We will test your code using an automated test script. Your submission must  compile. Programs that do not compile will receive an automatic zero. If you are  having trouble getting your assignment to compile, please visit consulting  hours. If you run out of time, it is better to comment out the parts that do not  compile and hand in a file that compiles, rather than handing in a more complete  file that does not compile. Do not change variable names. Do not change function names. Do not remove our  delimiter comments. Pay scrupulous attention to types. You have been warned. 

There are THREE separate parts to this assignment.

Part 1: Implementing Basic Data Structures: A Multi-Level Priority Queue

A priority queue is a fundamental abstract data structure where elements have associated priorities. This data structure allows to efficiently retrieve the element with highest priority from the queue. A multi-level priority queue consists of several priority queues, one at each level. Retrieving an element from such a queue yields the element with highest priority from the non-empty queue with highest level. The structure also supports an operation that moves elements from one level to the level below if certain conditions are met.

For instance, such a structure is used for scheduling processes in operating systems. New processes are inserted in the queue with highest level. As processes age, they are moved to the lower level queues. Since the scheduler always chooses processes from higher-level queues, this allows short-lived processes to complete faster.

Implement such a data structure using a list that contains all the elements of all queues. Each element is a triple consisting of: its priority, the level of the queue it belongs to, and the data item. Priorities and levels are represented as integer numbers:

   type 'a mlqueue = (int * int * 'a) list

The first integer is the level, the second is the priority. Smaller numbers represent higher priorities and levels. The list is maintained sorted, such that elements of a queue with level n occur before all the elements of queue with level n+1. Further more, within the same level, elements with higher priorities occur at the front of the list. Using this representation, implement the following functions to support such a data structure:

(* enqueue q l p e = inserts an element e with priority p 
 * at level l in the multi-level queue q. *)
val enqueue : 'a mlqueue -> int -> int -> 'a -> 'a mlqueue

(* dequeue q = a pair contianing: the element with highest 
 * priority from the highest-level queue in q; and the
 * remaining queue.
 * Raises Empty is the queue is empty. *)
val dequeue : 'a mlqueue -> 'a * 'a mlqueue

(* move pred q = moves all elements that satisfy the predicate
 * pred to a lower level queue within q. *)
val move : ('a -> bool) -> 'a mlqueue -> 'a mlqueue

(* atlevel q n = a list of all elements at level n. The list 
 * contains (priority, data item) pairs, and is sorted by 
 * priorities. *)
val atlevel: 'a mlqueue -> int -> (int * 'a) list

(* lookup pred  q = looks up the first element in q that 
 * satisfies pred, and returs its level and priority.
 * Raises NotFound if no such element exists. *)
val lookup : ('a -> bool) -> 'a mlqueue -> int * int

(* isempty q = true iff the queue q contains no elements. *)
val isempty : 'a mlqueue -> bool

 

Part 2: Boolean Expressions 

A boolean expression (or formula) consists of: variables, negation, boolean operators (such as AND, OR, etc). We can represent operators and expression using the following types and datatypes:

   datatype oper = AND | OR | XOR
   datatype expr = Var of string | Not of expr | Op of oper * expr * expr

For instance, the boolean formula "x and (y or not x)" is represented by the following ML expression:

   Op(AND, Var("x"), Op(OR, Var("y"), Not(Var("x"))))

In this problems you will implement several functions that manipulate such formulas.

  1. Write a function eval that evaluates the truth value of a formula, given the truth values of all variables in the formula. For instance, if x is true and y is false, then the above formula evaluates to false. The signature of the function eval is as follows:

    (* eval v f = the truth value of formula v given the
     * the mapping v of variables tp their truth values. *)
    val eval :(string -> bool) * form -> bool

    To make it easier to test eval, we have provided a function toMap that converts a list of variable names into a function that maps each variable in the list to true, and all other variables to false. 

  2. A boolean expression has a tree structure, where Var expressions are the leaves, Not expressions are nodes with one child, and Op expressions are nodes with two children. Write a fold function that that traverses the tree structure of an expression bottom-up (i.e., post-order: children first, then current node):

    (* fold f v e = folding over all expression nodes in e traversed 
     * bottom-up, starting with value v, and applying function f on 
     * each node. *)
    val fold : (expr * 'a -> 'a) -> 'a -> expr -> 'a
  3. Use the above fold function to write a function that yields a list of all variables in a boolean expression.  The computed list should not have duplicates, even if a variable occurs multiple times in the input expression. 

    (* variables e = list of variables in e, with no duplicates *)
    val variables : expr -> string list

    For instance, the variables of the example expression above are ["x", "y"].

 

Part 3: Sparse Matrices. 

Matrices with many more zeros than non-zero values are referred to as sparse matrices. For very large such matrices, it can be inefficient to store all of  those zeros with the matrix representation. A more efficient scheme stores only  the non-zero values. For this part of the problem set, you will implement common  matrix operations using the sparse matrix representation defined below. You will use the following representation: 

  type element = int * int         (* column, value pair *)
  type row = element list
  type matrix = int * row list
A sparse matrix will be represented by a list of rows, wherein each row contains (column, value) pairs, called elements. Each non-zero entry in a given row has a (column, value) pair where the column field indicates which column of the given  row that value can be found in (indexed starting at zero - thus if a matrix has  3 columns, they will be indexed 0, 1, and 2). In each row, (column, value) pairs are listed in ascending order by column. Entries of a matrix that are zero thus have no associated element in the representation, saving space. This list of rows containing (column, value) pairs comprises the data portion of the matrix. A matrix also has an additional integer field indicating the number of columns it has (note that we don't need to store the number of rows we have explicitly, since this can be determined by counting up the number of lists within the data portion of the matrix - you will do this later). For now we will only consider matrices with integer elements.

For example, the 3x3 integer identity matrix, which looks like this:
[1 0 0]
[0 1 0]
[0 0 1]
would have the following representation:
(3, [ [(0,1], [(1,1)], [(2,1)] ] )

A few additional examples follow. In the example below, the second row is an empty list because it contains only zeros:
[1 0 0]
[0 0 0] = (3, [[(0,1)], [], [(1,2)]])
[0 2 0] 

Another example:
[0 0 0 0 0 0 0 0]
[0 0 0 5 0 0 0 0] = (8, [[], [(3,5)], []])
[0 0 0 0 0 0 0 0]
This scheme can represent dense matrices as well, when all elements are non-zero:
[1 2 3] = (3, [[(0,1),(1,2),(2,3)], [(0,4),(1,5),(2,6)]])
[4 5 6] 
What you need to do: Implement the following functions defined in matrix.sml, which operate on matrices represented in this way. To help you, we have provided function printMatrix, which will display a sparse matrix in a familiar notation. 

  1. Implement a function that computes the number of rows in a matrix:

    2. val rows : matrix -> int
    rows(M) should return the number of rows that matrix M has. Recall that you can figure this out by counting the number of lists that appear in the matrix representation.

  2.  Implement a function that test of a matrix representation is valid:

    3. val isValid : matrix -> bool
    isValid(M) should return true if and only if matrix M satisfies the above representation. This means that M does not have more entries in a given column than advertised in its column field, and that elements in each row are sorted properly. Also, no zero-valued element may appear in the representation. Note that the empty matrix that has 0 columns or 0 rows is NOT valid.

  3. Write a function that adds two matrices:

    4. val add : matrix * matrix -> matrix
    add(A, B) should return the matrix sum of matrices A and B. This is simply the sum of corresponding elements between the matrices. For example,

    [1 4]   [1 1]     [1+1 4+1]     [2 5]
    [2 5] + [0 3] =   [2+0 5+3]  =  [2 8]
    [3 0]   [3 1]     [3+3 0+1]     [6 1]
    Addition cannot be perform on matrices that do not have identical dimensions. In the case that the addition cannot be performed for any reason, you should raise a Fail exception.

  4. Implement a function that computes the dot product between two rows. This function is useful for multiplying matrices:

    5. val dotProduct : element list * element list -> int
    In general, the dot product of two sequences of equal length, (x1,...,xn) and (y1,...,yn) is defined as the sum

    x1*y1 + x2*y2 + ... + xn*yn
    We define the dot product of two empty sequences to be 0. 

    The function dotProduct(e1,e2) should compute the dot product of the elements in rows e1 and e2, represented using our format. Note, that in our representation, the zero elements in the sequence are implicit and not present in the list. Your function should take this fact into account. For instance, the dot product of [(1,3),(2,5)] and [(2,3),(4,2)] is 5*3 = 15, since position 2 is the only position that contains non-zero values in each row.

  5. Write a function that transposes a matrix:

    6. val transpose : matrix -> matrix 
    Recall that the transpose of a matrix A is the matrix with its rows and columns swapped. The transpose of a matrix A is defined as the matrix B where: A(i,j) = B(j,i). For example, the transpose of : 

    [1 0 3]
    [0 5 0] 

    is:

    [1 0]
    [0 5]
    [3 0]

  6. Write a function that multiplies two matrices:

    7. val mult : matrix * matrix -> matrix
    mult(A, B) should return the matrix product of A and B. This is a bit more complicated than addition. Formally, the product C = A x B is a matrix whose elements are such that C(i,j) is the dot product of the i-th row of A and the j-th column of B. Note that if matrix A has dimensions (m x p) and matrix B has dimensions (p x n), the resulting product will have dimensions (m x n) (that is, m rows and n columns). Also, mult should raise Fail if the multiplication cannot be completed for any reason, such as the two matrices having incompatible dimensions.

    Here is an example of matrix multiplication:

    [0 1 1]   [1 3 1]
    [2 2 2] * [2 2 0]
              [3 1 1]

    = [0+2+3 0+2+1 0+0+1]
      [2+4+6 6+4+2 2+0+2]

    = [5  3  1]
      [12 12 4]
    Hint: Transpose the second matrix B, then compute the dot product between rows of A, and rows of the transposed matrix B to get the elements of C.

Note: You may find the SML List library useful for this part. In particular,  some of functions can be implemented using one or more applications of foldl or foldr. Be sure to use these when applicable. You may also want to take a look at the ListPair structure, which has useful operations for working with pairs of lists.