QUESTION 1:
a) instance Functor Result where
— fmap :: (a -> b) -> Result a -> Result b
fmap f (OK x) = OK (f x)
fmap f (ERROR xs) = ERROR xs
That is, mapping a function f over an OK value simply applies
the function to the underlying value, while applying f to an
ERROR string simply propogates the message.
b) instance Applicative Result where
— pure :: a -> Result a
pure x = OK x
— (<*>) :: Result (a -> b) -> Result a -> Result b
(OK g) <*> rx = fmap g rx
(ERROR xs) <*> _ = ERROR xs
The <*> operator can also be defined by
(OK g) <*> (OK x) = OK (g x)
(OK g) <*> (ERROR xs) = ERROR xs
(ERROR xs) <*> _ = ERROR xs
The applicative style for Result supports a form of erroneous
programming in which we can apply pure functions to arguments
that may fail with an error message. For example:
> pure (+) <*> OK 1 <*> OK 2
> pure (+) <*> ERROR “bang” <*> OK 2
ERROR “bang”
c) Only the first error message is returned. For example:
> pure (+) <*> ERROR “bang” <*> ERROR “boom”
ERROR “bang”
d) pure g <*> pure x
= applying pure
(OK g) <*> (OK x)
= applying <*>
fmap g (OK x)
= applying map
= unapplying pure
pure (g x)
This property states that if there are no error messages involved,
then <*> behaves like normal function application.
e) sumeven :: [Int] -> Result Int
sumeven [] = OK 0
sumeven (n:ns) | odd n = ERROR “odd number”
| even n = case sumeven ns of
ERROR xs -> ERROR xs
OK m -> OK (n+m)
f) sumeven :: [Int] -> Result Int
sumeven [] = return 0
sumeven (n:ns) | odd n = ERROR “odd number”
| even n = do m <- sumeven ns
return (n+m)
g) fmap g mx >>= f
= applying fmap
(mx >>= (return . g)) >>= f
= associativity law
mx >>= (\x -> (return . g) x >>= f)
= applying .
mx >>= (\x -> return (g x) >>= f)
= return law
mx >>= (\x -> f (g x))
= composition
mx >>= (f.g)
———————————————————————-
QUESTION 2:
a) False
= unapplying isEmpty
isEmpty []
= applying isEmpty
This is incorrect reasoning because the order in which equations
are defined is important. In particular, the second equation
isEmpty xs = False only applies when the list is non-empty, as
the empty case is already covered by the first equation isEmpty
[] = True. Hence the first step in the above proof is incorrect.
b) Base case:
map f (map g [])
= applying map
= applying map
= unapplying map
map (f.g) []
Inductive case:
map f (map g (x:xs))
= applying map
map f (g x : map g xs)
= applying map
f (g x) : map f (map g xs)
= induction hypothesis
f (g x) : map (f.g) xs
= unapplying .
(f.g) x : map (f.g) xs
= unapplying map
map (f.g) (x:xs)
c) Base case:
mirror (mirror (Leaf x))
= applying mirror
mirror (Leaf x)
= applying mirror
Inductive case:
mirror (mirror (Node l r))
= applying mirror
mirror (Node (mirror r) (mirror l))
= applying mirror
Node (mirror (mirror l)) (mirror (mirror r))
= induction hypotheses
d) mult [2,3,4]
= 2 * mult [3,4]
= 2 * (3 * mult [4])
= 2 * (3 * (4 * mult []))
= 2 * (3 * (4 * 1))
= 2 * (3 * 4)
None of the multiplications can be performed until the end of the
list is reached, and hence evaluation takes linear space.
e) Base case:
mult’ n []
= specification
n * mult []
= applying mult
= arithmetic
Inductive case:
mult’ n (x:xs)
= specification
n * mult (x:xs)
= applying mult
n * (x * mult xs)
= arithmetic
(n * x) * mult xs
= induction hypothesis
mult’ (n * x) xs
Resulting definition:
mult’ n [] = n
mult’ n (x:xs) = mult’ (n*x) xs
f) mult [2,3,4]
= mult’ 1 [2,3,4]
= mult’ (1*2) [3,4]
= mult’ 2 [3,4]
= mult’ (2*3) [4]
= mult’ 6 [4]
= mult’ (6*4) []
= mult’ 24 []
(Other evaluation sequences are possible too.)
The multiplications can now be performed incrementally as the
list is consumed, resulting in constant space usage.
———————————————————————-
QUESTION 3:
> The following example essay illustrates the kind of points that
> students are expected to cover. However, students are free to
> answer the question in any way that they please, provided that
> the key definitions and ideas are explained clearly.
Consider the problem of writing functions that manipulate some
form of state that can be changed over time. The kind of state
we are manipulating is not important for our purposes here, so
we leave the details of the state type unspecified:
type State = …
The most basic form of function on this type is a state
transformer, abbreviated by ST, which takes an input state
as its argument and produces an output state as its result,
in which the output state reflects any updates that were made
to the state by the function during its execution:
type ST = State -> State
In general, however, we may wish to return a result value in
addition to up-dating the state. For this reason, we generalise
the type of state transformers to also return a result value,
with the type of such values being a parameter of the ST type:
type ST a = State -> (a, State)
It is also convenient to think of such functions in pictorial
form as follows, where s is the input state, s’ is the output
state, and v is the result value:
+——-+ v
| |——>
——-| |——>
s +——-+ s
In order to make the parameterised type ST into a monad, we
need to define two primitive functions. The first of these,
return, can be defined as follows:
return :: a -> ST a
return x = \s -> (x,s)
That is, return converts a value into a state transformer that
simply returns that value without modifying the state.
x +——-+ x
——-|——-|——>
——-|——-|——>
s +——-+ s
The second function, >>=, can be defined as follows:
(>>=) :: ST a -> (a -> ST b) -> ST b
st >>= f = \s -> let (x,s’) = st s in f x s’
That is, >>= provides a means of sequencing state transformers:
st >>= f applies the state transformer st to an initial state
s, then applies the function f to the resulting value x to
give a second state transformer (f x), which is then applied
to the modified state s’ to give the final result.
+——-+ x +——-+
s | | —–> | | —–>
—–> | st | | f |
| | —–> | | —–>
+——-+ s’ +——-+
In this manner, the >>= function for the state monad integrates
the sequencing of state transformers with the processing of
their result values. Note that within the definition for >>=
we produce a new state transformer f x whose behaviour may
depend on the result value of the first argument x, which means
that the pattern of computation can change depending on x.
———————————————————————-