12/08/2020 Exercise (Week 7)
Exercise (Week 7)
DUE: Wed 22 July 2020 15:00:00 CSE
Stack
Download the exercise tarball and extract it to a directory on your local machine. This tarball contains a le, called Ex05.hs , wherein you will do all of your programming.
To test your code, run the following shell commands to open a GHCi session:
$ stack repl
Configuring GHCi with the following packages: Ex05
Using main module: 1. Package ‘Ex05′ component exe:Ex05 …
GHCi, version 8.2.2: http://www.haskell.org/ghc/ 😕 for help
[1 of 2] Compiling Ex05 (Ex05.hs, interpreted)
[2 of 2] Compiling Main (Main.hs, interpreted)
Ok, two modules loaded.
*Main Ex05> calculate “1 1 +”
…
Note that you will only need to submit Ex05.hs , so only make changes to that le.
Reverse Polish Notation
The is a common way to represent arithmetic expressions, where each operator appears after the operands it works on. Below are a number of examples in a sample GHCi session. Your task in this exercise is to develop a RPN calculator using a variety of monadic functions. You should be able to evaluate the same examples to the same results after you have completed this exercise:
Reverse Polish Notation Reverse Polish Notation
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/exercise.html
1/5
12/08/2020 Exercise (Week 7)
Generally, evaluation of RPN proceeds by looking at each token (number or operator), one at a time. We evaluate a number by pushing it on to a stack, and we evaluate an operator o by popping two numbers y and x from the stack, and pushing o x y back on. The number left on the top of the stack at the end of evaluating is the result of the expression.
Parsing (1 Mark)
We de ne a Token as either a number or a binary operator:
First, we need a way to translate String values into proper calculable expressions, that is, lists of Token . We have already de ned a function that will attempt to convert a single word into a single Token , called parseToken :
data Token = Number Int | Operator (Int -> Int -> Int)
parseToken :: String -> Maybe Token
parseToken “+” = Just (Operator (+))
parseToken “-” = Just (Operator (-))
parseToken “/” = Just (Operator div)
parseToken “*” = Just (Operator (*))
parseToken str = fmap Number (readMaybe str)
Your rst task is to implement the function tokenise :
This function must break the string into words (the built-in words function will be useful), and then attempt to parse each one into a Token , returning a non- Nothing result only if every word can be parsed.
tokenise :: String -> Maybe [Token]
*Ex05> calculate “3 4 +”
Just 7
*Ex05> calculate “3 4 – 5 +”
Just 4
*Ex05> calculate “3 4 2 / *”
Just 6
*Ex05> calculate “3 4 2 / * +”
Nothing
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/exercise.html
2/5
12/08/2020 Exercise (Week 7)
Note that you can (and should) exploit the fact that is an instance of , Applicative and Functor . This will enable you to make the above function into a
short, one-line de nition.
Stack Operations (2 Marks)
Next, in order to evaluate RPN expressions, we need a convenient way to model computations which manipulate a stack, and can possibly fail (for example, if we were to try to pop from an empty stack).
In Haskell, such a computation could be modelled as a function that, given an input stack (of Int ), will either fail (returning Nothing ) or return Just an output stack with an additional return value.
Implement the two basic stack operations, push and pop as Calc computations.
Evaluating (3 Marks)
We have provided instances of Monad , Applicative and Functor for Calc :
newtype Calc a = C ([Int] -> Maybe ([Int], a))
pop :: Calc Int
push :: Int -> Calc ()
Maybe
Monad
instance Functor Calc where
fmap f (C sa) = C $ \s ->
case sa s of
Nothing -> Nothing
Just (s’, a) -> Just (s’, f a)
instance Applicative Calc where
pure x = C (\s -> Just (s,x))
C sf <*> C sx = C $ \s ->
case sf s of
Nothing -> Nothing
Just (s’,f) -> case sx s’ of
Nothing -> Nothing
Just (s”,x) -> Just (s”, f x)
instance Monad Calc where
return = pure
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/exercise.html
3/5
12/08/2020 Exercise (Week 7)
All three instances make sure that the whole computation will return if any subcomputation returns Nothing . Furthermore, the Applicative and
instances allow us to thread the stack through multiple computations without manually keeping track of this state. For example, the Calc computation that adds the two topmost elements of the stack and pushes the result back to the stack can be de ned as:
Nothing
Monad
addTwo :: Calc ()
addTwo = do
x <- pop
y <- pop
push (x + y)
By threading the stack through in the Monad instance here, we can just treat the stack as some implicit state that we manipulate abstractly with Calc computations. This allows us to make code much shorter and cleaner.
Using the above instances for Calc , de ne a function evaluate :
This should evaluate a list of Token as described above, using the stack operations you de ned earlier, nally returning the topmost element of the stack.
Putting it together (1 Mark)
Lastly, de ne a function calculate :
That will rst attempt to parse the given string with to get a list of tokens. If that succeeds, it should use evaluate to get a computation corresponding to that list of tokens. Then, it should run that computation starting with an empty stack, returning just the resultant integer from that computation, if any. If the stack has more than one element when calculate runs, it should return the topmost element.
evaluate :: [Token] -> Calc Int
calculate :: String -> Maybe Int
tokenise
Calc
C sa >>= f = C $ \s ->
case sa s of
Nothing -> Nothing
Just (s’,a) -> unwrapCalc (f a) s’
where unwrapCalc (C a) = a
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/exercise.html
4/5
12/08/2020 Exercise (Week 7)
Note that once again you can use the , and instances of Maybe to succinctly implement this function.
After implementing this function, test it with the examples listed at the beginning of this exercise, and try your own examples also.
You can submit your exercise by typing:
on a CSE terminal, or by using the give web interface. Your le must be named Ex05.hs (case-sensitive!). A dry-run test will partially autotest your solution at
submission time. To get full marks, you will need to perform further testing yourself.
Monad
Applicative
Functor
$ give cs3141 Ex05 Ex05.hs
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/exercise.html
5/5