+ (nlHsVar (mk_data_type_name tycon))
+
+
+gfoldl_RDR, gunfold_RDR, toConstr_RDR, dataTypeOf_RDR, mkConstr_RDR,
+ mkDataType_RDR, conIndex_RDR, prefix_RDR, infix_RDR :: RdrName
+gfoldl_RDR = varQual_RDR gENERICS (fsLit "gfoldl")
+gunfold_RDR = varQual_RDR gENERICS (fsLit "gunfold")
+toConstr_RDR = varQual_RDR gENERICS (fsLit "toConstr")
+dataTypeOf_RDR = varQual_RDR gENERICS (fsLit "dataTypeOf")
+mkConstr_RDR = varQual_RDR gENERICS (fsLit "mkConstr")
+mkDataType_RDR = varQual_RDR gENERICS (fsLit "mkDataType")
+conIndex_RDR = varQual_RDR gENERICS (fsLit "constrIndex")
+prefix_RDR = dataQual_RDR gENERICS (fsLit "Prefix")
+infix_RDR = dataQual_RDR gENERICS (fsLit "Infix")
+\end{code}
+
+
+
+%************************************************************************
+%* *
+ Functor instances
+%* *
+%************************************************************************
+
+For the data type:
+
+ data T a = T1 Int a | T2 (T a)
+
+We generate the instance:
+
+ instance Functor T where
+ fmap f (T1 b1 a) = T1 b1 (f a)
+ fmap f (T2 ta) = T2 (fmap f ta)
+
+Notice that we don't simply apply 'fmap' to the constructor arguments.
+Rather
+ - Do nothing to an argument whose type doesn't mention 'a'
+ - Apply 'f' to an argument of type 'a'
+ - Apply 'fmap f' to other arguments
+That's why we have to recurse deeply into the constructor argument types,
+rather than just one level, as we typically do.
+
+What about types with more than one type parameter? In general, we only
+derive Functor for the last position:
+
+ data S a b = S1 [b] | S2 (a, T a b)
+ instance Functor (S a) where
+ fmap f (S1 bs) = S1 (fmap f bs)
+ fmap f (S2 (p,q)) = S2 (a, fmap f q)
+
+However, we have special cases for
+ - tuples
+ - functions
+
+More formally, we write the derivation of fmap code over type variable
+'a for type 'b as ($fmap 'a 'b). In this general notation the derived
+instance for T is:
+
+ instance Functor T where
+ fmap f (T1 x1 x2) = T1 ($(fmap 'a 'b1) x1) ($(fmap 'a 'a) x2)
+ fmap f (T2 x1) = T2 ($(fmap 'a '(T a)) x1)
+
+ $(fmap 'a 'b) x = x -- when b does not contain a
+ $(fmap 'a 'a) x = f x
+ $(fmap 'a '(b1,b2)) x = case x of (x1,x2) -> ($(fmap 'a 'b1) x1, $(fmap 'a 'b2) x2)
+ $(fmap 'a '(T b1 b2)) x = fmap $(fmap 'a 'b2) x -- when a only occurs in the last parameter, b2
+ $(fmap 'a '(b -> c)) x = \b -> $(fmap 'a' 'c) (x ($(cofmap 'a 'b) b))
+
+For functions, the type parameter 'a can occur in a contravariant position,
+which means we need to derive a function like:
+
+ cofmap :: (a -> b) -> (f b -> f a)
+
+This is pretty much the same as $fmap, only without the $(cofmap 'a 'a) case:
+
+ $(cofmap 'a 'b) x = x -- when b does not contain a
+ $(cofmap 'a 'a) x = error "type variable in contravariant position"
+ $(cofmap 'a '(b1,b2)) x = case x of (x1,x2) -> ($(cofmap 'a 'b1) x1, $(cofmap 'a 'b2) x2)
+ $(cofmap 'a '[b]) x = map $(cofmap 'a 'b) x
+ $(cofmap 'a '(T b1 b2)) x = fmap $(cofmap 'a 'b2) x -- when a only occurs in the last parameter, b2
+ $(cofmap 'a '(b -> c)) x = \b -> $(cofmap 'a' 'c) (x ($(fmap 'a 'c) b))
+
+\begin{code}
+gen_Functor_binds :: SrcSpan -> TyCon -> (LHsBinds RdrName, DerivAuxBinds)
+gen_Functor_binds loc tycon
+ = (listToBag [fmap_bind], [])
+ where
+ data_cons = tyConDataCons tycon
+ arg = last (tyConTyVars tycon) -- argument to derive for, 'a in the above description
+
+ fmap_bind = L loc $ mkFunBind (L loc fmap_RDR) (map fmap_eqn data_cons)
+ fmap_eqn con = evalState (match_for_con [f_Pat] con parts) bs_RDRs
+ where parts = map derive_fmap_type (dataConOrigArgTys con)
+
+ derive_fmap_type :: Type -> LHsExpr RdrName -> State [RdrName] (LHsExpr RdrName)
+ derive_fmap_type = functorLikeTraverse
+ (\ x -> return x) -- fmap f x = x
+ (\ x -> return (nlHsApp f_Expr x)) -- fmap f x = f x
+ (panic "contravariant")
+ (\g h x -> mkSimpleLam (\b -> h =<< (nlHsApp x `fmap` g b))) -- fmap f x = \b -> h (x (g b))
+ (mkSimpleTupleCase match_for_con) -- fmap f x = case x of (a1,a2,..) -> (g1 a1,g2 a2,..)
+ (\_ g x -> do gg <- mkSimpleLam g
+ return $ nlHsApps fmap_RDR [gg,x]) -- fmap f x = fmap g x
+ (panic "in other argument")
+ (\_ g x -> g x)
+ arg
+
+ match_for_con = mkSimpleConMatch $
+ \con_name xsM -> do xs <- sequence xsM
+ return (nlHsApps con_name xs) -- Con (g1 v1) (g2 v2) ..
+\end{code}
+
+Utility functions related to Functor deriving.
+
+Since several things use the same pattern of traversal, this is abstracted into functorLikeTraverse.
+This function works like a fold: it makes a value of type 'a' in a bottom up way.
+
+\begin{code}
+-- Generic traversal for Functor deriving
+functorLikeTraverse :: a -- ^ Case: does not contain variable
+ -> a -- ^ Case: the variable itself
+ -> a -- ^ Case: the variable itself, contravariantly
+ -> (a -> a -> a) -- ^ Case: function type
+ -> (Boxity -> [a] -> a) -- ^ Case: tuple type
+ -> (Type -> a -> a) -- ^ Case: type app, variable only in last argument
+ -> a -- ^ Case: type app, variable other than in last argument
+ -> (TcTyVar -> a -> a) -- ^ Case: forall type
+ -> TcTyVar -- ^ Variable to look for
+ -> Type -- ^ Type to process
+ -> a
+functorLikeTraverse caseTrivial caseVar caseCoVar caseFun caseTuple caseTyApp caseWrongArg caseForAll var ty
+ = fst (go False ty)
+ where -- go returns (result of type a, does type contain var)
+ go co ty | Just ty' <- coreView ty = go co ty'
+ go co (TyVarTy v) | v == var = (if co then caseCoVar else caseVar,True)
+ go co (FunTy (PredTy _) b) = go co b
+ go co (FunTy x y) | xc || yc = (caseFun xr yr,True)
+ where (xr,xc) = go (not co) x
+ (yr,yc) = go co y
+ go co (AppTy x y) | xc = (caseWrongArg, True)
+ | yc = (caseTyApp x yr, True)
+ where (_, xc) = go co x
+ (yr,yc) = go co y
+ go co ty@(TyConApp con args)
+ | isTupleTyCon con = (caseTuple (tupleTyConBoxity con) xrs,True)
+ | null args = (caseTrivial,False) -- T
+ | or (init xcs) = (caseWrongArg,True) -- T (..var..) ty
+ | last xcs = -- T (..no var..) ty
+ (caseTyApp (fst (splitAppTy ty)) (last xrs),True)
+ where (xrs,xcs) = unzip (map (go co) args)
+ go co (ForAllTy v x) | v /= var && xc = (caseForAll v xr,True)
+ where (xr,xc) = go co x
+ go _ _ = (caseTrivial,False)
+
+-- Return all syntactic subterms of ty that contain var somewhere
+-- These are the things that should appear in instance constraints
+deepSubtypesContaining :: TcTyVar -> TcType -> [TcType]
+deepSubtypesContaining = functorLikeTraverse
+ []
+ []
+ (panic "contravariant")
+ (\x y -> x ++ y) -- function
+ (\_ xs -> concat xs) -- tuple
+ (\ty x -> ty : x) -- tyapp
+ (panic "in other argument")
+ (\v x -> filter (not . (v `elemVarSet`) . tyVarsOfType) x) -- forall v
+
+
+-- Make a HsLam using a fresh variable from a State monad
+mkSimpleLam :: (LHsExpr id -> State [id] (LHsExpr id)) -> State [id] (LHsExpr id)
+mkSimpleLam lam = do
+ (n:names) <- get
+ put names
+ body <- lam (nlHsVar n)
+ return (mkHsLam [nlVarPat n] body)
+
+mkSimpleLam2 :: (LHsExpr id -> LHsExpr id -> State [id] (LHsExpr id)) -> State [id] (LHsExpr id)
+mkSimpleLam2 lam = do
+ (n1:n2:names) <- get
+ put names
+ body <- lam (nlHsVar n1) (nlHsVar n2)
+ return (mkHsLam [nlVarPat n1,nlVarPat n2] body)
+
+-- "Con a1 a2 a3 -> fold [x1 a1, x2 a2, x3 a3]"
+mkSimpleConMatch :: Monad m => (RdrName -> [a] -> m (LHsExpr RdrName)) -> [LPat RdrName] -> DataCon -> [LHsExpr RdrName -> a] -> m (LMatch RdrName)
+mkSimpleConMatch fold extra_pats con insides = do
+ let con_name = getRdrName con
+ let vars_needed = takeList insides as_RDRs
+ let pat = nlConVarPat con_name vars_needed
+ rhs <- fold con_name (zipWith ($) insides (map nlHsVar vars_needed))
+ return $ mkMatch (extra_pats ++ [pat]) rhs emptyLocalBinds
+
+-- "case x of (a1,a2,a3) -> fold [x1 a1, x2 a2, x3 a3]"
+mkSimpleTupleCase :: Monad m => ([LPat RdrName] -> DataCon -> [LHsExpr RdrName -> a] -> m (LMatch RdrName))
+ -> Boxity -> [LHsExpr RdrName -> a] -> LHsExpr RdrName -> m (LHsExpr RdrName)
+mkSimpleTupleCase match_for_con boxity insides x = do
+ let con = tupleCon boxity (length insides)
+ match <- match_for_con [] con insides
+ return $ nlHsCase x [match]