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))
fun parse(exp:string):AST
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 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 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.
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 = ...
In
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 [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]])
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