Week 14: Exercises

1. FMap from Bind

Write a function

m_fmap :: Monad m => (a -> b) -> m a -> m b

that works like fmap, but is implemented using the >>= operator.

2. Application from Bind

Write a function

m_apply :: Monad m => m (a -> b) -> m a -> m b

that works like <*>, but is implemented using the >>= operator.

3. State Monad

Haskell's Control.Monad.State module implements a monad State s a, representing a stateful computation with a state of type s, returning a value of type a. It includes these functions:

get :: State s s

Return the current state.

put :: s -> State s ()

Replace the state inside the monad.

runState :: State s a -> s -> (a, s)

Run a computation, returning its result and the final state.

Implement this monad.

4. Interpreter

Consider a simple language in which every program consists of a series of assignments, one per line. For example, here is a program:

x = 2
x = 3 + x
y = 10 + 2 * x
a = (y - 15) * 20 

In this language all values are integers, and constants are non-negative integers. Integers have the same numeric range as an Int in Haskell. Variable names consist of 1 or more lowercase letters.

Expressions may contain the operators '+', '-', '*' and '/'. All operators are left-associative. '*' and '/' have higher precedence than '+' and '-'. Any subexpression may be surrounded by parentheses. Every assignment is of the form 'var = expression'. Whitespace may appear anywhere in an input line.

Write a program that reads a program in this language and interprets it. The program should print out the final values of all variables in alphabetical order. For example:

a = 100
x = 5
y = 20