Problem Set 2 — Folding, Currying, and Datatypes, Oh My!

Due February 12, 2007.

Part 1

In this part you must define a datatype and write a function to construct an instance of one based on some input. The datatype will be an Abstract Syntax Tree and the input will be a simple arithmetic expression. You must parse the expression in postfix notation which will include integers, and arithmetic and exponential operators, then return an AST corresponding to that expression. The types of operators in our expressions will be Plus, Minus, Times, Divide (Binary operators), Ln, Exp, Neg (Unary operators, where Ln is the natural logarithm, Exp signifies Euler's exponential function, and Neg is the negation operator). Use the following datatypes in your solution.

datatype BinaryOp = Plus | Minus | Times | Divide
datatype UnaryOp = Ln | Exp | Neg
datatype Terminal = Int of int
datatype AST = Empty
(* Define your AST using above datatypes here *)


(* The Empty value above is a dummy definition           *)
(* please construct new values using the datatypes above *)
(* when implementing your Abstract Syntax Tree           *)

Here is an example of a simple input expression:

14 5 * 3 + 16 / 7 6 - *

Which corresponds to the infix expression:

(((14 * 5) + 3) / 16) * (7 - 6) (note the order for non commutative operations like subtraction)

Here is another example with unary operators as well as binary operators:

3 Exp 4 + Ln Neg 12 - 5 4 3 - - *

which corresponds to the infix expression:

(~Ln(Exp(3)+4) – 12)*(5-(4-3))

The function to construct the AST will have the following signature:
fun parse(exp:string):AST

Part 2

Now we ask you to write a general function to fold over the AST defined above with the following signature:

fun foldt (f:(AST * 'a)->'a) (a:'a) (t:AST):'a

This function should behave in all respects like the functions foldl and foldr with which we are already familiar. You should use a post-order traversal of the tree to serialize its elements, reflecting the postfix syntax of our simple language for arithmetic expressions. For example, foldt would apply its argument function to the elements of this AST

          Times
        /       \
      Plus      Minus
     /    \    /     \
  Minus    4  3      Neg
 /    \               |
6      5              2
In the following order: 6 5 Minus 4 Plus 3 2 Neg Minus Times.

Part 3

In part 3 you will apply the tool you built in part 2 to the structure you designed in part 1. Write a function eval using foldt that evaluates a given AST to a single integer value based on the rules of arithmetic. Do not concern yourself with the correctness of the input, assume it is of the proper form.

fun eval(a:AST):int

The tree in the example from the last problem should evaluate to 25.

Part 4a

Write a function nice to apply a given function to its argument n times using the two auxiliary functions twice and thrice. You must use twice and thrice, and you may assume n >= 2 as a precondition. Your solution should recurse at most logarithmically with the size of n, a function simply applying f n times directly will be marked as incorrect.

fun twice  f a = f (f a)
fun thrice f a = f (f (f a))
fun nice   f a n = ...

Part 4b

In each subproblem, specify what function and accumulator to pass into foldl to produce the desired result given an integer list as input.

It is acceptable to return a tuple containing the desired answer, so long as it is the first element of the tuple.
:

i) The sum of all the elements.
ii) The product of every other element. (the first, third, fifth, seventh, ...)
iii) The sum of the factorials of the even elements. (you should only process elements that are divisible by two, their position in the list is irrelevant).
iv) The reverse of the given list.
v) Every prefix of the list. ( for the list [1, 2, 3, 4, 5], the answer would be [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]])

Part 5

Use the substitution model to show the evaluation of the following code segments:

  1. ~(19 - 3) div 2
  2. (hd (tl [1, 2, 3, 4]))::[]
  3. (fn x => fn y => y x) 3 f 
  4. let
  val x = 2 + 2
  val y = fn z => x+z
  val z = y x
in
  (fn x => (y z) + x) x
end