Due 5PM Friday, November 5.

Chapter 18:

1. The state monad can be made polymorphic in the state in the following way:
   
   data SM s a = SM (s -> (s, a))
   
   instance Monad (SM s) where
        return a        = SM $ \s  -> (s,a)
        SM sm0 >>= fsm1 = SM $ \s0 ->
           let (s1,a1) = sm0 s0
               SM sm1  = fsm1 a1
               (s2,a2) = sm1 s1
           in (s2,a2)
   
   Note the "partial application" of SM to s in the instance declaration.
   
   The state monad can also be combined with the Maybe monad to yield a state monad that permits failure and back-tracking.  In particular:
   
   data SME s a = SME (s -> Maybe (s, a))
   
   Provide an instance declaration for SME not just in class Monad, but also in class MonadPlus.
   
   Note: The significance of MonadPlus for SME is that an expression such as "e1 `mplus` e2" means "try e1, and if it succeeds, we are done; but if it fails, try e2".  Since e1 can be arbitrarily complex, this is, in essence, a form of back-tracking.
    
2. Use SME and its monadic instances to devise a solution to the n-queens problem.
    

Chapter 19:

3. Exercise 19.2 in SOE.
    
4. Exercise 19.3 in SOE.
    
5. Exercise 19.4, part 1.
    

Solutions.