Programming Project 5

Due date: Thu 4/17 11:00 pm

Introduction

This assignment has two parts. In the first part we use higher order functions in ML. In the second part you will write simple functions in Prolog.

Higher Order Functions in ML

In this part we use higher order functions to implement some matrix operations in ML. We represent a matrix as a list of integer lists. Here are three ML values and the matrices they represent. Notice that the number of rows and columns need not be the same.
val A = [[1,2,3],[3,4,5],[3,1,1]];
val B = [[1,2,3,5],[5,3,4,5],[5,3,1,1],[5,3,1,1]];
val C = [[1,2,3,5],[5,3,4,5],[5,3,1,1]];

 A corresponds to        B corresponds to       C corresponds to
   [ 1 2 3 ]               [ 1 2 3 5 ]             [ 1 2 3 5 ]
   [ 3 4 5 ]               [ 5 3 4 5 ]             [ 5 3 4 5 ] 
   [ 3 1 1 ]               [ 5 3 1 1 ]             [ 5 3 1 1 ]
                           [ 5 3 1 1 ]
  1. Write a function transpose: 'a list list -> 'a list list whose input is a matrix and whose output is the transpose of the matrix where columns of the original matrix become the rows of the output matrix. For example transpose(A) returns [[1,3,3],[2,4,1],[3,5,1]].

    You may use any number of helper functions in this part. You must use some higher order functions (such as map or foldl or your own functions) in the implementation. Code using direct iteration without higher order functions will not obtain full credit.

  2. Recall that when calculating a matrix product M1 x M2 each element of the resulting matrix is a dot product of a row in M1 with a column in M2 where a dot product is a sum of products of the corresponding elements. For example if we are calculating A x A then the element in the second column of the first row in the result is equal to the dot product of [1,2,3] and [2,4,1] and therefore has the value $2+8+3=13$. Similarly the $i,j$ entry is equal to the dot product of the $i$'th row of M1 and $j$'th column of M2. For example
         A x A is equal to             A x C is equal to
           [ 16 13 16 ]                 [ 26 17 14 18]
           [ 30 27 34 ]                 [ 48 33 30 40]
           [ 9  11 15 ]                 [ 13 12 14 21]
    

    Write a function MM : int list list * int list list -> int list list that calculates matrix multiplication.

    You may use any number of helper functions in this part. You must use some higher order functions (such as map or foldl or your own functions) in the implementation. Code using direct iteration without higher order functions will not obtain full credit.

Prolog Introduction - Using the SWI Prolog System

Prolog Code

  1. Use the file db1.pl (from class examples) and write queries to extract information from the database as follows. (NB use the database predicates only -- do not use the rules in db1-rules.pl.) Write expressions for queries that: For this part write your queries as comments in your Prolog file.

  2. Write one or more rules defining the predicate hereOnTue(Student). The predicate identifies students who are taking classes on Tuesdays. Your programs should work for db1.pl and any other database in the same format (note the lower case encoding of Tuesday in db1.pl).

  3. Write one or more rules defining the predicate everyday(Student). The predicate identifies students who are taking classes on Mondays, Tuesdays, Wednesdays, and Thursdays. Your programs should work for db1.pl and any other database in the same format.

  4. Write one or more rules defining the predicate deep(Course). The predicate identifies courses that require a sequence of at least two courses to be taken before them. In db1.pl the only course that satisfies this predicate is comp3b.

  5. For this part please refer to the code for binary search trees in usingterms.pl. Write one or more rules defining the predicate range(Tree,Value). The predicate is true when value is the difference between the maximum value in the tree and the minimum value in the tree. For the example tree in the file this value is $12-2=10$.

    You may want to first write rules calculating the minimum and maximum of the tree and then write a rule to calculate the range.

Files

The Prolog files are available through the class examples section of the course web page.

Submitting your program

Your code for the ML section should be in a file pp5.sml, the code for the Prolog section in pp5.pl.

Assuming your files are in the current directory on one of our Sun workstations or servers, you should submit by typing
provide comp80 pp5 pp5.pl pp5.sml

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation -no_images -dir TEMPHTML pp5.tex

The translation was initiated by Roni Khardon on 2008-04-08


Roni Khardon 2008-04-08