The exercises below can be done in any order, but you should try to complete the non-optional exercises if you can before the deadline. Sections containing mandatory exercises are indicated in blue, sections containing optional ones in red, and sections containing a mix of both in purple.
You should not use any external libraries, but it is okay to import functions from the standard library.
Download the template file Lab4.hs, put all your solutions in this
file, and upload it to Moodle before the deadline. Make sure that you
submit a working Haskell file!
We will be using a few pre-defined monads from the standard library in this lab, as well as the list library and system random number generator. Let’s import everything here (we also turn on a GHC flag to avoid some spurious warning messages):
{-# OPTIONS_GHC -Wno-noncanonical-monad-instances #-}
import Control.Monad.State
import Control.Monad.Fail
import System.Random
import Data.ListNote you may have to install some libraries on your machine first to import these modules. On the lab machines, you can install the appropriate libraries by running the following commands from the terminal:
$ cabal update
$ cabal install --lib mtl
$ cabal install --lib randomIn class, we considered a few different evaluators for a toy language of arithmetic expressions that included numeric constants, subtraction expressions, and division expressions. Let’s recall here the Haskell data type we used to represent expressions, as well as some example expressions.
data Expr = Con Double | Sub Expr Expr | Div Expr Expr
deriving (Show,Eq)
e1 = Sub (Div (Con 2) (Con 4)) (Con 3)
e2 = Sub (Con 1) (Div (Con 2) (Con 2))
e3 = Div (Con 1) (Sub (Con 2) (Con 2))Let’s also recall the monadic version of the first error-handling
evaluator, which runs in the Maybe monad in order to handle
division-by-zero errors. (This evaluator is called eval1'
in the slides, but we have renamed it below.)
evalSafe :: Expr -> Maybe Double
evalSafe (Con c) = return c
evalSafe (Sub e1 e2) =
evalSafe e1 >>= \x1 ->
evalSafe e2 >>= \x2 ->
return (x1 - x2)
evalSafe (Div e1 e2) =
evalSafe e1 >>= \x1 ->
evalSafe e2 >>= \x2 ->
if x2 /= 0 then return (x1 / x2) else NothingAs a warmup exercise, rewrite evalSafe using “do
notation” (as seen in class, and also explained here).
-- Exercise 1a
evalSafe :: Expr -> Maybe Double
evalSafe = undefinedThe Maybe monad is not the only monad that can be used for error-handling. In fact, the Haskell standard library defines a type class for such monads:
class Monad m => MonadFail (m :: * -> *) where
fail :: String -> m aIn other words, an instance of MonadFail is a monad m
that supports a polymorphic operation “fail” taking a string as argument
and returning a value of type m a, for any
a.
The Maybe monad provides an instance of MonadFail, where the fail operation simply ignores its string argument:
instance MonadFail Maybe where
fail s = NothingOther instances of MonadFail include the List monad (with
fail s = []) and the IO monad (raising an exception). We
can witness this behavior for ourselves by running the fail
command in the interpreter, with different type annotations added to
invoke different instances of the MonadFail class.
ghci> fail "bad!"
*** Exception: user error (bad!)
ghci> fail "bad!" :: Maybe Int
Nothing
ghci> fail "bad!" :: [Int]
[]Rewrite evalSafe again so that it works with any monad
that is an instance of MonadFail, calling the fail
operation with a sensible error message in the case of
division-by-zero.
-- Exercise 1b
evalSafeMF :: MonadFail m => Expr -> m Double
evalSafeMF = undefinedThen try running it in a few different monads on a few different expressions and see what kind of output it gives you. Record what you see as a comment.
{- different outputs of evalSafeMF ... -}(The GHC interpreter evaluates expressions in the IO monad by default, but you can get it to run them in different monads by including a type annotation, as we saw above.)
In class we also saw how to write an error-handling-and-stateful
evaluator, which ran in the monad StateT Int Maybe in order
to both handle division-by-zero errors and to implement the (admittedly
slightly weird) revised semantics of expressions where every third
constant is interpreted as 0, when reading the expression from left to
right. (This evaluator was called eval3' in the slides, but
again we have renamed it below.)
evalWeird :: Expr -> StateT Int Maybe Double
evalWeird (Con c) =
get >>= \n ->
put (n+1) >>= \_ ->
return (if n `mod` 3 == 2 then 0 else c)
evalWeird (Sub e1 e2) =
evalWeird e1 >>= \x1 ->
evalWeird e2 >>= \x2 ->
return (x1-x2)
evalWeird (Div e1 e2) =
evalWeird e1 >>= \x1 ->
evalWeird e2 >>= \x2 ->
if x2 /= 0 then return (x1/x2) else lift Nothing
evalWeirdTop e = runStateT (evalWeird e) 0 >>= \(x,s) -> return xAdapt the weird evaluator to implement a slightly modified (and slightly weirder) semantics of expressions, where every third constant is interpreted as 0 when reading the expression from right to left. (Hint: you do not need to modify much code! You just need to adapt the evaluator to evaluate expressions from right to left…) While you’re at it, generalize it to work with any MonadFail monad wrapped in state. Implement this revised semantics as a pair of functions below:
-- Exercise 1c
evalWeird' :: MonadFail m => Expr -> StateT Int m Double
evalWeird' = undefined
evalWeirdTop' :: MonadFail m => Expr -> m Double
evalWeirdTop' = undefinedFor example, you should recover the following interpretations:
> evalWeirdTop' e1
-3.0
> evalWeirdTop' (Sub e1 (Con 0)) :: Maybe Double
NothingSometimes monads are useful even when they do not necessarily correspond in an obvious way to a notion of computation.
Consider the following data type of binary trees with labelled leaves (similar to the data type of binary trees we saw in Lectures 1 and 2, but with the labels shifted from nodes to leaves).
data Bin a = L a | B (Bin a) (Bin a)
deriving (Show,Eq)Let’s begin by establishing that the Bin type constructor is a functor. Indeed, we can define an operation of mapping a function over a binary tree analogous to the map operation on lists, and use it as the fmap operation of the Functor class:
mapBin :: (a -> b) -> Bin a -> Bin b
mapBin f (L x) = L (f x)
mapBin f (B tL tR) = B (mapBin f tL) (mapBin f tR)
instance Functor Bin where
fmap = mapBinProve that Bin really is a functor in the full sense of the word by proving that mapBin satisfies the functor laws:
mapBin id t = t
mapBin (f . g) t = mapBin f (mapBin g t)
for all binary trees t :: Bin a and functions
f :: b -> c and g :: a -> b. (You will
probably want to use a proof by structural induction on trees.)
-- Exercise 2a
{- Your proof goes here -}Now we will establish that Bin is a monad. To that end, first we have to describe how to define the monadic return and “bind” operations, which in this case will correspond to operations of the following types:
return :: a -> Bin a
(>>=) :: Bin a -> (a -> Bin b) -> Bin bIn other words, return takes a value and constructs a
tree, while (>>=) takes a tree and a function from
values to trees, and builds a tree.
Moreover, to show that we really have a monad, we need to show that these operations satisfy the monad laws
return x >>= f = f x
t >>= return = t
(t >>= f) >>= g = t >>= (\x -> (f x >>= g))for all values x :: a, binary trees
t :: Bin a, and functions f :: a -> Bin b
and g :: b -> Bin c.
Define an appropriate instance of the Monad class for Bin:
-- Exercise 2b
instance Monad Bin where
return = undefined
(>>=) = undefinedThe meaning of “appropriate instance” is left up to you to figure out, but the polymorphic types of return and bind do not leave very many natural possibilities for writing them. Moreover, your implementation should satisfy the monad laws, even if you do not prove that formally in the optional exercise below!
Note that Monad
is a superclass of Applicative,
so to define a Monad instance you also need to define an instance of
Applicative by implementing the operations
pure :: a -> m a and
(<*>) :: m (a -> b) -> m a -> m b. However,
there is a standard way of deriving an instance of Applicative from an
instance of Monad, as shown in the boilerplate code below:
instance Applicative Bin where
pure = return
fm <*> xm = fm >>= \f -> xm >>= return . fProve that the operations you defined above satisfy the monad laws.
-- Exercise 2c (optional)
{- Your proof goes here -}Can values of the monadic type Bin a be seen as
describing effectful computations in some sense? Think about it, and if
you eventually find any inspiration (perhaps after completing the other
exercises), write down your thoughts below.
-- Exercise 2d (optional)
{- Your thoughts go here -}For the following exercises, we introduce our own type class extending the Monad class:
class Monad m => SelectMonad m where
select :: [a] -> m aOur intuition is that a “selection monad” is a monad that supports an operation of selecting among a list of values, typically in a non-deterministic or probabilistic way.
An easy example is the List monad [], where
select is simply implemented as the identity function:
instance SelectMonad [] where
select = idWe can think of the List monad as simulating a non-deterministic selection by trying all possible choices.
Another example is provided by the IO monad, where we call the system random number generator to pick one of the elements (the list must be non-empty or the selection fails):
instance SelectMonad IO where
select xs
| not (null xs) = do i <- getStdRandom (randomR (0, length xs-1))
return (xs !! i)
| otherwise = fail "cannot select from empty list"Finally, the monad of probability distributions provides another interesting example that we will develop here. Formally, the monad itself is defined similarly to the List monad, but where computations are represented as lists of value-probability pairs, rather than simply lists of values:
newtype Dist a = Dist { dist :: [(a,Rational)] } deriving (Show)
instance Monad Dist where
return x = Dist [(x,1)]
xm >>= f = Dist [(y,p*q) | (x,p) <- dist xm, (y,q) <- dist (f x)]Observe that return x creates a deterministic
probability distribution (sometimes called a Dirac
distribution) that always (i.e., with probability 1) returns the
value x. The definition of the bind operator
xm >>= f may be understood as follows: if
xm :: Dist a describes a distribution on as
and f :: a -> Dist b describes a family of distributions
f x :: Dist b conditioned on the value x :: a,
then xm >>= f defines a single distribution on
bs by weighting each f x according to the
probability of x assigned by xm.
Non-deterministic selection in the distributions monad may be implemented by taking the uniform distribution on a (non-empty) list of values:
instance SelectMonad Dist where
select xs
| not (null xs) = let n = length xs in Dist [(x, 1 / fromIntegral n) | x <- xs]
| otherwise = error "cannot select uniformly from an empty list"To complete the definition of the distributions monad we also add the following standard boilerplate to derive instances of the Functor and Applicative type classes, from the Monad instance above:
instance Functor Dist where
fmap f xm = xm >>= return . f
instance Applicative Dist where
pure = return
xm <*> ym = xm >>= \x -> ym >>= return . xNow, to illustrate these different implementations of selection monads, consider the following simple program that picks a number \(x\) between 1 and 6, and then picks a number \(y\) between 1 and \(x\), and returns their sum \(x+y\):
experiment :: SelectMonad m => m Int
experiment = do
x <- select [1..6]
y <- select [1..x]
return (x + y)Here is a sample transcript of running experiment in the
IO monad (which recall GHCi uses by default). Multiple runs
can yield different results, of course:
ghci> experiment
4
ghci> experiment
6
ghci> experiment
3Now running it using the List monad, which always returns the same long list of results:
ghci> experiment :: [Int]
[2,3,4,4,5,6,5,6,7,8,6,7,8,9,10,7,8,9,10,11,12]And finally running it using the monad of finite probability distributions, which again always returns the same distribution:
ghci> experiment :: Dist Int
Dist {dist = [(2,1 % 6),(3,1 % 12),(4,1 % 12),(4,1 % 18),(5,1 % 18),(6,1 % 18),(5,1 % 24),(6,1 % 24),(7,1 % 24),(8,1 % 24),(6,1 % 30),(7,1 % 30),(8,1 % 30),(9,1 % 30),(10,1 % 30),(7,1 % 36),(8,1 % 36),(9,1 % 36),(10,1 % 36),(11,1 % 36),(12,1 % 36)]}Notice that our representation of finite probability distributions
allows the same value to occur multiple times in the list of
value/probability pairs. We can normalize distributions to get rid of
multiple occurrences as follows. First, we write a function to compute
the total probability of a value occurring in a given distribution (here
we have to assume that it is a distribution over an Eq
type!):
prob :: Eq a => Dist a -> a -> Rational
prob xm x = sum [p | (y,p) <- dist xm, x == y]Then we normalize a distribution by first computing the list of values in its support, and then returning the probabilities of all those values:
normalize :: Eq a => Dist a -> Dist a
normalize xm = Dist [(x,prob xm x) | x <- support xm]
where
support :: Eq a => Dist a -> [a]
support xm = nub [x | (x,p) <- dist xm, p > 0] -- "nub", defined in Data.List, removes duplicatesHere is the normalized result of the experiment:
ghci> normalize experiment
Dist {dist = [(2,1 % 6),(3,1 % 12),(4,5 % 36),(5,7 % 72),(6,47 % 360),(7,37 % 360),(8,37 % 360),(9,11 % 180),(10,11 % 180),(11,1 % 36),(12,1 % 36)]}(We didn’t need to put any type annotations here, since the type
Dist Int is automatically inferred from the types of
normalize and experiment.)
From looking at the normalized distribution, we see for example that 2 is the most likely value to be returned from the experiment, with probability 1/6, while 11 and 12 are both equally least likely with probability 1/36. Note that these are the exact probabilities, not the result of any simulation!
Using the SelectMonad class, write a function that “flips a coin” by
selecting a boolean value True or False.
-- Exercise 3a
coin :: SelectMonad m => m Bool
coin = undefinedThen use that to write a function that selects an arbitrary subset of elements of a list.
-- Exercise 3b
subset :: SelectMonad m => [a] -> m [a]
subset = undefined(The elements of the subset may be listed in any order, and if the input list contains duplicates it is okay for the output list to contain duplicates as well.)
You should see results roughly like the following (the first two results will probably be different):
ghci> subset [1..3]
[3]
ghci> subset [1..3]
[1,3]
ghci> subset [1..3] :: [[Int]]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
ghci> normalize (subset [1..3])
Dist {dist = [([],1 % 8),([1],1 % 8),([2],1 % 8),([1,2],1 % 8),([3],1 % 8),([1,3],1 % 8),([2,3],1 % 8),([1,2,3],1 % 8)]}Write a function which takes a monadic computation of a boolean and
runs it repeatedly, returning how many times it evaluates to
True.
-- Exercise 3c
simulate :: Monad m => Int -> m Bool -> m Int
simulate = undefinedNote that the type of simulate indicates that it should
work with an arbitrary monad, not just a selection monad.
Here are some more precise requirements:
simulate n bm should run without error for any
non-negative integer n (for n < 0 it can do
anything)m = IO,
simulate n bm should run in time proportional to
nm = Dist,
prob (simulate n bm) k should give the exact probability
that if the experiment bm is repeated n times,
it will return True exactly k times.Examples:
ghci> simulate 100000 coin
49932
ghci> simulate 10000 (subset ['a'..'z'] >>= \xs -> return (elem 'a' xs && elem 'b' xs))
2492
ghci> normalize (simulate 3 coin)
Dist {dist = [(3,1 % 8),(2,3 % 8),(1,3 % 8),(0,1 % 8)]}>Rémy’s algorithm is an elegant iterative algorithm for generating random binary trees, where each binary tree of a given size is generated with the same probability. In other words, it is a uniform generator for binary trees with a given number of nodes/leaves.
The algorithm for generating a binary tree with n nodes and n+1 leaves can be described as follows:
Begin by creating a single-leaf tree.
Then perform n iterations of the following “growth” procedure on the current binary tree t:
Here is a little animation of running Rémy’s algorithm to generate a random binary tree with 50 leaves (followed by running the algorithm in reverse to deconstruct the tree):
Observe that as we grow new leaves, we also label them in the order of creation.
Implement Rémy’s algorithm as a function
-- Exercise 3d (optional)
genTree :: SelectMonad m => [a] -> m (Bin a)
genTree = undefinedthat generates a binary tree with a given list of leaf labels.
More precise requirements:
genTree xs should run without error for any non-empty
list xs :: [a] (the behavior on the empty list is
undefined)m = IO,
genTree xs should return a binary tree whose canopy of
leaves is a permutation of xs, in time at worst quadratic
in the length of xsm = [],
genTree xs :: [Bin a] should compute the list of all
possible binary trees whose canopy is a permutation of xs,
without duplicatesm = Dist,
genTree xs :: Dist (Bin a) should give the uniform
distribution on all possible binary trees whose canopy is a permutation
of xs.Examples:
> genTree [1,2] :: [Bin Int]
[B (L 1) (L 2),B (L 2) (L 1)]
> normalize (genTree [1..3])
Dist {dist = [(B (L 1) (B (L 2) (L 3)),1 % 12),(B (B (L 2) (L 3)) (L 1),1 % 12),(B (B (L 1) (L 2)) (L 3),1 % 12),(B (B (L 2) (L 1)) (L 3),1 % 12),(B (L 2) (B (L 1) (L 3)),1 % 12),(B (L 2) (B (L 3) (L 1)),1 % 12),(B (L 1) (B (L 3) (L 2)),1 % 12),(B (B (L 3) (L 2)) (L 1),1 % 12),(B (B (L 1) (L 3)) (L 2),1 % 12),(B (B (L 3) (L 1)) (L 2),1 % 12),(B (L 3) (B (L 1) (L 2)),1 % 12),(B (L 3) (B (L 2) (L 1)),1 % 12)]}
> prob (genTree [1..4]) (B (L 3) (B (B (L 1) (L 4)) (L 2)))
1 % 120
> prob (genTree [1..4]) (B (B (L 4) (L 1)) (B (L 2) (L 3)))
1 % 120
> genTree [1..50]
B (B (B (B (L 41) (L 43)) (B (B (L 46) (L 38)) (L 39))) (B (B (B (L 1) (L 29)) (B (L 36) (L 21))) (B (B (L 22) (L 47)) (B (L 9) (B (B (L 34) (L 48)) (B (B (B (B (L 13) (L 14)) (L 16)) (L 37)) (B (L 11) (B (B (L 6) (L 44)) (B (L 8) (B (B (B (L 49) (B (L 45) (B (B (L 4) (B (L 28) (B (B (L 24) (B (B (L 23) (L 12)) (B (B (L 2) (B (L 18) (L 19))) (B (L 33) (L 3))))) (L 7)))) (B (L 26) (B (L 40) (B (B (B (L 15) (L 32)) (L 31)) (L 27))))))) (L 5)) (L 35))))))))))) (B (B (B (L 25) (B (B (B (L 42) (L 50)) (L 20)) (L 10))) (L 30)) (L 17))