----------------------------------------------------------------------

Module:         COMP2003 Advanced Functional Programming
School:         Computer Science, University of Nottingham
Lecturer:       Graham Hutton
Level:          2
Semester:       Spring
Year:           22-23

----------------------------------------------------------------------

QUESTION 1:

a) instance Functor List where
      -- fmap :: (a -> b) -> List a -> List b
      fmap f Nil         = Nil
      fmap f (Cons x xs) = Cons (f x) (fmap f xs)

b) append Nil         ys = ys
   append (Cons x xs) ys = Cons x (append xs ys)

c) instance Applicative List where
      -- pure :: a -> List a
      pure x = Cons x Nil

      -- (<*>) :: List (a -> b) -> List a -> List b
      Nil         <*> _  = Nil
      (Cons f fs) <*> xs = append (fmap f xs) (fs <*> xs)

   instance Monad List where
      -- return :: a -> List a
      return x = pure x

      -- (>>=) :: List a -> (a -> List b) -> List b
      Nil >>= _         = Nil
      (Cons x xs) >>= f = append (f x) (xs >>= f)

d) replace Nil         n = (Nil, n)
   replace (Cons x xs) n = (Cons n xs', n')
                           where
                              (xs',n') = replace xs (n+1)

e) fresh :: ST Int
   fresh = S (\s -> (s, s+1))

   replace' :: List a -> ST (List Int)
   replace' Nil         = return Nil
   replace' (Cons x xs) = do x'  <- fresh
                             xs' <- replace' xs
                             return (Cons x' xs')

----------------------------------------------------------------------

QUESTION 2:

a) leaves :: Tree -> Int
   leaves (Leaf _)   = 1
   leaves (Node l r) = leaves l + leaves r

   nodes :: Tree -> Int
   nodes (Leaf _)   = 0
   nodes (Node l r) = 1 + nodes l + nodes r

b) Base case:

        nodes (Leaf n) + 1
      =   applying nodes
        0 + 1
      =   applying +
        1
      =   unapplying leaves
        leaves (Leaf n)

   Inductive case:

        nodes (Node l r) + 1
      =   applying nodes
        1 + nodes l + nodes r + 1
      =   arithmetic
        (nodes l + 1) + (nodes r + 1)
      =   induction hypotheses
        leaves l + leaves r
      =   unapplying leaves
        leaves (Node l r)

c) Base case:

     map f (map g (Leaf x)
   =    applying map
     map f (Leaf (g x))
   =    applying map
     Leaf (f (g x))
   =    unapplying .
     Leaf ((f.g) x)
   =    unapplying map
     map (f.g) (Leaf x)
   
   Inductive case:
   
     map f (map g (Node l r))
   =    applying map
     map f (Node (map g l) (map g r))
   =    applying map
     Node (map f (map g l)) (map f (map g r))
   =    induction hypotheses
     Node (map (f.g) l) (map (f.g) r)
   =    unapplying map
     map (f.g) (Node l r)

d) Base case:

     replicate Zero x
   =    specification
     take Zero (repeat x)
   =    applying take
     []

   Inductive case:

     replicate (Succ n) x
   =    specification
     take (Succ n) (repeat x)
   =    applying repeat
     take (Succ n) (x : repeat x)
   =    applying take
     x : take n (repeat x)
   =    induction hypothesis
     x : replicate n x
   
   Hence, we have calculated:
   
   replicate Zero     x = []
   replicate (Succ n) x = x : replicate n x

----------------------------------------------------------------------

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 use of the >>= operator is clearly explained.

Consider the following type of expressions that are built up from 
integer values using a division operator:

   data Expr = Val Int | Div Expr Expr

Such expressions can be evaluated as follows:

   eval :: Expr -> Int
   eval (Val n)   = n
   eval (Div x y) = eval x `div` eval y

However, this function does not take account of the possibility of
division by zero, and will produce an error in this case.  To address
this, we can use the Maybe type to define a safe version of division
that returns Nothing when the second argument is zero,

   safediv :: Int -> Int -> Maybe Int
   safediv _ 0 = Nothing
   safediv n m = Just (n `div` m)

and modify our evaluator to explicitly handle the possibility of
failure when the function is called recursively:

   eval :: Expr -> Maybe Int
   eval (Val n)   = Just n
   eval (Div x y) = case eval x of
                       Nothing -> Nothing
                       Just n  -> case eval y of
                                     Nothing -> Nothing
                                     Just m  -> safediv n m

The new definition for eval resolves the division by zero issue,
but is rather verbose.  To write eval in a simpler manner, we
can observe the common pattern that occurs twice in its definition,
namely performing a case analysis on a Maybe value, mapping Nothing
to itself and Just x to some result depending on x.  Abstracting out
this pattern gives a new operator >>= that is defined as follows:

   (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
   mx >>= f = case mx of
                 Nothing -> Nothing
                 Just x  -> f x

Using the >>= operator and the lambda notation, we can now redefine
the function eval in a more compact manner as follows:

   eval :: Expr -> Maybe Int
   eval (Val n)   = Just n
   eval (Div x y) = eval x >>= \n ->
                    eval y >>= \m ->
                    safediv n m

The case for division states that we first evaluate x and call
its result value n, then evaluate y and call its result value m,
and finally combine the two results by applying safediv.

Using the >>= operator in the above definition ensures that the
division case only succeeds if every component in this case succeeds.
Moreover, we no longer have to worry about handling the possibility
of failure at any point in the definition, as this is handled
automatically by the definition of the >>= operator.

In conclusion, the >>= operator captures a common pattern of failure
management, and allows us to focus on the successful cases when we
are defining functions, with the detection and propagation of 
failure being handled automatically by the >>= operator.

----------------------------------------------------------------------