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:
5 * 3 + 16 / 7 6 - *
Which corresponds to the infix expression:
* 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 - - *
corresponds to the infix expression:
(~Ln(Exp(3)+4) – 12)*(5-(4-3))
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
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 2In the following order:
6 5 Minus 4 Plus 3 2 Neg Minus Times.
In part 3
you will apply the tool you built in part 2 to the structure you
designed in part 1. Write a function
that evaluates a given
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.
The tree in the example from the last problem should evaluate to 25.
to apply a given function to its argument
times using the two auxiliary functions
You must use twice and thrice, and you may assume
>= 2 as
Your solution should recurse at most logarithmically with the size of
n, a function
f n times directly will be marked as incorrect.
twice f a = f (f a)
fun thrice f a = f (f (f a))
fun nice f a n = ...
each subproblem, specify what function and accumulator to pass into
foldl to produce
the desired result given an integer list as input.
[1, 2, 3, 4, 5], the answer would be
Use the substitution model to show the evaluation of the following code segments:
~(19 - 3) div 2
(hd (tl [1, 2, 3, 4]))::
(fn x => fn y => y x) 3 f
let val x = 2 + 2 val y = fn z => x+z val z = y x in (fn x => (y z) + x) x end