Exercise

16 February

• Produce the Haskell class declaration for the type class Functor and state its invariants.
• Assume the following datatype declaration:

  data Expr op var
    = Var var
    | Lit Integer
    | OpAppl op [Expr Var]
  

  Define (and verify) a Functor instance for Expr op.
• Assume the following class declaration:

  data GenTerm t where
    genSubst :: t x -> (x -> t y) -> t y
  

  Define a GenTerm instance for Expr op.
• Define a GenTerm instance for HTree, with:

  data HTree a = Leaf a | HTree a :^: HTree a
  

• Define a GenTerm instance for []. Hint: Use map!
• Define a GenTerm instance for Maybe.
• Define a GenTerm instance for Data.Set.Set (in class, a mathematical definition is sufficient).
• Define a GenTerm instance for (->) c.
• Define a GenTerm instance for IO.
• Define composition of substitutions:

  (=>=) :: GenTerm t => (x -> t y) -> (y -> t z) -> (x -> t z)
  

  What are the properties you would expect for this composition?

  In which of the above examples do they hold?