[SOLVED] Assignment 4: state monad and imperative programming csc324h1

Task 1: State Monad 30 pts
Recall that during the lecture, we discussed the WCounter monad, which keeps track
of a counter.
Here, we generalize the concept of a counter to a more general state. We make the
state type s a parameter of the State monad.
newtype State s a = State {runState :: s -> (a, s)}
Intuitively, State s is a wrapper over type a that carries a state of type s.
It represents a stateful computation that takes an initial state of type s and returns
a result of type a along with a final state of type s. We can treat the state s as some
state context that threads through the computation.
Given a State monad, we run it by providing an initial state and extracting the
result and the final state. Sometimes, you may only care about the result and ignore
the final state. Let’s define a helper function evalState that does this.
evalState :: State s a -> s -> a
evalState (State f) s = fst (f s)
(a) get and put 10 pts
Now, let’s define two functions get and put that allow us to interact with the state.
• get returns the current state as the result.
• put n replaces the current state with new state n, and returns ().
Define the functions get and put. You can check the provided tests to better understand the expected behaviour.
(b) Instance of Functor 10 pts
Recall that a Functor is a type class on a type constructor f that allows you to
apply a mapping to the value inside the type constructor. For State s, the mapping is
applied to the result of the computation.
Implement Functor for State s. It must satisfy the following laws:
1
• fmap id = id
• fmap (f . g) = fmap f . fmap g
(c) Instance of Applicative 10 pts
It’s intuitive that State s is a Monad. More interestingly, State s is also an instance
of a weaker type class called Applicative.
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
Intuitively,
• pure (return in Monad): wraps a value in the type constructor.
• <*>: applies a mapping wrapped in the type constructor to a value inside the type
constructor. Notice how this is similar to fmap, but the mapping itself is also
wrapped in the type constructor.
For State s,
• pure should wrap a value a in the State monad with the state unchanged.
• <*> should do something similar to fmap, but the state change of the mapping
should be taken into account.
Also, an Applicative instance must satisfy the following laws:
• pure id <*> v = v
• pure f <*> pure x = pure (f x)
• u <*> pure y = pure ($ y) <*> u
• u <*> (v <*> w) = pure (.) <*> u <*> v <*> w
Implement Applicative for State s.
Do NOT use the Monad instance to implement this, or you will receive 0 points.
Note: There are more than one correct implementation for this task. You can choose
any implementation that satisfies the laws.
Task 2: Imperative Programming 70 pts
The essence of imperative programming is to have a sequence of statements that
can modify the state of the program. With the State monad and do notation, we can
simulate imperative programming in Haskell.
In this task, you will define def, var, lit, while, +=, -= and *= functions that allow
you to write the following imperative style factorial function in Haskell.
2
You are free to define additional helper functions if you find them useful.
factorial :: Int -> Int
factorial n = def $ do
result <- var 1
i <- var n
while i (> 0) $ do
result *= i
i -= lit 1
return result
Goal: 25 pts if the imperative factorial function and 4 additional imperative style
function behaves correctly.
Don’t worry if you have no clue how to implement these functions. Let’s do it step
by step.
First, notice that there are two different kinds of values that we need to represent
in our imperative language: variables and literals. We can define a Value type that
represents either a variable or a literal of type a. A variable is represented by an integer
index, and a literal is just a value of type a.
data Value a = Var Int | Lit a
(a) Figure out a suitable State type 10 pts
Recall how we defined the operational semantics of lambda calculus: we have an
environment that maps variables to values. Similarly, here we need a state that maps
variable indices to values.
Define a suitable State type Ctx. You can use either data or type to define Ctx. It
has two helper functions:
• getVar that takes an index and returns the value of the variable at that index.
• emptyCtx that represents an initial state with no variables.
Hint: You need to track the next available variable index in the state, so that you
can generate fresh variables when calling var.
Note: There are no test cases for this task. It will be graded manually, meaning that
any reasonable implementation will be accepted.
(b) Define lit and var 10 pts
• lit creates a Value from a literal value.
• var creates a new variable in the state and returns a Value representing that
variable.
Hint: Don’t forget to update the state to keep track of the new variable. Use do
notation to make it easier to work with the State monad.
3
(c) Define def 10 pts
def is a helper function that takes an imperative program, runs it with an initial
state, and returns the final result.
Hint: You can use undefined as a value of any type you want, as long as you are
sure that it will never be evaluated.
(d) Define +=, -=, and *= 15 pts
These functions should modify the value of a variable in the state, and return nothing.
If the first argument is a literal, they do nothing.
For convenience, start with a helper function modifyVar that takes a mapping function f and applies it to a variable.
Note: for this task, you are free to remove modifyVar and implement +=, -=, and *=
directly if you prefer.
(e) Define while
while takes a value, a predicate function, and a body program. It runs the body
program repeatedly as long as the predicate function returns True on the value.
Hint: Informally,
while cond pred body =
(
body; while cond pred body if (pred cond)
() if not (pred cond)
Note: Completing this task does not guarantee any points. However, skipping this
task will make the factorial function fail.
Submission and Instructions
Submit the file A4.hs to Markus. Make sure to complete all sections labeled “undefined” in A4.hs.
For all assignments:
• You are responsible for making sure that your code has no syntax errors or compile
errors. If your file cannot be imported in another file, you may receive a grade of
zero.
• If you’re not intending to complete one of the functions, do not remove the function
signature. If you are including a partial solution, make sure it doesn’t cause a
compile error. If your partial solution causes compiles errors, it’s better to comment
out your solution (but not the signature).
• Do not modify the (provide …) (in Racket) and module (…) where (in
Haskell) lines of your code. These lines are crucial for your code to pass the tests.