Homework 3

Data Types and Curried Functions

 Modified: 

Overview

Relational database operations common to the SQL language supported by Access, MySQL, Oracle and many others are based upon the standard mathematical operations on sets of union, intersection, difference and Cartesian product.  Other operations specifically for maniuplating relational databases are select, project and join. For example, the standard SELECT operation serves to filter elements that meet some specified criteria. In the following exercise, we will implement a simple relational database using these set theoretic operations. 

First a definition of the set data type supported in our database. The sets are defined as lists where I is an int list, S is a string list, etc. The Cartesian product, for example of  IxS produces an (int * string) tuple list. The naming of the data types attempts to hint at tuples definition so that SI is a list of (string * int) tuples, the result of SxI; SIIS is a list of ((string*int)*(int*string)), the result of (SxI)x(IxS), etc. Below are basic set definitions in ML:
 

datatype set =                                                        (* Examples *)
    I of int list |                                                        (* I [1,2,3] *)
    S of string list |                                                   (* S ["a","b","c"] *)
    IS of (int * string) list |                                        (* IS [(1,"a"), (2,"b") ] *)
    II of (int * int) list|                                              (* II [(1,2), (3,4), (5,6)] *)
    SS of (string * string) list |                                   (* SS [("a","b"), ("c","d")] *)
    SI of (string * int) list |                                        (* SI [("a",1), ("b",2)] *)
    SISI of ((string * int) * (string * int)) list |            (* SISI [(("a",1),("b",2)), (("c",3),("d",4))] *)
    SIIS of ((string * int) * (int * string)) list;             (* SIIS [(("a",1),(2,"b")), (("c",3),(4, "d"))] *)

 

Assignment

It is recommended to do Assignments 1-7 in order. Write and give output from TESTING each of the following assignments:

  1. Recall that the Cartesian product produces a set as a tuple list of two sets. Some examples are below.
    fun product (I s1) (I s2) = II (pairs s1 s2)
    |    product (S s1) (S s2) = SS (pairs s1 s2)
    |    product (SI s1) (IS s2) = SIIS (pairs s1 s2);


    For example:

    val i2 = I [5555,6666];
    val s2 = S ["CHEM", "MATH"];
    product i2 s2;                                    (* IxS *)
        val it = IS [(5555, "CHEM"), (5555, "MATH"), (6666, "CHEM"), (6666, "MATH")] : set
        
    product s2 i2;                                    (* SxI *)
        val it = SI [("CHEM", 5555), ("CHEM", 6666), ("MATH", 5555), ("MATH", 6666)] : set
     

    Complete defining the product for the remaining three set cases of IS, SI, and SISI (I and S are not product results).

    You will need to define a pairs function that generates all possible pairs as tuples of elements from two lists. Hint: Write a function to distribute one element across every element of a list;  dist (3, ["a","b","c"]) returns [(3, "a"), (3, "b"), (3, "c")].

    Test using the following. Show result of last test.

    val i1 = I [1111,2222,3333];
    val i2 = I [5555,6666];
    val s1 = S ["CSCI", "ENG", "PHY"];
    val s2 = S ["CHEM", "MATH"];

    val is = product i1 s1;
    val si1 = product s1 i1;
    val si2 = product s2 i2;
    val sisi = product si1 si2;
    val siis1 = product si1 is;
    val siis2 = product si2 is;                            (* Verify each but print this result only *)


  2. Using member and union functions for lists from earlier homeworks and notes, implement the union operation on the set data types SI and SIIS. The following union handles three cases and uses the old list union function renamed to unionList.

    fun union (I s1) (I s2) = I (unionList s1 s2)
    |    union (IS s1) (IS s2) = IS (unionList s1 s2)
    |    union (SISI s1) (SISI s2) = SISI (unionList s1 s2);

Test using the following. Show result of union tests only.

val i1 = I [1111,2222,3333];
val i2 = I [5555,6666];
val s1 = S ["CSCI", "ENG", "PHY"];
val s2 = S ["CHEM", "MATH"];
val is = product i1 s1;
val si1 = product s1 i1;
val si2 = product s2 i2;
val sisi = product si1 si2;
val siis1 = product si1 is;
val siis2 = product si2 is;

union si1 si2;                                     (* Show union results only *)
union siis1 siis2;                                (* Result is a big SIIS set *)
  1. The following predicate function determines if the first tuple field of the second parameter is greater than the first parameter.

    fun gtIx (x:int) (a:int, _) = a > x;
    gtIx 4 (5,"red");        returns true

    The following predicate function determines if the second tuple's second field of the second parameter is greater than the first parameter.

    fun gtxxxI (x:int) ((_, _),(_, i:int)) = i > x;
    gtxxxI 4 ((6,"blue"),("red",5));                        returns true

    Define the two predicate functions similarly to produce the following. Show test results. 
     

    gtSx "red" ("blue", 5);
        val it = false : bool
    gtSx "blue" ("red", 5);
        val it = true : bool

    eqxIxx 4 (("red",4),(6,"blue"));
        val it = true : bool
    eqxIxx 4 (("red",3),(6,"blue"));
        val it = false : bool

     

  2. Curried functions promote code reuse. Question 3 implemented binary predicate functions that return true when some criteria condition is met. The use of the predicates in Question 3 was to bind the two parameters and return a boolean result. A useful alternative is to bind only the first parameter and return an anonymous unary predicate function. For example, the following are equivalent:

    fun gtIx (x:int) (a:int, _) = a > x;

    gtIx 4 (5,"red");
        val it = true : bool
    (gtIx 4) (5,"red");
        val it = true : bool

    (gtIx 4) binds the first parameter x to 4 and returns the anonymous unary predicate function:

        fn (a:int, _) => a > 4;

    The effect is to convert a predicate function of two parameters into a predicate function of one parameter for the relation a > 4. This allows the more general case of the binary predicates in Question 3 to be used in conjunction with the filter function discussed in class. The filter function applies a unary predicate function to every element of a list, returning those elements for which the predicate is true.

    Using the normal filter function and the curried (gtIx 4) filters only those tuples where the first field is greater than 4 from the list:

    fun filter f [] = [] 
    | filter f (h::t) = if (f h) then h :: (filter f t) else (filter f t); 

    filter (gtIx 4) [(7,"CSCI"),(3,"CHEM"), (6,"PHY")];
            val it = [(7, "CSCI"), (6, "PHY")] : (int * string) list

    Perform unit tests of these functions before moving on to Question 5, the following uses the filter function from class and tests using your predicates of Question 3. Show filter test results only.

    val i1 = I [1111,2222,3333];
    val i2 = I [5555,6666];
    val s1 = S ["CSCI", "ENG", "PHY"];
    val s2 = S ["CHEM", "MATH"];
    val is = product i1 s1;
    val si1 = product s1 i1;
    val si2 = product s2 i2;
    val sisi = product si1 si2;
    val siis1 = product si1 is;
    val siis2 = product si2 is;

    filter (gtSx "CSCI") [("CSCI",3.0),("PHY",4.0),("MATH",5.0)];

    val (SIIS x) = siis2;                    (* x is the list of the SIIS set *)
    filter (eqxIxx 5555) x;                    (* filter 5555 entries *)
  1. A key database operation is selection from a set given a criteria relation, essentially a filter operation on lists. For example, using the selection criteria of the first tuple field equal 5555 on the set:
         IS [(5555, "CHEM"), (5555, "MATH"), (6666, "CHEM"), (6666, "MATH")]
    returns:
         IS [(5555, "CHEM"), (5555, "MATH")]

    Select functions are given below for IS and SISI sets:

    fun selectIS (IS L) f = IS (filter f L);
    fun selectSISI (SISI L) f = SISI (filter f L);

With the appropriate curried predicate function, set selection is implemented:

    selectIS isSET (gtIx 2222);
    selectSISI sisiSET (gtxxxI 2222);

Implement selection operations for SI and SIIS sets for the test below. Show select test results only.

val i1 = I [1111,2222,3333];
val i2 = I [5555,6666];
val s1 = S ["CSCI", "ENG", "PHY"];
val s2 = S ["CHEM", "MATH"];
val is = product i1 s1;
val si1 = product s1 i1;
val si2 = product s2 i2;
val sisi = product si1 si2;
val siis1 = product si1 is;
val siis2 = product si2 is;

selectSI si1 (gtSx "CSCI");
selectSIIS siis1 (eqxIxx 2222); 
  1. Anonymous functions are useful when a function is used only once, avoiding the effort of implementing many seldom used functions. From Question 3 we saw that:

    fun gtIx (x:int) (a:int, _) = a > x;

    gtIx 4 (5,"red");
        val it = true : bool
    (gtIx 4) (5,"red");
        val it = true : bool

    (gtIx 4) binds the first parameter x to 4 and returns the anonymous unary predicate function:

        fn (a:int, _) => a > 4

     so that:

        (fn (a:int, _) => a > 4) (5, "red");
            val it = true : bool

    Used with the filter function:

        filter (fn (a:int, _) => a > 4) [(7,"CSCI"),(3,"CHEM"), (6,"PHY")];
            val it = [(7, "CSCI"), (6, "PHY")] : (int * string) list

    and with the selectIS function:

        selectIS is (fn (a:int, _) => a > 2222);
                val it = IS [(3333, "CSCI"), (3333, "ENG"), (3333, "PHY")] : set

    Use the selection implementation operations for SI and SIIS. Replace the gtSx and eqxIxx below with anonymous functions. Show select test results only.

    val i1 = I [1111,2222,3333];
    val i2 = I [5555,6666];
    val s1 = S ["CSCI", "ENG", "PHY"];
    val s2 = S ["CHEM", "MATH"];
    val is = product i1 s1;
    val si1 = product s1 i1;
    val si2 = product s2 i2;
    val sisi = product si1 si2;
    val siis1 = product si1 is;
    val siis2 = product si2 is;

    selectSI si1 (gtSx "CSCI");
    selectSIIS siis1 (eqxIxx 2222); 

 

  1. Set difference, R - S, is all tuples in R but not in S. For example:

        R = IS [(3333, "CSCI"), (3333, "ENG"), (3333, "PHY")]
        S = IS [(3333, "CSCI"), (3333, "BIO")]

        R - S = IS [(3333, "ENG"), (3333, "PHY")]

    Define the difference operation     for SI and SIIS sets for the test below. Show difference test results only.
     
    val i1 = I [1111,2222,3333];
    val i2 = I [5555,6666];
    val s1 = S ["CSCI", "ENG", "PHY"];
    val s2 = S ["CHEM", "MATH"];
    val is = product i1 s1;
    val si1 = product s1 i1;
    val si2 = product s2 i2;
    val sisi = product si1 si2;
    val siis1 = product si1 is;
    val siis2 = product si2 is;

    difference si1 si2;
    difference siis1 siis2;

 

Turn In

  1. Cover sheet with your name, date, and Homework 3.
  2. Print out for Assignments 1-7 of function definitions.
  3. Print out for Assignments 1-7 of test interactions containing the evaluation results of all the functions using the given test examples.

Document last modified: