%include Haskell.fmt
%format m1
%format m2
%format m3

%if False
\begin{code}
import Test.QuickCheck
import Control.Monad (liftM)
\end{code}
%endif

\begin{question}{List Monad}{25}
The following list comprehension generates an infinite list containing infinite lists:
\begin{code}
squareList :: [[Int]]
squareList = [ [sq, sq*2 ..] | i <- [1..], let sq = i*i ]
\end{code}
This list of lists could be visualized as follows:
\begin{center}
|(1:2:3:4:...) ^^ : ^^ (4:8:12:16:...) ^^ : ^^ (9:18:27:36:...) ^^ : ^^ (16:32:48:64:...) ^^ : ^^ ...|
\end{center}
We have the |Prelude| function |concat| at our disposal to flatten this list. However, |concat squareList|
will {\it only} return elements from the first list. The function |join|, defined below, has |concat|'s type, 
but takes elements in a diagonal fashion:

\noindent\begin{minipage}{10cm}
\begin{code}
join :: [[a]] -> [a]
join = rec [] 

  where
    rec  []  []  = []
    rec  as  bs  = 
       let  notEmpty  = not . null
            (hd, tl)  = splitAt 1 bs
            rest      = hd ++ map tail as
       in map head as ++ rec (filter notEmpty rest) tl
\end{code}
\end{minipage}
\begin{minipage}{5cm}
\xfig{sqlist}
\end{minipage}

Indeed, the expression |take 10 (join squareList)| evaluates to
|[1,4,2,9,8,3,16,18,12,4]|.

\subquestion
Explain in your own words why the potentially dangerous functions |head| and |tail| in |join|'s definition
are safe (no pattern match failures).

\answer{The functions |head| and |tail| are both mapped over |as| (|rec|'s first argument). All lists in |as| 
are non-empty because we start with the empty list (contains no list at all), and for each recursive call 
to |rec| we first throw away all empty lists (|filter notEmpty rest|). }

\subquestion
We continue with the introduction of a wrapper data type for a normal Haskell list:
\begin{code}
newtype List a = List { listify :: [a] } deriving Eq
\end{code}
This brings into scope the unwrapper function |listify| of type |List a -> [a]|.
Make |List| an instance of the |Functor| type class:
\begin{spec}
class Functor f where 
   fmap :: (a -> b) -> f a -> f b
\end{spec}
  
\answer{
Because normal lists are in the |Functor| type class, we can write:
\begin{code}
instance Functor List where
   fmap f = List . fmap f . listify
\end{code}}
  
\subquestion
Give a point-free definition for |joinList :: List (List a) -> List a|, which 
uses the function |join| to combine lists. There will be a small penalty for a
definition that is not point-free.   
 
\answer{
\begin{code}
joinList = List . join . listify . fmap listify
\end{code}}
 
\subquestion
\label{monadinstance}
Having |join| and |map| (or actually, |fmap|) defined makes it easy to define the monadic
|(>>=)| operator. Make |List| an instance of the |Monad| type class. Of course you may reuse
code defined earlier.
  
\answer{
\begin{code}
instance Monad List where
   return a  = List [a]
   as >>= f  = joinList (fmap f as)
\end{code}}
  
\subquestion
Remember the three algebraic laws for monads:
\begin{center}
%{
%format == = "\equiv"
\begin{tabular}{rclr}
|return x >>= f|&|==|&|f x| & {\sc (left unit)} \\
|m >>= return   |&|==|&|m| & {\sc (right unit)} \\
|m1 >>= (\x -> m2 >>= (\y -> m3))|&|==|&|(m1 >>= (\x -> m2)) >>= (\y -> m3)| & {\sc (bind)} \\
\multicolumn{4}{l}{\hspace*{1cm} assuming that |x| does not appear free in |m3|} \\
\end{tabular}
%}
\end{center}
Do the monad laws hold for the instance defined at {\bf \ref{monadinstance})}?
If you think they hold, give a short motivation (no formal proof is required).
Otherwise, give a counter-example.    

\answer{
The first two laws hold, but not {\sc (bind)}. For proving the left and right unit
laws, you can use the following properties of the |join| function:
\begin{spec}
join [xs]                   ==  xs -- only one row
join (map (\x -> [x]) xs)   ==  xs -- only one column
\end{spec}
To construct a counter-example for {\sc (bind)}, we choose |m1 = List [1,2]|, |m2 = List [x, x]|, and |m3 = List [y, y]|:
\begin{spec}
m1 >>= (\x -> m2 >>= (\y -> m3))   
   = List [1,2] >>= (\x -> List [x, x] >>= (\y -> List [y, y]))
   = List [1,2,1,2,1,2,1,2]
\end{spec}
whereas
\begin{spec}
(m1 >>= (\x -> m2)) >>= (\y -> m3)
   = (List [1,2] >>= (\x -> List [x, x])) >>= (\y -> List [y, y])
   = List [1,2,1,1,2,2,1,2]
\end{spec}}

\subquestion
Define three |QuickCheck| properties to check the monad laws for your |List| instance.
You may assume that a random data generator for |List|s is provided.   

\answer{
The type signatures are required by QuickCheck.
\begin{code}
-- |quickCheck leftUnit| returns |"OK, passed 100 tests."|
leftUnit :: (Int -> List Int) -> Int -> Bool
leftUnit f x = (return x >>= f) == f x

-- |quickCheck rightUnit| returns |"OK, passed 100 tests."|
rightUnit :: List Int -> Bool
rightUnit m  = (m >>= return) == m

-- |quickCheck bind| returns |"Falsifiable."|
bind :: List Int -> (Int -> List Int) -> (Int -> List Int) -> Bool
bind m f g   = ((m >>= f) >>= g) == (m >>= (\x -> f x >>= g))
\end{code}}

\subquestion
Suppose we want to have a monad transformer for |List|. Give a suitable type definition
for this transformer. You do not have to give the instance declarations. 

\answer{
\begin{code}
newtype ListT m a = ListT (m [a])
\end{code}}

\end{question}

%if False
\begin{code}
instance Show a => Show (List a) where
   show (List as) = "List " ++ show as

instance Arbitrary a => Arbitrary (List a) where
   arbitrary                = liftM List arbitrary
   coarbitrary (List as) gb = coarbitrary as gb

instance Show (a -> b) where
   show _ = "<<function>>"
\end{code}
%endif