CS 3304 Comparative Languages

Homework 3

Submit your solution as a text file "hw3.sml". Include a header

(* Name: <your name here> *)
(* PID: <your pid here>   *)
(* Homework 3                *)

All problems involve using SML and are based on material discussed in class or in the online notes. If any auxillary functions are needed they are mentioned explicitly.

Problems to submit:

1. Write a function trans that takes a list of pairs and outputs a pair of lists. For instance, the input [(1,"a"),(2,"b")] would result in the output ([1,2],["a","b"]). Your function will need to be recursive, and you must use pattern matching. The type of your function should be val trans = fn : ('a * 'b) list -> 'a list * 'b list. You should not need to constraint any types if you setup the cases in the function properly.
2. Propositional logic uses proposition symbols to indicate a statement that may be true or false. We define propositional expressions as follows:
   • A propositional symbol P is a propositional expression, its value may be assigned to be either true or false.
   • AND(A,B) is a propositional expression if A and B are. It is true if both A and B are true, and false otherwise.
   • OR(A,B) is a propositional expression if A and B are. It is true if at least one of A or B is true, and false otherwise.
   • NOT(A) is a propositional expression if A is. It is true if A is false, and false otherwise.
   Do the following:
   1. Write a datatype declaration that represent propositional expressions as described above. Represent propositional symbols as strings. An example value in this type should be something like AND(OR(PROP("A"),NOT(PROP("C"))),NOT("D")).
   2. Write a function eval(exp,truthlist) that takes a propositional expression exp and a list of true proposition symbols truthlist, and determines whether the expression is true. Assume that any symbol that does not occur in the list is false. (You may find it useful to write or track down a list member function.)
   3. Write a function that simplifies propositional expressions using the equivalences NOT(NOT(A)) = A, AND(A,A) = A , and OR(B,B) = B . Be careful of input such as NOT(AND(NOT(PROP("a")),NOT(PROP("a")))) , which is not completely simplified if you take the naive approach.

Suggested exercises:

1. Rewrite the following function so that it does not use pattern matching on the marked line, but instead uses the line val x = split(cs) and obtains the components by other means.

   fun split [] = ([],[])
    |  split [a] = ([a],[])
    |  split a::b::cs = 
         let
             val (M,N) = split cs;
         in
             (a::M, b::N)
         end;
   

2. The following datatype defines a binary tree type. Write a function insert to manage the tree as a binary search tree.

   datatype 'a bintree = Empty | Leaf of 'a | Node of 'a * 'a bintree * 'a bintree;