Exercise

16 March

1. Assume the following datatype declaration:

   data T a = MkT a [T a]
   

   Define a function generate :: (a -> [a]) -> a -> T a that accepts as arguments a reduction relation encoded as a function of type a -> [a] and a starting point for reduction, and returns the tree of possible reductions from that starting point.
2. Define a function findFirst :: (a -> Bool) -> T a -> a that, given a predicate p :: a -> Bool and a tree, returns among all tree elements satisfying p one of those reachable from the root via one of the shortest paths.

   Note: The argument tree might be infinite.

3. Using

   Array.array :: Ix i => (i, i) -> [(i, a)] -> Array i a  -- array initialisation
   Ix.range :: Ix i => (i, i) -> [i]                       -- index range
   

   define a function funArray :: (Ix i) => (i,i) -> (i -> a) -> Array a i that stores the image of a function on a given range in an array.

   Using also

   Array.(!) :: Ix i => Array i a -> i -> a       -- array lookup
   Ix.inRange :: Ix i => (i, i) -> i -> Bool       -- bounds check
   

   define a function withFunArray :: (Ix i) => (i,i) -> (i -> a) -> (i -> a) such that withFunArray bounds f i uses an array produced with funArray bounds f to lookup the result if i is within the bounds, and directly applies f otherwise.
   What is the effect of this?
4. In Data.List, you find: unfoldr :: (b -> Maybe (a, b)) -> b -> [a].
   • Show how the type of unfoldr is dual to the type of foldr.
   • Define unfoldr; it produces a list from a seed value.
   • Identify the conditions that required for the following to hold:

     unfoldr g (foldr f z xs) == xs
     

5. Assume the following datatype declaration:

   newtype State s a = State {runState :: (s -> (a, s))}
     -- we already have Functor and Monad instances for this.
   

   Define getState and updState functions.
6. Assume the following datatype declaration:

   newtype StateT s (m::* -> *) a = StateT {runStateT :: (s -> m (a, s))}
   

   • Define (and, at home, verify) a Monad instance for StateT s m.
   • Define a function liftState :: State s a -> StateT s m a that can ``lift'' functions like getState to this new monad.
   • What are the laws you would expect to hold for liftState?