Haskell Programming

Background Reverse Polish Notation (RPN) and Polish Notation (PN) are alternatives to the more commonly seen inx notation for arithmetic. Unlike inx notation, RPN and PN do not require conventions regarding the order of operations. Instead, the order of evaluation is dictated by the syntax. With RPN, operands are followed by their operators and evaluated accordingly. In this assignment, we will implement an RPN interpreter similar to what you might see in an HP calculator. Here is the declaration for the language you will write the interpreter for: data Op = Val Int | Plus | Minus | Mul | IntDiv deriving (Show , Eq) type PExp = [Op] Our operators (i.e., Plus, Minus, Mul, and IntDiv) and operands are both represented by the Op type. Whole arithmetic expressions in RPN are represented as lists of operations. Evaluation for RPN works by reading a stream of inputs from front to back. If a number (i.e., Val 5) is read, it (i.e., 5) is pushed onto a stack. If any operator is read, its operands are popped o of the stack, the operation is performed with them and the result is pushed back onto the stack. The topmost value on the stack becomes the rightmost argument to an operator. For example,the input 2 5 - should evaluate to -3. Correct computations in RPN result in an empty input and a stack with only one number value. Stacks with more than one value in them at the end of evaluation result from malformed input.

3. The evaluator crashes in cases where there are bad inputs and division by zero. This isnt particularly useful for recovery purposes. We can refactor the evaluator by using the data type, Either a b, to allow us to return a valid result or a failure indicator. Note the following code:

data RPNError = DivByZero | InvalidInput deriving (Show , Eq)

data Either a b = Left a | Right b deriving (Show , Eq)

type RPNResult = Either RPNError Int

By convention, the data type, Either a b, is either the failure case (i.e., Left a) or the success case (i.e., Right b). Write a function called evalSafe, that has the type PExp -> RPNResult. Hint: you may need to dene a helper function that takes a stack and a PExp and returns an RPNResult. Use this helper function to dene evalSafe. Note: This problem will not simply encapsulate your work from Problem 2, the error function in Haskell (a hack of sorts) crashes the program and isnt catchable in a pure function.

Here are examples of how evalSafe should work: HW4*> evalSafe [Val 5, Val 0, IntDiv]

Left DivByZero

HW4*> evalSafe [IntDiv, Plus, Val 0]

Left InvalidInput

HW4*> evalSafe [Val 5, Val 1, Val 1, Plus, Mul]

Right 10