## Homework 3

Due: 4 February 2002 by 11:59:59 pm

```(* Name: <your name here> *)
(* PID: <your pid here>   *)
(* Homework 3                *)
```
Also, precede each solution with the corresponding exercise number in comments. At the moment the plan is for the gta to grade the solutions by hand.

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;
```