{- (c) The University of Glasgow 2011 The deriving code for the Functor, Foldable, and Traversable classes (equivalent to the code in TcGenDeriv, for other classes) -} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE LambdaCase #-} module TcGenFunctor ( FFoldType(..), functorLikeTraverse, deepSubtypesContaining, foldDataConArgs, gen_Functor_binds, gen_Foldable_binds, gen_Traversable_binds ) where import GhcPrelude import Bag import DataCon import FastString import HsSyn import Panic import PrelNames import RdrName import SrcLoc import State import TcGenDeriv import TcType import TyCon import TyCoRep import Type import Util import Var import VarSet import MkId (coerceId) import TysWiredIn (true_RDR, false_RDR) import Data.Maybe (catMaybes, isJust) {- ************************************************************************ * * Functor instances see http://www.mail-archive.com/haskell-prime@haskell.org/msg02116.html * * ************************************************************************ 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) = f $(fmap 'a '(b1,b2)) = \x -> case x of (x1,x2) -> ($(fmap 'a 'b1) x1, $(fmap 'a 'b2) x2) $(fmap 'a '(T b1 b2)) = fmap $(fmap 'a 'b2) -- 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) = 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]) = map $(cofmap 'a 'b) $(cofmap 'a '(T b1 b2)) = fmap $(cofmap 'a 'b2) -- when a only occurs in the last parameter, b2 $(cofmap 'a '(b -> c)) = \x b -> $(cofmap 'a' 'c) (x ($(fmap 'a 'c) b)) Note that the code produced by $(fmap _ _) is always a higher order function, with type `(a -> b) -> (g a -> g b)` for some g. When we need to do pattern matching on the type, this means create a lambda function (see the (,) case above). The resulting code for fmap can look a bit weird, for example: data X a = X (a,Int) -- generated instance instance Functor X where fmap f (X x) = (\y -> case y of (x1,x2) -> X (f x1, (\z -> z) x2)) x The optimizer should be able to simplify this code by simple inlining. An older version of the deriving code tried to avoid these applied lambda functions by producing a meta level function. But the function to be mapped, `f`, is a function on the code level, not on the meta level, so it was eta expanded to `\x -> [| f $x |]`. This resulted in too much eta expansion. It is better to produce too many lambdas than to eta expand, see ticket #7436. -} gen_Functor_binds :: SrcSpan -> TyCon -> (LHsBinds GhcPs, BagDerivStuff) -- When the argument is phantom, we can use fmap _ = coerce -- See Note [Phantom types with Functor, Foldable, and Traversable] gen_Functor_binds :: SrcSpan -> TyCon -> (LHsBinds GhcPs, BagDerivStuff) gen_Functor_binds loc :: SrcSpan loc tycon :: TyCon tycon | Role Phantom <- [Role] -> Role forall a. [a] -> a last (TyCon -> [Role] tyConRoles TyCon tycon) = (LHsBind GhcPs -> LHsBinds GhcPs forall a. a -> Bag a unitBag LHsBind GhcPs fmap_bind, BagDerivStuff forall a. Bag a emptyBag) where fmap_name :: GenLocated SrcSpan RdrName fmap_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName forall l e. l -> e -> GenLocated l e L SrcSpan loc RdrName fmap_RDR fmap_bind :: LHsBind GhcPs fmap_bind = GenLocated SrcSpan RdrName -> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs mkRdrFunBind GenLocated SrcSpan RdrName fmap_name [LMatch GhcPs (LHsExpr GhcPs)] fmap_eqns fmap_eqns :: [LMatch GhcPs (LHsExpr GhcPs)] fmap_eqns = [HsMatchContext (NameOrRdrName (IdP GhcPs)) -> [LPat GhcPs] -> LHsExpr GhcPs -> LMatch GhcPs (LHsExpr GhcPs) forall (p :: Pass) (body :: * -> *). HsMatchContext (NameOrRdrName (IdP (GhcPass p))) -> [LPat (GhcPass p)] -> Located (body (GhcPass p)) -> LMatch (GhcPass p) (Located (body (GhcPass p))) mkSimpleMatch HsMatchContext RdrName HsMatchContext (NameOrRdrName (IdP GhcPs)) fmap_match_ctxt [LPat GhcPs nlWildPat] LHsExpr GhcPs coerce_Expr] fmap_match_ctxt :: HsMatchContext RdrName fmap_match_ctxt = GenLocated SrcSpan RdrName -> HsMatchContext RdrName forall id. Located id -> HsMatchContext id mkPrefixFunRhs GenLocated SrcSpan RdrName fmap_name gen_Functor_binds loc :: SrcSpan loc tycon :: TyCon tycon = ([LHsBind GhcPs] -> LHsBinds GhcPs forall a. [a] -> Bag a listToBag [LHsBind GhcPs fmap_bind, LHsBind GhcPs replace_bind], BagDerivStuff forall a. Bag a emptyBag) where data_cons :: [DataCon] data_cons = TyCon -> [DataCon] tyConDataCons TyCon tycon fmap_name :: GenLocated SrcSpan RdrName fmap_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName forall l e. l -> e -> GenLocated l e L SrcSpan loc RdrName fmap_RDR -- See Note [EmptyDataDecls with Functor, Foldable, and Traversable] fmap_bind :: LHsBind GhcPs fmap_bind = Arity -> (LHsExpr GhcPs -> LHsExpr GhcPs) -> GenLocated SrcSpan RdrName -> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs mkRdrFunBindEC 2 LHsExpr GhcPs -> LHsExpr GhcPs forall a. a -> a id GenLocated SrcSpan RdrName fmap_name [LMatch GhcPs (LHsExpr GhcPs)] fmap_eqns fmap_match_ctxt :: HsMatchContext RdrName fmap_match_ctxt = GenLocated SrcSpan RdrName -> HsMatchContext RdrName forall id. Located id -> HsMatchContext id mkPrefixFunRhs GenLocated SrcSpan RdrName fmap_name fmap_eqn :: DataCon -> LMatch GhcPs (LHsExpr GhcPs) fmap_eqn con :: DataCon con = (State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs)) -> [RdrName] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> LMatch GhcPs (LHsExpr GhcPs) forall a b c. (a -> b -> c) -> b -> a -> c flip State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs) forall s a. State s a -> s -> a evalState [RdrName] bs_RDRs (State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> LMatch GhcPs (LHsExpr GhcPs)) -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> LMatch GhcPs (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ HsMatchContext RdrName -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_for_con HsMatchContext RdrName fmap_match_ctxt [LPat GhcPs f_Pat] DataCon con ([LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> State [RdrName] [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b =<< State [RdrName] [LHsExpr GhcPs] parts where parts :: State [RdrName] [LHsExpr GhcPs] parts = [State [RdrName] (LHsExpr GhcPs)] -> State [RdrName] [LHsExpr GhcPs] forall (t :: * -> *) (m :: * -> *) a. (Traversable t, Monad m) => t (m a) -> m (t a) sequence ([State [RdrName] (LHsExpr GhcPs)] -> State [RdrName] [LHsExpr GhcPs]) -> [State [RdrName] (LHsExpr GhcPs)] -> State [RdrName] [LHsExpr GhcPs] forall a b. (a -> b) -> a -> b $ FFoldType (State [RdrName] (LHsExpr GhcPs)) -> DataCon -> [State [RdrName] (LHsExpr GhcPs)] forall a. FFoldType a -> DataCon -> [a] foldDataConArgs FFoldType (State [RdrName] (LHsExpr GhcPs)) ft_fmap DataCon con fmap_eqns :: [LMatch GhcPs (LHsExpr GhcPs)] fmap_eqns = (DataCon -> LMatch GhcPs (LHsExpr GhcPs)) -> [DataCon] -> [LMatch GhcPs (LHsExpr GhcPs)] forall a b. (a -> b) -> [a] -> [b] map DataCon -> LMatch GhcPs (LHsExpr GhcPs) fmap_eqn [DataCon] data_cons ft_fmap :: FFoldType (State [RdrName] (LHsExpr GhcPs)) ft_fmap :: FFoldType (State [RdrName] (LHsExpr GhcPs)) ft_fmap = FT :: forall a. a -> a -> a -> (a -> a -> a) -> (TyCon -> [a] -> a) -> (Type -> a -> a) -> a -> (TcTyVar -> a -> a) -> FFoldType a FT { ft_triv :: State [RdrName] (LHsExpr GhcPs) ft_triv = (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs)) -> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ \x :: LHsExpr GhcPs x -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return LHsExpr GhcPs x -- fmap f = \x -> x , ft_var :: State [RdrName] (LHsExpr GhcPs) ft_var = LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return LHsExpr GhcPs f_Expr -- fmap f = f , ft_fun :: State [RdrName] (LHsExpr GhcPs) -> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] (LHsExpr GhcPs) ft_fun = \g :: State [RdrName] (LHsExpr GhcPs) g h :: State [RdrName] (LHsExpr GhcPs) h -> do LHsExpr GhcPs gg <- State [RdrName] (LHsExpr GhcPs) g LHsExpr GhcPs hh <- State [RdrName] (LHsExpr GhcPs) h (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam2 ((LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs)) -> (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ \x :: LHsExpr GhcPs x b :: LHsExpr GhcPs b -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs hh (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs x (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs gg LHsExpr GhcPs b)) -- fmap f = \x b -> h (x (g b)) , ft_tup :: TyCon -> [State [RdrName] (LHsExpr GhcPs)] -> State [RdrName] (LHsExpr GhcPs) ft_tup = \t :: TyCon t gs :: [State [RdrName] (LHsExpr GhcPs)] gs -> do [LHsExpr GhcPs] gg <- [State [RdrName] (LHsExpr GhcPs)] -> State [RdrName] [LHsExpr GhcPs] forall (t :: * -> *) (m :: * -> *) a. (Traversable t, Monad m) => t (m a) -> m (t a) sequence [State [RdrName] (LHsExpr GhcPs)] gs (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs)) -> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ ([LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [LHsExpr GhcPs] -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => ([LPat GhcPs] -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs) mkSimpleTupleCase (HsMatchContext RdrName -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_for_con HsMatchContext RdrName forall id. HsMatchContext id CaseAlt) TyCon t [LHsExpr GhcPs] gg -- fmap f = \x -> case x of (a1,a2,..) -> (g1 a1,g2 a2,..) , ft_ty_app :: Type -> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] (LHsExpr GhcPs) ft_ty_app = \_ g :: State [RdrName] (LHsExpr GhcPs) g -> LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs fmap_Expr (LHsExpr GhcPs -> LHsExpr GhcPs) -> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] (LHsExpr GhcPs) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b <$> State [RdrName] (LHsExpr GhcPs) g -- fmap f = fmap g , ft_forall :: TcTyVar -> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] (LHsExpr GhcPs) ft_forall = \_ g :: State [RdrName] (LHsExpr GhcPs) g -> State [RdrName] (LHsExpr GhcPs) g , ft_bad_app :: State [RdrName] (LHsExpr GhcPs) ft_bad_app = String -> State [RdrName] (LHsExpr GhcPs) forall a. String -> a panic "in other argument in ft_fmap" , ft_co_var :: State [RdrName] (LHsExpr GhcPs) ft_co_var = String -> State [RdrName] (LHsExpr GhcPs) forall a. String -> a panic "contravariant in ft_fmap" } -- See Note [Deriving <$] replace_name :: GenLocated SrcSpan RdrName replace_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName forall l e. l -> e -> GenLocated l e L SrcSpan loc RdrName replace_RDR -- See Note [EmptyDataDecls with Functor, Foldable, and Traversable] replace_bind :: LHsBind GhcPs replace_bind = Arity -> (LHsExpr GhcPs -> LHsExpr GhcPs) -> GenLocated SrcSpan RdrName -> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs mkRdrFunBindEC 2 LHsExpr GhcPs -> LHsExpr GhcPs forall a. a -> a id GenLocated SrcSpan RdrName replace_name [LMatch GhcPs (LHsExpr GhcPs)] replace_eqns replace_match_ctxt :: HsMatchContext RdrName replace_match_ctxt = GenLocated SrcSpan RdrName -> HsMatchContext RdrName forall id. Located id -> HsMatchContext id mkPrefixFunRhs GenLocated SrcSpan RdrName replace_name replace_eqn :: DataCon -> LMatch GhcPs (LHsExpr GhcPs) replace_eqn con :: DataCon con = (State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs)) -> [RdrName] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> LMatch GhcPs (LHsExpr GhcPs) forall a b c. (a -> b -> c) -> b -> a -> c flip State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs) forall s a. State s a -> s -> a evalState [RdrName] bs_RDRs (State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> LMatch GhcPs (LHsExpr GhcPs)) -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> LMatch GhcPs (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ HsMatchContext RdrName -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_for_con HsMatchContext RdrName replace_match_ctxt [LPat GhcPs z_Pat] DataCon con ([LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> State [RdrName] [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b =<< State [RdrName] [LHsExpr GhcPs] parts where parts :: State [RdrName] [LHsExpr GhcPs] parts = (State [RdrName] Replacer -> State [RdrName] (LHsExpr GhcPs)) -> [State [RdrName] Replacer] -> State [RdrName] [LHsExpr GhcPs] forall (t :: * -> *) (f :: * -> *) a b. (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) traverse ((Replacer -> LHsExpr GhcPs) -> State [RdrName] Replacer -> State [RdrName] (LHsExpr GhcPs) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap Replacer -> LHsExpr GhcPs replace) ([State [RdrName] Replacer] -> State [RdrName] [LHsExpr GhcPs]) -> [State [RdrName] Replacer] -> State [RdrName] [LHsExpr GhcPs] forall a b. (a -> b) -> a -> b $ FFoldType (State [RdrName] Replacer) -> DataCon -> [State [RdrName] Replacer] forall a. FFoldType a -> DataCon -> [a] foldDataConArgs FFoldType (State [RdrName] Replacer) ft_replace DataCon con replace_eqns :: [LMatch GhcPs (LHsExpr GhcPs)] replace_eqns = (DataCon -> LMatch GhcPs (LHsExpr GhcPs)) -> [DataCon] -> [LMatch GhcPs (LHsExpr GhcPs)] forall a b. (a -> b) -> [a] -> [b] map DataCon -> LMatch GhcPs (LHsExpr GhcPs) replace_eqn [DataCon] data_cons ft_replace :: FFoldType (State [RdrName] Replacer) ft_replace :: FFoldType (State [RdrName] Replacer) ft_replace = FT :: forall a. a -> a -> a -> (a -> a -> a) -> (TyCon -> [a] -> a) -> (Type -> a -> a) -> a -> (TcTyVar -> a -> a) -> FFoldType a FT { ft_triv :: State [RdrName] Replacer ft_triv = (LHsExpr GhcPs -> Replacer) -> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap LHsExpr GhcPs -> Replacer Nested (State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer) -> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer forall a b. (a -> b) -> a -> b $ (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs)) -> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ \x :: LHsExpr GhcPs x -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return LHsExpr GhcPs x -- (p <$) = \x -> x , ft_var :: State [RdrName] Replacer ft_var = (LHsExpr GhcPs -> Replacer) -> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap LHsExpr GhcPs -> Replacer Immediate (State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer) -> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer forall a b. (a -> b) -> a -> b $ (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs)) -> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ \_ -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return LHsExpr GhcPs z_Expr -- (p <$) = const p , ft_fun :: State [RdrName] Replacer -> State [RdrName] Replacer -> State [RdrName] Replacer ft_fun = \g :: State [RdrName] Replacer g h :: State [RdrName] Replacer h -> do LHsExpr GhcPs gg <- Replacer -> LHsExpr GhcPs replace (Replacer -> LHsExpr GhcPs) -> State [RdrName] Replacer -> State [RdrName] (LHsExpr GhcPs) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b <$> State [RdrName] Replacer g LHsExpr GhcPs hh <- Replacer -> LHsExpr GhcPs replace (Replacer -> LHsExpr GhcPs) -> State [RdrName] Replacer -> State [RdrName] (LHsExpr GhcPs) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b <$> State [RdrName] Replacer h (LHsExpr GhcPs -> Replacer) -> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap LHsExpr GhcPs -> Replacer Nested (State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer) -> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer forall a b. (a -> b) -> a -> b $ (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam2 ((LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs)) -> (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ \x :: LHsExpr GhcPs x b :: LHsExpr GhcPs b -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs hh (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs x (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs gg LHsExpr GhcPs b)) -- (<$) p = \x b -> h (x (g b)) , ft_tup :: TyCon -> [State [RdrName] Replacer] -> State [RdrName] Replacer ft_tup = \t :: TyCon t gs :: [State [RdrName] Replacer] gs -> do [LHsExpr GhcPs] gg <- (State [RdrName] Replacer -> State [RdrName] (LHsExpr GhcPs)) -> [State [RdrName] Replacer] -> State [RdrName] [LHsExpr GhcPs] forall (t :: * -> *) (f :: * -> *) a b. (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) traverse ((Replacer -> LHsExpr GhcPs) -> State [RdrName] Replacer -> State [RdrName] (LHsExpr GhcPs) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap Replacer -> LHsExpr GhcPs replace) [State [RdrName] Replacer] gs (LHsExpr GhcPs -> Replacer) -> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap LHsExpr GhcPs -> Replacer Nested (State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer) -> ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs)) -> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] Replacer forall b c a. (b -> c) -> (a -> b) -> a -> c . (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] Replacer) -> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] Replacer forall a b. (a -> b) -> a -> b $ ([LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [LHsExpr GhcPs] -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => ([LPat GhcPs] -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs) mkSimpleTupleCase (HsMatchContext RdrName -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_for_con HsMatchContext RdrName forall id. HsMatchContext id CaseAlt) TyCon t [LHsExpr GhcPs] gg -- (p <$) = \x -> case x of (a1,a2,..) -> (g1 a1,g2 a2,..) , ft_ty_app :: Type -> State [RdrName] Replacer -> State [RdrName] Replacer ft_ty_app = \_ gm :: State [RdrName] Replacer gm -> do Replacer g <- State [RdrName] Replacer gm case Replacer g of Nested g' :: LHsExpr GhcPs g' -> Replacer -> State [RdrName] Replacer forall (f :: * -> *) a. Applicative f => a -> f a pure (Replacer -> State [RdrName] Replacer) -> (LHsExpr GhcPs -> Replacer) -> LHsExpr GhcPs -> State [RdrName] Replacer forall b c a. (b -> c) -> (a -> b) -> a -> c . LHsExpr GhcPs -> Replacer Nested (LHsExpr GhcPs -> State [RdrName] Replacer) -> LHsExpr GhcPs -> State [RdrName] Replacer forall a b. (a -> b) -> a -> b $ LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs fmap_Expr (LHsExpr GhcPs -> LHsExpr GhcPs) -> LHsExpr GhcPs -> LHsExpr GhcPs forall a b. (a -> b) -> a -> b $ LHsExpr GhcPs g' Immediate _ -> Replacer -> State [RdrName] Replacer forall (f :: * -> *) a. Applicative f => a -> f a pure (Replacer -> State [RdrName] Replacer) -> (LHsExpr GhcPs -> Replacer) -> LHsExpr GhcPs -> State [RdrName] Replacer forall b c a. (b -> c) -> (a -> b) -> a -> c . LHsExpr GhcPs -> Replacer Nested (LHsExpr GhcPs -> State [RdrName] Replacer) -> LHsExpr GhcPs -> State [RdrName] Replacer forall a b. (a -> b) -> a -> b $ LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs replace_Expr LHsExpr GhcPs z_Expr -- (p <$) = fmap (p <$) , ft_forall :: TcTyVar -> State [RdrName] Replacer -> State [RdrName] Replacer ft_forall = \_ g :: State [RdrName] Replacer g -> State [RdrName] Replacer g , ft_bad_app :: State [RdrName] Replacer ft_bad_app = String -> State [RdrName] Replacer forall a. String -> a panic "in other argument in ft_replace" , ft_co_var :: State [RdrName] Replacer ft_co_var = String -> State [RdrName] Replacer forall a. String -> a panic "contravariant in ft_replace" } -- Con a1 a2 ... -> Con (f1 a1) (f2 a2) ... match_for_con :: HsMatchContext RdrName -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_for_con :: HsMatchContext RdrName -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_for_con ctxt :: HsMatchContext RdrName ctxt = HsMatchContext RdrName -> (RdrName -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *). Monad m => HsMatchContext RdrName -> (RdrName -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> m (LMatch GhcPs (LHsExpr GhcPs)) mkSimpleConMatch HsMatchContext RdrName ctxt ((RdrName -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> (RdrName -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall a b. (a -> b) -> a -> b $ \con_name :: RdrName con_name xs :: [LHsExpr GhcPs] xs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id) nlHsApps RdrName IdP GhcPs con_name [LHsExpr GhcPs] xs -- Con x1 x2 .. -- See Note [Deriving <$] data Replacer = Immediate {Replacer -> LHsExpr GhcPs replace :: LHsExpr GhcPs} | Nested {replace :: LHsExpr GhcPs} {- Note [Deriving <$] ~~~~~~~~~~~~~~~~~~ We derive the definition of <$. Allowing this to take the default definition can lead to memory leaks: mapping over a structure with a constant function can fill the result structure with trivial thunks that retain the values from the original structure. The simplifier seems to handle this all right for simple types, but not for recursive ones. Consider data Tree a = Bin !(Tree a) a !(Tree a) | Tip deriving Functor -- fmap _ Tip = Tip -- fmap f (Bin l v r) = Bin (fmap f l) (f v) (fmap f r) Using the default definition of <$, we get (<$) x = fmap (\_ -> x) and that simplifies no further. Why is that? `fmap` is defined recursively, so GHC cannot inline it. The static argument transformation would turn the definition into a non-recursive one -- fmap f = go where -- go Tip = Tip -- go (Bin l v r) = Bin (go l) (f v) (go r) which GHC could inline, producing an efficient definion of `<$`. But there are several problems. First, GHC does not perform the static argument transformation by default, even with -O2. Second, even when it does perform the static argument transformation, it does so only when there are at least two static arguments, which is not the case for fmap. Finally, when the type in question is non-regular, such as data Nesty a = Z a | S (Nesty a) (Nest (a, a)) the function argument is no longer (entirely) static, so the static argument transformation will do nothing for us. Applying the default definition of `<$` will produce a tree full of thunks that look like ((\_ -> x) x0), which represents unnecessary thunk allocation and also retention of the previous value, potentially leaking memory. Instead, we derive <$ separately. Two aspects are different from fmap: the case of the sought type variable (ft_var) and the case of a type application (ft_ty_app). The interesting one is ft_ty_app. We have to distinguish two cases: the "immediate" case where the type argument *is* the sought type variable, and the "nested" case where the type argument *contains* the sought type variable. The immediate case: Suppose we have data Imm a = Imm (F ... a) Then we want to define x <$ Imm q = Imm (x <$ q) The nested case: Suppose we have data Nes a = Nes (F ... (G a)) Then we want to define x <$ Nes q = Nes (fmap (x <$) q) We use the Replacer type to tag whether the expression derived for applying <$ to the last type variable was the ft_var case (immediate) or one of the others (letting ft_forall pass through as usual). We could, but do not, give tuples special treatment to improve efficiency in some cases. Suppose we have data Nest a = Z a | S (Nest (a,a)) The optimal definition would be x <$ Z _ = Z x x <$ S t = S ((x, x) <$ t) which produces a result with maximal internal sharing. The reason we do not attempt to treat this case specially is that we have no way to give user-provided tuple-like types similar treatment. If the user changed the definition to data Pair a = Pair a a data Nest a = Z a | S (Nest (Pair a)) they would experience a surprising degradation in performance. -} {- 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. -} -- Generic traversal for Functor deriving -- See Note [FFoldType and functorLikeTraverse] data FFoldType a -- Describes how to fold over a Type in a functor like way = FT { FFoldType a -> a ft_triv :: a -- ^ Does not contain variable , FFoldType a -> a ft_var :: a -- ^ The variable itself , FFoldType a -> a ft_co_var :: a -- ^ The variable itself, contravariantly , FFoldType a -> a -> a -> a ft_fun :: a -> a -> a -- ^ Function type , FFoldType a -> TyCon -> [a] -> a ft_tup :: TyCon -> [a] -> a -- ^ Tuple type , FFoldType a -> Type -> a -> a ft_ty_app :: Type -> a -> a -- ^ Type app, variable only in last argument , FFoldType a -> a ft_bad_app :: a -- ^ Type app, variable other than in last argument , FFoldType a -> TcTyVar -> a -> a ft_forall :: TcTyVar -> a -> a -- ^ Forall type } functorLikeTraverse :: forall a. TyVar -- ^ Variable to look for -> FFoldType a -- ^ How to fold -> Type -- ^ Type to process -> a functorLikeTraverse :: TcTyVar -> FFoldType a -> Type -> a functorLikeTraverse var :: TcTyVar var (FT { ft_triv :: forall a. FFoldType a -> a ft_triv = a caseTrivial, ft_var :: forall a. FFoldType a -> a ft_var = a caseVar , ft_co_var :: forall a. FFoldType a -> a ft_co_var = a caseCoVar, ft_fun :: forall a. FFoldType a -> a -> a -> a ft_fun = a -> a -> a caseFun , ft_tup :: forall a. FFoldType a -> TyCon -> [a] -> a ft_tup = TyCon -> [a] -> a caseTuple, ft_ty_app :: forall a. FFoldType a -> Type -> a -> a ft_ty_app = Type -> a -> a caseTyApp , ft_bad_app :: forall a. FFoldType a -> a ft_bad_app = a caseWrongArg, ft_forall :: forall a. FFoldType a -> TcTyVar -> a -> a ft_forall = TcTyVar -> a -> a caseForAll }) ty :: Type ty = (a, Bool) -> a forall a b. (a, b) -> a fst (Bool -> Type -> (a, Bool) go Bool False Type ty) where go :: Bool -- Covariant or contravariant context -> Type -> (a, Bool) -- (result of type a, does type contain var) go :: Bool -> Type -> (a, Bool) go co :: Bool co ty :: Type ty | Just ty' :: Type ty' <- Type -> Maybe Type tcView Type ty = Bool -> Type -> (a, Bool) go Bool co Type ty' go co :: Bool co (TyVarTy v :: TcTyVar v) | TcTyVar v TcTyVar -> TcTyVar -> Bool forall a. Eq a => a -> a -> Bool == TcTyVar var = (if Bool co then a caseCoVar else a caseVar,Bool True) go co :: Bool co (FunTy x :: Type x y :: Type y) | Type -> Bool isPredTy Type x = Bool -> Type -> (a, Bool) go Bool co Type y | Bool xc Bool -> Bool -> Bool || Bool yc = (a -> a -> a caseFun a xr a yr,Bool True) where (xr :: a xr,xc :: Bool xc) = Bool -> Type -> (a, Bool) go (Bool -> Bool not Bool co) Type x (yr :: a yr,yc :: Bool yc) = Bool -> Type -> (a, Bool) go Bool co Type y go co :: Bool co (AppTy x :: Type x y :: Type y) | Bool xc = (a caseWrongArg, Bool True) | Bool yc = (Type -> a -> a caseTyApp Type x a yr, Bool True) where (_, xc :: Bool xc) = Bool -> Type -> (a, Bool) go Bool co Type x (yr :: a yr,yc :: Bool yc) = Bool -> Type -> (a, Bool) go Bool co Type y go co :: Bool co ty :: Type ty@(TyConApp con :: TyCon con args :: [Type] args) | Bool -> Bool not ([Bool] -> Bool forall (t :: * -> *). Foldable t => t Bool -> Bool or [Bool] xcs) = (a caseTrivial, Bool False) -- Variable does not occur -- At this point we know that xrs, xcs is not empty, -- and at least one xr is True | TyCon -> Bool isTupleTyCon TyCon con = (TyCon -> [a] -> a caseTuple TyCon con [a] xrs, Bool True) | [Bool] -> Bool forall (t :: * -> *). Foldable t => t Bool -> Bool or ([Bool] -> [Bool] forall a. [a] -> [a] init [Bool] xcs) = (a caseWrongArg, Bool True) -- T (..var..) ty | Just (fun_ty :: Type fun_ty, _) <- Type -> Maybe (Type, Type) splitAppTy_maybe Type ty -- T (..no var..) ty = (Type -> a -> a caseTyApp Type fun_ty ([a] -> a forall a. [a] -> a last [a] xrs), Bool True) | Bool otherwise = (a caseWrongArg, Bool True) -- Non-decomposable (eg type function) where -- When folding over an unboxed tuple, we must explicitly drop the -- runtime rep arguments, or else GHC will generate twice as many -- variables in a unboxed tuple pattern match and expression as it -- actually needs. See Trac #12399 (xrs :: [a] xrs,xcs :: [Bool] xcs) = [(a, Bool)] -> ([a], [Bool]) forall a b. [(a, b)] -> ([a], [b]) unzip ((Type -> (a, Bool)) -> [Type] -> [(a, Bool)] forall a b. (a -> b) -> [a] -> [b] map (Bool -> Type -> (a, Bool) go Bool co) ([Type] -> [Type] dropRuntimeRepArgs [Type] args)) go co :: Bool co (ForAllTy (Bndr v :: TcTyVar v vis :: ArgFlag vis) x :: Type x) | ArgFlag -> Bool isVisibleArgFlag ArgFlag vis = String -> (a, Bool) forall a. String -> a panic "unexpected visible binder" | TcTyVar v TcTyVar -> TcTyVar -> Bool forall a. Eq a => a -> a -> Bool /= TcTyVar var Bool -> Bool -> Bool && Bool xc = (TcTyVar -> a -> a caseForAll TcTyVar v a xr,Bool True) where (xr :: a xr,xc :: Bool xc) = Bool -> Type -> (a, Bool) go Bool co Type x go _ _ = (a caseTrivial,Bool False) -- Return all syntactic subterms of ty that contain var somewhere -- These are the things that should appear in instance constraints deepSubtypesContaining :: TyVar -> Type -> [TcType] deepSubtypesContaining :: TcTyVar -> Type -> [Type] deepSubtypesContaining tv :: TcTyVar tv = TcTyVar -> FFoldType [Type] -> Type -> [Type] forall a. TcTyVar -> FFoldType a -> Type -> a functorLikeTraverse TcTyVar tv (FT :: forall a. a -> a -> a -> (a -> a -> a) -> (TyCon -> [a] -> a) -> (Type -> a -> a) -> a -> (TcTyVar -> a -> a) -> FFoldType a FT { ft_triv :: [Type] ft_triv = [] , ft_var :: [Type] ft_var = [] , ft_fun :: [Type] -> [Type] -> [Type] ft_fun = [Type] -> [Type] -> [Type] forall a. [a] -> [a] -> [a] (++) , ft_tup :: TyCon -> [[Type]] -> [Type] ft_tup = \_ xs :: [[Type]] xs -> [[Type]] -> [Type] forall (t :: * -> *) a. Foldable t => t [a] -> [a] concat [[Type]] xs , ft_ty_app :: Type -> [Type] -> [Type] ft_ty_app = (:) , ft_bad_app :: [Type] ft_bad_app = String -> [Type] forall a. String -> a panic "in other argument in deepSubtypesContaining" , ft_co_var :: [Type] ft_co_var = String -> [Type] forall a. String -> a panic "contravariant in deepSubtypesContaining" , ft_forall :: TcTyVar -> [Type] -> [Type] ft_forall = \v :: TcTyVar v xs :: [Type] xs -> (Type -> Bool) -> [Type] -> [Type] forall a. (a -> Bool) -> [a] -> [a] filterOut ((TcTyVar v TcTyVar -> VarSet -> Bool `elemVarSet`) (VarSet -> Bool) -> (Type -> VarSet) -> Type -> Bool forall b c a. (b -> c) -> (a -> b) -> a -> c . Type -> VarSet tyCoVarsOfType) [Type] xs }) foldDataConArgs :: FFoldType a -> DataCon -> [a] -- Fold over the arguments of the datacon foldDataConArgs :: FFoldType a -> DataCon -> [a] foldDataConArgs ft :: FFoldType a ft con :: DataCon con = (Type -> a) -> [Type] -> [a] forall a b. (a -> b) -> [a] -> [b] map Type -> a foldArg (DataCon -> [Type] dataConOrigArgTys DataCon con) where foldArg :: Type -> a foldArg = case Type -> Maybe TcTyVar getTyVar_maybe ([Type] -> Type forall a. [a] -> a last (Type -> [Type] tyConAppArgs (DataCon -> Type dataConOrigResTy DataCon con))) of Just tv :: TcTyVar tv -> TcTyVar -> FFoldType a -> Type -> a forall a. TcTyVar -> FFoldType a -> Type -> a functorLikeTraverse TcTyVar tv FFoldType a ft Nothing -> a -> Type -> a forall a b. a -> b -> a const (FFoldType a -> a forall a. FFoldType a -> a ft_triv FFoldType a ft) -- If we are deriving Foldable for a GADT, there is a chance that the last -- type variable in the data type isn't actually a type variable at all. -- (for example, this can happen if the last type variable is refined to -- be a concrete type such as Int). If the last type variable is refined -- to be a specific type, then getTyVar_maybe will return Nothing. -- See Note [DeriveFoldable with ExistentialQuantification] -- -- The kind checks have ensured the last type parameter is of kind *. -- Make a HsLam using a fresh variable from a State monad mkSimpleLam :: (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) -- (mkSimpleLam fn) returns (\x. fn(x)) mkSimpleLam :: (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam lam :: LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) lam = State [RdrName] [RdrName] forall s. State s s get State [RdrName] [RdrName] -> ([RdrName] -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b >>= \case n :: RdrName n:names :: [RdrName] names -> do [RdrName] -> State [RdrName] () forall s. s -> State s () put [RdrName] names LHsExpr GhcPs body <- LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) lam (IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs n) LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return ([LPat GhcPs] -> LHsExpr GhcPs -> LHsExpr GhcPs forall (p :: Pass). (XMG (GhcPass p) (LHsExpr (GhcPass p)) ~ NoExt) => [LPat (GhcPass p)] -> LHsExpr (GhcPass p) -> LHsExpr (GhcPass p) mkHsLam [IdP GhcPs -> LPat GhcPs forall (id :: Pass). IdP (GhcPass id) -> LPat (GhcPass id) nlVarPat RdrName IdP GhcPs n] LHsExpr GhcPs body) _ -> String -> State [RdrName] (LHsExpr GhcPs) forall a. String -> a panic "mkSimpleLam" mkSimpleLam2 :: (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam2 :: (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam2 lam :: LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) lam = State [RdrName] [RdrName] forall s. State s s get State [RdrName] [RdrName] -> ([RdrName] -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b >>= \case n1 :: RdrName n1:n2 :: RdrName n2:names :: [RdrName] names -> do [RdrName] -> State [RdrName] () forall s. s -> State s () put [RdrName] names LHsExpr GhcPs body <- LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) lam (IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs n1) (IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs n2) LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return ([LPat GhcPs] -> LHsExpr GhcPs -> LHsExpr GhcPs forall (p :: Pass). (XMG (GhcPass p) (LHsExpr (GhcPass p)) ~ NoExt) => [LPat (GhcPass p)] -> LHsExpr (GhcPass p) -> LHsExpr (GhcPass p) mkHsLam [IdP GhcPs -> LPat GhcPs forall (id :: Pass). IdP (GhcPass id) -> LPat (GhcPass id) nlVarPat RdrName IdP GhcPs n1,IdP GhcPs -> LPat GhcPs forall (id :: Pass). IdP (GhcPass id) -> LPat (GhcPass id) nlVarPat RdrName IdP GhcPs n2] LHsExpr GhcPs body) _ -> String -> State [RdrName] (LHsExpr GhcPs) forall a. String -> a panic "mkSimpleLam2" -- "Con a1 a2 a3 -> fold [x1 a1, x2 a2, x3 a3]" -- -- @mkSimpleConMatch fold extra_pats con insides@ produces a match clause in -- which the LHS pattern-matches on @extra_pats@, followed by a match on the -- constructor @con@ and its arguments. The RHS folds (with @fold@) over @con@ -- and its arguments, applying an expression (from @insides@) to each of the -- respective arguments of @con@. mkSimpleConMatch :: Monad m => HsMatchContext RdrName -> (RdrName -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> m (LMatch GhcPs (LHsExpr GhcPs)) mkSimpleConMatch :: HsMatchContext RdrName -> (RdrName -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs] -> m (LMatch GhcPs (LHsExpr GhcPs)) mkSimpleConMatch ctxt :: HsMatchContext RdrName ctxt fold :: RdrName -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs) fold extra_pats :: [LPat GhcPs] extra_pats con :: DataCon con insides :: [LHsExpr GhcPs] insides = do let con_name :: RdrName con_name = DataCon -> RdrName forall thing. NamedThing thing => thing -> RdrName getRdrName DataCon con let vars_needed :: [RdrName] vars_needed = [LHsExpr GhcPs] -> [RdrName] -> [RdrName] forall b a. [b] -> [a] -> [a] takeList [LHsExpr GhcPs] insides [RdrName] as_RDRs let bare_pat :: LPat GhcPs bare_pat = RdrName -> [RdrName] -> LPat GhcPs nlConVarPat RdrName con_name [RdrName] vars_needed let pat :: LPat GhcPs pat = if [RdrName] -> Bool forall (t :: * -> *) a. Foldable t => t a -> Bool null [RdrName] vars_needed then LPat GhcPs bare_pat else LPat GhcPs -> LPat GhcPs forall (name :: Pass). LPat (GhcPass name) -> LPat (GhcPass name) nlParPat LPat GhcPs bare_pat LHsExpr GhcPs rhs <- RdrName -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs) fold RdrName con_name ((LHsExpr GhcPs -> RdrName -> LHsExpr GhcPs) -> [LHsExpr GhcPs] -> [RdrName] -> [LHsExpr GhcPs] forall a b c. (a -> b -> c) -> [a] -> [b] -> [c] zipWith (\i :: LHsExpr GhcPs i v :: RdrName v -> LHsExpr GhcPs i LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) `nlHsApp` IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs v) [LHsExpr GhcPs] insides [RdrName] vars_needed) LMatch GhcPs (LHsExpr GhcPs) -> m (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return (LMatch GhcPs (LHsExpr GhcPs) -> m (LMatch GhcPs (LHsExpr GhcPs))) -> LMatch GhcPs (LHsExpr GhcPs) -> m (LMatch GhcPs (LHsExpr GhcPs)) forall a b. (a -> b) -> a -> b $ HsMatchContext (NameOrRdrName (IdP GhcPs)) -> [LPat GhcPs] -> LHsExpr GhcPs -> Located (HsLocalBinds GhcPs) -> LMatch GhcPs (LHsExpr GhcPs) forall (p :: Pass). HsMatchContext (NameOrRdrName (IdP (GhcPass p))) -> [LPat (GhcPass p)] -> LHsExpr (GhcPass p) -> Located (HsLocalBinds (GhcPass p)) -> LMatch (GhcPass p) (LHsExpr (GhcPass p)) mkMatch HsMatchContext RdrName HsMatchContext (NameOrRdrName (IdP GhcPs)) ctxt ([LPat GhcPs] extra_pats [LPat GhcPs] -> [LPat GhcPs] -> [LPat GhcPs] forall a. [a] -> [a] -> [a] ++ [LPat GhcPs pat]) LHsExpr GhcPs rhs (SrcSpanLess (Located (HsLocalBinds GhcPs)) -> Located (HsLocalBinds GhcPs) forall a. HasSrcSpan a => SrcSpanLess a -> a noLoc SrcSpanLess (Located (HsLocalBinds GhcPs)) forall (a :: Pass) (b :: Pass). HsLocalBindsLR (GhcPass a) (GhcPass b) emptyLocalBinds) -- "Con a1 a2 a3 -> fmap (\b2 -> Con a1 b2 a3) (traverse f a2)" -- -- @mkSimpleConMatch2 fold extra_pats con insides@ behaves very similarly to -- 'mkSimpleConMatch', with two key differences: -- -- 1. @insides@ is a @[Maybe (LHsExpr RdrName)]@ instead of a -- @[LHsExpr RdrName]@. This is because it filters out the expressions -- corresponding to arguments whose types do not mention the last type -- variable in a derived 'Foldable' or 'Traversable' instance (i.e., the -- 'Nothing' elements of @insides@). -- -- 2. @fold@ takes an expression as its first argument instead of a -- constructor name. This is because it uses a specialized -- constructor function expression that only takes as many parameters as -- there are argument types that mention the last type variable. -- -- See Note [Generated code for DeriveFoldable and DeriveTraversable] mkSimpleConMatch2 :: Monad m => HsMatchContext RdrName -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> m (LMatch GhcPs (LHsExpr GhcPs)) mkSimpleConMatch2 :: HsMatchContext RdrName -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> m (LMatch GhcPs (LHsExpr GhcPs)) mkSimpleConMatch2 ctxt :: HsMatchContext RdrName ctxt fold :: LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs) fold extra_pats :: [LPat GhcPs] extra_pats con :: DataCon con insides :: [Maybe (LHsExpr GhcPs)] insides = do let con_name :: RdrName con_name = DataCon -> RdrName forall thing. NamedThing thing => thing -> RdrName getRdrName DataCon con vars_needed :: [RdrName] vars_needed = [Maybe (LHsExpr GhcPs)] -> [RdrName] -> [RdrName] forall b a. [b] -> [a] -> [a] takeList [Maybe (LHsExpr GhcPs)] insides [RdrName] as_RDRs pat :: LPat GhcPs pat = RdrName -> [RdrName] -> LPat GhcPs nlConVarPat RdrName con_name [RdrName] vars_needed -- Make sure to zip BEFORE invoking catMaybes. We want the variable -- indicies in each expression to match up with the argument indices -- in con_expr (defined below). exps :: [LHsExpr GhcPs] exps = [Maybe (LHsExpr GhcPs)] -> [LHsExpr GhcPs] forall a. [Maybe a] -> [a] catMaybes ([Maybe (LHsExpr GhcPs)] -> [LHsExpr GhcPs]) -> [Maybe (LHsExpr GhcPs)] -> [LHsExpr GhcPs] forall a b. (a -> b) -> a -> b $ (Maybe (LHsExpr GhcPs) -> RdrName -> Maybe (LHsExpr GhcPs)) -> [Maybe (LHsExpr GhcPs)] -> [RdrName] -> [Maybe (LHsExpr GhcPs)] forall a b c. (a -> b -> c) -> [a] -> [b] -> [c] zipWith (\i :: Maybe (LHsExpr GhcPs) i v :: RdrName v -> (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) `nlHsApp` IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs v) (LHsExpr GhcPs -> LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b <$> Maybe (LHsExpr GhcPs) i) [Maybe (LHsExpr GhcPs)] insides [RdrName] vars_needed -- An element of argTysTyVarInfo is True if the constructor argument -- with the same index has a type which mentions the last type -- variable. argTysTyVarInfo :: [Bool] argTysTyVarInfo = (Maybe (LHsExpr GhcPs) -> Bool) -> [Maybe (LHsExpr GhcPs)] -> [Bool] forall a b. (a -> b) -> [a] -> [b] map Maybe (LHsExpr GhcPs) -> Bool forall a. Maybe a -> Bool isJust [Maybe (LHsExpr GhcPs)] insides (asWithTyVar :: [LHsExpr GhcPs] asWithTyVar, asWithoutTyVar :: [LHsExpr GhcPs] asWithoutTyVar) = [Bool] -> [LHsExpr GhcPs] -> ([LHsExpr GhcPs], [LHsExpr GhcPs]) forall a. [Bool] -> [a] -> ([a], [a]) partitionByList [Bool] argTysTyVarInfo [LHsExpr GhcPs] as_Vars con_expr :: LHsExpr GhcPs con_expr | [LHsExpr GhcPs] -> Bool forall (t :: * -> *) a. Foldable t => t a -> Bool null [LHsExpr GhcPs] asWithTyVar = IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id) nlHsApps RdrName IdP GhcPs con_name [LHsExpr GhcPs] asWithoutTyVar | Bool otherwise = let bs :: [RdrName] bs = [Bool] -> [RdrName] -> [RdrName] forall a. [Bool] -> [a] -> [a] filterByList [Bool] argTysTyVarInfo [RdrName] bs_RDRs vars :: [LHsExpr GhcPs] vars = [Bool] -> [LHsExpr GhcPs] -> [LHsExpr GhcPs] -> [LHsExpr GhcPs] forall a. [Bool] -> [a] -> [a] -> [a] filterByLists [Bool] argTysTyVarInfo [LHsExpr GhcPs] bs_Vars [LHsExpr GhcPs] as_Vars in [LPat GhcPs] -> LHsExpr GhcPs -> LHsExpr GhcPs forall (p :: Pass). (XMG (GhcPass p) (LHsExpr (GhcPass p)) ~ NoExt) => [LPat (GhcPass p)] -> LHsExpr (GhcPass p) -> LHsExpr (GhcPass p) mkHsLam ((RdrName -> LPat GhcPs) -> [RdrName] -> [LPat GhcPs] forall a b. (a -> b) -> [a] -> [b] map RdrName -> LPat GhcPs forall (id :: Pass). IdP (GhcPass id) -> LPat (GhcPass id) nlVarPat [RdrName] bs) (IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id) nlHsApps RdrName IdP GhcPs con_name [LHsExpr GhcPs] vars) LHsExpr GhcPs rhs <- LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs) fold LHsExpr GhcPs con_expr [LHsExpr GhcPs] exps LMatch GhcPs (LHsExpr GhcPs) -> m (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return (LMatch GhcPs (LHsExpr GhcPs) -> m (LMatch GhcPs (LHsExpr GhcPs))) -> LMatch GhcPs (LHsExpr GhcPs) -> m (LMatch GhcPs (LHsExpr GhcPs)) forall a b. (a -> b) -> a -> b $ HsMatchContext (NameOrRdrName (IdP GhcPs)) -> [LPat GhcPs] -> LHsExpr GhcPs -> Located (HsLocalBinds GhcPs) -> LMatch GhcPs (LHsExpr GhcPs) forall (p :: Pass). HsMatchContext (NameOrRdrName (IdP (GhcPass p))) -> [LPat (GhcPass p)] -> LHsExpr (GhcPass p) -> Located (HsLocalBinds (GhcPass p)) -> LMatch (GhcPass p) (LHsExpr (GhcPass p)) mkMatch HsMatchContext RdrName HsMatchContext (NameOrRdrName (IdP GhcPs)) ctxt ([LPat GhcPs] extra_pats [LPat GhcPs] -> [LPat GhcPs] -> [LPat GhcPs] forall a. [a] -> [a] -> [a] ++ [LPat GhcPs pat]) LHsExpr GhcPs rhs (SrcSpanLess (Located (HsLocalBinds GhcPs)) -> Located (HsLocalBinds GhcPs) forall a. HasSrcSpan a => SrcSpanLess a -> a noLoc SrcSpanLess (Located (HsLocalBinds GhcPs)) forall (a :: Pass) (b :: Pass). HsLocalBindsLR (GhcPass a) (GhcPass b) emptyLocalBinds) -- "case x of (a1,a2,a3) -> fold [x1 a1, x2 a2, x3 a3]" mkSimpleTupleCase :: Monad m => ([LPat GhcPs] -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs) mkSimpleTupleCase :: ([LPat GhcPs] -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs) mkSimpleTupleCase match_for_con :: [LPat GhcPs] -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs)) match_for_con tc :: TyCon tc insides :: [a] insides x :: LHsExpr GhcPs x = do { let data_con :: DataCon data_con = TyCon -> DataCon tyConSingleDataCon TyCon tc ; LMatch GhcPs (LHsExpr GhcPs) match <- [LPat GhcPs] -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs)) match_for_con [] DataCon data_con [a] insides ; LHsExpr GhcPs -> m (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return (LHsExpr GhcPs -> m (LHsExpr GhcPs)) -> LHsExpr GhcPs -> m (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ LHsExpr GhcPs -> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsExpr GhcPs nlHsCase LHsExpr GhcPs x [LMatch GhcPs (LHsExpr GhcPs) match] } {- ************************************************************************ * * Foldable instances see http://www.mail-archive.com/haskell-prime@haskell.org/msg02116.html * * ************************************************************************ Deriving Foldable instances works the same way as Functor instances, only Foldable instances are not possible for function types at all. Given (data T a = T a a (T a) deriving Foldable), we get: instance Foldable T where foldr f z (T x1 x2 x3) = $(foldr 'a 'a) x1 ( $(foldr 'a 'a) x2 ( $(foldr 'a '(T a)) x3 z ) ) -XDeriveFoldable is different from -XDeriveFunctor in that it filters out arguments to the constructor that would produce useless code in a Foldable instance. For example, the following datatype: data Foo a = Foo Int a Int deriving Foldable would have the following generated Foldable instance: instance Foldable Foo where foldr f z (Foo x1 x2 x3) = $(foldr 'a 'a) x2 since neither of the two Int arguments are folded over. The cases are: $(foldr 'a 'a) = f $(foldr 'a '(b1,b2)) = \x z -> case x of (x1,x2) -> $(foldr 'a 'b1) x1 ( $(foldr 'a 'b2) x2 z ) $(foldr 'a '(T b1 b2)) = \x z -> foldr $(foldr 'a 'b2) z x -- when a only occurs in the last parameter, b2 Note that the arguments to the real foldr function are the wrong way around, since (f :: a -> b -> b), while (foldr f :: b -> t a -> b). One can envision a case for types that don't contain the last type variable: $(foldr 'a 'b) = \x z -> z -- when b does not contain a But this case will never materialize, since the aforementioned filtering removes all such types from consideration. See Note [Generated code for DeriveFoldable and DeriveTraversable]. Foldable instances differ from Functor and Traversable instances in that Foldable instances can be derived for data types in which the last type variable is existentially quantified. In particular, if the last type variable is refined to a more specific type in a GADT: data GADT a where G :: a ~ Int => a -> G Int then the deriving machinery does not attempt to check that the type a contains Int, since it is not syntactically equal to a type variable. That is, the derived Foldable instance for GADT is: instance Foldable GADT where foldr _ z (GADT _) = z See Note [DeriveFoldable with ExistentialQuantification]. Note [Deriving null] ~~~~~~~~~~~~~~~~~~~~ In some cases, deriving the definition of 'null' can produce much better results than the default definition. For example, with data SnocList a = Nil | Snoc (SnocList a) a the default definition of 'null' would walk the entire spine of a nonempty snoc-list before concluding that it is not null. But looking at the Snoc constructor, we can immediately see that it contains an 'a', and so 'null' can return False immediately if it matches on Snoc. When we derive 'null', we keep track of things that cannot be null. The interesting case is type application. Given data Wrap a = Wrap (Foo (Bar a)) we use null (Wrap fba) = all null fba but if we see data Wrap a = Wrap (Foo a) we can just use null (Wrap fa) = null fa Indeed, we allow this to happen even for tuples: data Wrap a = Wrap (Foo (a, Int)) produces null (Wrap fa) = null fa As explained in Note [Deriving <$], giving tuples special performance treatment could surprise users if they switch to other types, but Ryan Scott seems to think it's okay to do it for now. -} gen_Foldable_binds :: SrcSpan -> TyCon -> (LHsBinds GhcPs, BagDerivStuff) -- When the parameter is phantom, we can use foldMap _ _ = mempty -- See Note [Phantom types with Functor, Foldable, and Traversable] gen_Foldable_binds :: SrcSpan -> TyCon -> (LHsBinds GhcPs, BagDerivStuff) gen_Foldable_binds loc :: SrcSpan loc tycon :: TyCon tycon | Role Phantom <- [Role] -> Role forall a. [a] -> a last (TyCon -> [Role] tyConRoles TyCon tycon) = (LHsBind GhcPs -> LHsBinds GhcPs forall a. a -> Bag a unitBag LHsBind GhcPs foldMap_bind, BagDerivStuff forall a. Bag a emptyBag) where foldMap_name :: GenLocated SrcSpan RdrName foldMap_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName forall l e. l -> e -> GenLocated l e L SrcSpan loc RdrName foldMap_RDR foldMap_bind :: LHsBind GhcPs foldMap_bind = GenLocated SrcSpan RdrName -> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs mkRdrFunBind GenLocated SrcSpan RdrName foldMap_name [LMatch GhcPs (LHsExpr GhcPs)] foldMap_eqns foldMap_eqns :: [LMatch GhcPs (LHsExpr GhcPs)] foldMap_eqns = [HsMatchContext (NameOrRdrName (IdP GhcPs)) -> [LPat GhcPs] -> LHsExpr GhcPs -> LMatch GhcPs (LHsExpr GhcPs) forall (p :: Pass) (body :: * -> *). HsMatchContext (NameOrRdrName (IdP (GhcPass p))) -> [LPat (GhcPass p)] -> Located (body (GhcPass p)) -> LMatch (GhcPass p) (Located (body (GhcPass p))) mkSimpleMatch HsMatchContext RdrName HsMatchContext (NameOrRdrName (IdP GhcPs)) foldMap_match_ctxt [LPat GhcPs nlWildPat, LPat GhcPs nlWildPat] LHsExpr GhcPs mempty_Expr] foldMap_match_ctxt :: HsMatchContext RdrName foldMap_match_ctxt = GenLocated SrcSpan RdrName -> HsMatchContext RdrName forall id. Located id -> HsMatchContext id mkPrefixFunRhs GenLocated SrcSpan RdrName foldMap_name gen_Foldable_binds loc :: SrcSpan loc tycon :: TyCon tycon | [DataCon] -> Bool forall (t :: * -> *) a. Foldable t => t a -> Bool null [DataCon] data_cons -- There's no real point producing anything but -- foldMap for a type with no constructors. = (LHsBind GhcPs -> LHsBinds GhcPs forall a. a -> Bag a unitBag LHsBind GhcPs foldMap_bind, BagDerivStuff forall a. Bag a emptyBag) | Bool otherwise = ([LHsBind GhcPs] -> LHsBinds GhcPs forall a. [a] -> Bag a listToBag [LHsBind GhcPs foldr_bind, LHsBind GhcPs foldMap_bind, LHsBind GhcPs null_bind], BagDerivStuff forall a. Bag a emptyBag) where data_cons :: [DataCon] data_cons = TyCon -> [DataCon] tyConDataCons TyCon tycon foldr_bind :: LHsBind GhcPs foldr_bind = GenLocated SrcSpan RdrName -> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs mkRdrFunBind (SrcSpan -> RdrName -> GenLocated SrcSpan RdrName forall l e. l -> e -> GenLocated l e L SrcSpan loc RdrName foldable_foldr_RDR) [LMatch GhcPs (LHsExpr GhcPs)] eqns eqns :: [LMatch GhcPs (LHsExpr GhcPs)] eqns = (DataCon -> LMatch GhcPs (LHsExpr GhcPs)) -> [DataCon] -> [LMatch GhcPs (LHsExpr GhcPs)] forall a b. (a -> b) -> [a] -> [b] map DataCon -> LMatch GhcPs (LHsExpr GhcPs) foldr_eqn [DataCon] data_cons foldr_eqn :: DataCon -> LMatch GhcPs (LHsExpr GhcPs) foldr_eqn con :: DataCon con = State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs) forall s a. State s a -> s -> a evalState (LHsExpr GhcPs -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_foldr LHsExpr GhcPs z_Expr [LPat GhcPs f_Pat,LPat GhcPs z_Pat] DataCon con ([Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> State [RdrName] [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b =<< State [RdrName] [Maybe (LHsExpr GhcPs)] parts) [RdrName] bs_RDRs where parts :: State [RdrName] [Maybe (LHsExpr GhcPs)] parts = [State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] [Maybe (LHsExpr GhcPs)] forall (t :: * -> *) (m :: * -> *) a. (Traversable t, Monad m) => t (m a) -> m (t a) sequence ([State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] [Maybe (LHsExpr GhcPs)]) -> [State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] [Maybe (LHsExpr GhcPs)] forall a b. (a -> b) -> a -> b $ FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs))) -> DataCon -> [State [RdrName] (Maybe (LHsExpr GhcPs))] forall a. FFoldType a -> DataCon -> [a] foldDataConArgs FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs))) ft_foldr DataCon con foldMap_name :: GenLocated SrcSpan RdrName foldMap_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName forall l e. l -> e -> GenLocated l e L SrcSpan loc RdrName foldMap_RDR -- See Note [EmptyDataDecls with Functor, Foldable, and Traversable] foldMap_bind :: LHsBind GhcPs foldMap_bind = Arity -> (LHsExpr GhcPs -> LHsExpr GhcPs) -> GenLocated SrcSpan RdrName -> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs mkRdrFunBindEC 2 (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall a b. a -> b -> a const LHsExpr GhcPs mempty_Expr) GenLocated SrcSpan RdrName foldMap_name [LMatch GhcPs (LHsExpr GhcPs)] foldMap_eqns foldMap_eqns :: [LMatch GhcPs (LHsExpr GhcPs)] foldMap_eqns = (DataCon -> LMatch GhcPs (LHsExpr GhcPs)) -> [DataCon] -> [LMatch GhcPs (LHsExpr GhcPs)] forall a b. (a -> b) -> [a] -> [b] map DataCon -> LMatch GhcPs (LHsExpr GhcPs) foldMap_eqn [DataCon] data_cons foldMap_eqn :: DataCon -> LMatch GhcPs (LHsExpr GhcPs) foldMap_eqn con :: DataCon con = State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs) forall s a. State s a -> s -> a evalState ([LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_foldMap [LPat GhcPs f_Pat] DataCon con ([Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> State [RdrName] [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b =<< State [RdrName] [Maybe (LHsExpr GhcPs)] parts) [RdrName] bs_RDRs where parts :: State [RdrName] [Maybe (LHsExpr GhcPs)] parts = [State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] [Maybe (LHsExpr GhcPs)] forall (t :: * -> *) (m :: * -> *) a. (Traversable t, Monad m) => t (m a) -> m (t a) sequence ([State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] [Maybe (LHsExpr GhcPs)]) -> [State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] [Maybe (LHsExpr GhcPs)] forall a b. (a -> b) -> a -> b $ FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs))) -> DataCon -> [State [RdrName] (Maybe (LHsExpr GhcPs))] forall a. FFoldType a -> DataCon -> [a] foldDataConArgs FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs))) ft_foldMap DataCon con -- Given a list of NullM results, produce Nothing if any of -- them is NotNull, and otherwise produce a list of Maybes -- with Justs representing unknowns and Nothings representing -- things that are definitely null. convert :: [NullM a] -> Maybe [Maybe a] convert :: [NullM a] -> Maybe [Maybe a] convert = (NullM a -> Maybe (Maybe a)) -> [NullM a] -> Maybe [Maybe a] forall (t :: * -> *) (f :: * -> *) a b. (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) traverse NullM a -> Maybe (Maybe a) forall a. NullM a -> Maybe (Maybe a) go where go :: NullM a -> Maybe (Maybe a) go IsNull = Maybe a -> Maybe (Maybe a) forall a. a -> Maybe a Just Maybe a forall a. Maybe a Nothing go NotNull = Maybe (Maybe a) forall a. Maybe a Nothing go (NullM a :: a a) = Maybe a -> Maybe (Maybe a) forall a. a -> Maybe a Just (a -> Maybe a forall a. a -> Maybe a Just a a) null_name :: GenLocated SrcSpan RdrName null_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName forall l e. l -> e -> GenLocated l e L SrcSpan loc RdrName null_RDR null_match_ctxt :: HsMatchContext RdrName null_match_ctxt = GenLocated SrcSpan RdrName -> HsMatchContext RdrName forall id. Located id -> HsMatchContext id mkPrefixFunRhs GenLocated SrcSpan RdrName null_name null_bind :: LHsBind GhcPs null_bind = GenLocated SrcSpan RdrName -> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs mkRdrFunBind GenLocated SrcSpan RdrName null_name [LMatch GhcPs (LHsExpr GhcPs)] null_eqns null_eqns :: [LMatch GhcPs (LHsExpr GhcPs)] null_eqns = (DataCon -> LMatch GhcPs (LHsExpr GhcPs)) -> [DataCon] -> [LMatch GhcPs (LHsExpr GhcPs)] forall a b. (a -> b) -> [a] -> [b] map DataCon -> LMatch GhcPs (LHsExpr GhcPs) null_eqn [DataCon] data_cons null_eqn :: DataCon -> LMatch GhcPs (LHsExpr GhcPs) null_eqn con :: DataCon con = (State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs)) -> [RdrName] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> LMatch GhcPs (LHsExpr GhcPs) forall a b c. (a -> b -> c) -> b -> a -> c flip State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs) forall s a. State s a -> s -> a evalState [RdrName] bs_RDRs (State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> LMatch GhcPs (LHsExpr GhcPs)) -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> LMatch GhcPs (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ do [NullM (LHsExpr GhcPs)] parts <- [State [RdrName] (NullM (LHsExpr GhcPs))] -> State [RdrName] [NullM (LHsExpr GhcPs)] forall (t :: * -> *) (m :: * -> *) a. (Traversable t, Monad m) => t (m a) -> m (t a) sequence ([State [RdrName] (NullM (LHsExpr GhcPs))] -> State [RdrName] [NullM (LHsExpr GhcPs)]) -> [State [RdrName] (NullM (LHsExpr GhcPs))] -> State [RdrName] [NullM (LHsExpr GhcPs)] forall a b. (a -> b) -> a -> b $ FFoldType (State [RdrName] (NullM (LHsExpr GhcPs))) -> DataCon -> [State [RdrName] (NullM (LHsExpr GhcPs))] forall a. FFoldType a -> DataCon -> [a] foldDataConArgs FFoldType (State [RdrName] (NullM (LHsExpr GhcPs))) ft_null DataCon con case [NullM (LHsExpr GhcPs)] -> Maybe [Maybe (LHsExpr GhcPs)] forall a. [NullM a] -> Maybe [Maybe a] convert [NullM (LHsExpr GhcPs)] parts of Nothing -> LMatch GhcPs (LHsExpr GhcPs) -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return (LMatch GhcPs (LHsExpr GhcPs) -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> LMatch GhcPs (LHsExpr GhcPs) -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall a b. (a -> b) -> a -> b $ HsMatchContext (NameOrRdrName (IdP GhcPs)) -> [LPat GhcPs] -> LHsExpr GhcPs -> Located (HsLocalBinds GhcPs) -> LMatch GhcPs (LHsExpr GhcPs) forall (p :: Pass). HsMatchContext (NameOrRdrName (IdP (GhcPass p))) -> [LPat (GhcPass p)] -> LHsExpr (GhcPass p) -> Located (HsLocalBinds (GhcPass p)) -> LMatch (GhcPass p) (LHsExpr (GhcPass p)) mkMatch HsMatchContext RdrName HsMatchContext (NameOrRdrName (IdP GhcPs)) null_match_ctxt [LPat GhcPs -> LPat GhcPs forall (name :: Pass). LPat (GhcPass name) -> LPat (GhcPass name) nlParPat (DataCon -> LPat GhcPs nlWildConPat DataCon con)] LHsExpr GhcPs false_Expr (SrcSpanLess (Located (HsLocalBinds GhcPs)) -> Located (HsLocalBinds GhcPs) forall a. HasSrcSpan a => SrcSpanLess a -> a noLoc SrcSpanLess (Located (HsLocalBinds GhcPs)) forall (a :: Pass) (b :: Pass). HsLocalBindsLR (GhcPass a) (GhcPass b) emptyLocalBinds) Just cp :: [Maybe (LHsExpr GhcPs)] cp -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_null [] DataCon con [Maybe (LHsExpr GhcPs)] cp -- Yields 'Just' an expression if we're folding over a type that mentions -- the last type parameter of the datatype. Otherwise, yields 'Nothing'. -- See Note [FFoldType and functorLikeTraverse] ft_foldr :: FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs))) ft_foldr :: FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs))) ft_foldr = FT :: forall a. a -> a -> a -> (a -> a -> a) -> (TyCon -> [a] -> a) -> (Type -> a -> a) -> a -> (TcTyVar -> a -> a) -> FFoldType a FT { ft_triv :: State [RdrName] (Maybe (LHsExpr GhcPs)) ft_triv = Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return Maybe (LHsExpr GhcPs) forall a. Maybe a Nothing -- foldr f = \x z -> z , ft_var :: State [RdrName] (Maybe (LHsExpr GhcPs)) ft_var = Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return (Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs))) -> Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall a b. (a -> b) -> a -> b $ LHsExpr GhcPs -> Maybe (LHsExpr GhcPs) forall a. a -> Maybe a Just LHsExpr GhcPs f_Expr -- foldr f = f , ft_tup :: TyCon -> [State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] (Maybe (LHsExpr GhcPs)) ft_tup = \t :: TyCon t g :: [State [RdrName] (Maybe (LHsExpr GhcPs))] g -> do [Maybe (LHsExpr GhcPs)] gg <- [State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] [Maybe (LHsExpr GhcPs)] forall (t :: * -> *) (m :: * -> *) a. (Traversable t, Monad m) => t (m a) -> m (t a) sequence [State [RdrName] (Maybe (LHsExpr GhcPs))] g LHsExpr GhcPs lam <- (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam2 ((LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs)) -> (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ \x :: LHsExpr GhcPs x z :: LHsExpr GhcPs z -> ([LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [Maybe (LHsExpr GhcPs)] -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => ([LPat GhcPs] -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs) mkSimpleTupleCase (LHsExpr GhcPs -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_foldr LHsExpr GhcPs z) TyCon t [Maybe (LHsExpr GhcPs)] gg LHsExpr GhcPs x Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return (LHsExpr GhcPs -> Maybe (LHsExpr GhcPs) forall a. a -> Maybe a Just LHsExpr GhcPs lam) -- foldr f = (\x z -> case x of ...) , ft_ty_app :: Type -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) ft_ty_app = \_ g :: State [RdrName] (Maybe (LHsExpr GhcPs)) g -> do Maybe (LHsExpr GhcPs) gg <- State [RdrName] (Maybe (LHsExpr GhcPs)) g (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall (t :: * -> *) (m :: * -> *) a b. (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b) mapM (\gg' :: LHsExpr GhcPs gg' -> (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam2 ((LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs)) -> (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ \x :: LHsExpr GhcPs x z :: LHsExpr GhcPs z -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id) nlHsApps RdrName IdP GhcPs foldable_foldr_RDR [LHsExpr GhcPs gg',LHsExpr GhcPs z,LHsExpr GhcPs x]) Maybe (LHsExpr GhcPs) gg -- foldr f = (\x z -> foldr g z x) , ft_forall :: TcTyVar -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) ft_forall = \_ g :: State [RdrName] (Maybe (LHsExpr GhcPs)) g -> State [RdrName] (Maybe (LHsExpr GhcPs)) g , ft_co_var :: State [RdrName] (Maybe (LHsExpr GhcPs)) ft_co_var = String -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall a. String -> a panic "contravariant in ft_foldr" , ft_fun :: State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) ft_fun = String -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall a. String -> a panic "function in ft_foldr" , ft_bad_app :: State [RdrName] (Maybe (LHsExpr GhcPs)) ft_bad_app = String -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall a. String -> a panic "in other argument in ft_foldr" } match_foldr :: LHsExpr GhcPs -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_foldr :: LHsExpr GhcPs -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_foldr z :: LHsExpr GhcPs z = HsMatchContext RdrName -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *). Monad m => HsMatchContext RdrName -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> m (LMatch GhcPs (LHsExpr GhcPs)) mkSimpleConMatch2 HsMatchContext RdrName forall id. HsMatchContext id LambdaExpr ((LHsExpr GhcPs -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall a b. (a -> b) -> a -> b $ \_ xs :: [LHsExpr GhcPs] xs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return ([LHsExpr GhcPs] -> LHsExpr GhcPs mkFoldr [LHsExpr GhcPs] xs) where -- g1 v1 (g2 v2 (.. z)) mkFoldr :: [LHsExpr GhcPs] -> LHsExpr GhcPs mkFoldr :: [LHsExpr GhcPs] -> LHsExpr GhcPs mkFoldr = (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs) -> LHsExpr GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs z -- See Note [FFoldType and functorLikeTraverse] ft_foldMap :: FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs))) ft_foldMap :: FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs))) ft_foldMap = FT :: forall a. a -> a -> a -> (a -> a -> a) -> (TyCon -> [a] -> a) -> (Type -> a -> a) -> a -> (TcTyVar -> a -> a) -> FFoldType a FT { ft_triv :: State [RdrName] (Maybe (LHsExpr GhcPs)) ft_triv = Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return Maybe (LHsExpr GhcPs) forall a. Maybe a Nothing -- foldMap f = \x -> mempty , ft_var :: State [RdrName] (Maybe (LHsExpr GhcPs)) ft_var = Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return (LHsExpr GhcPs -> Maybe (LHsExpr GhcPs) forall a. a -> Maybe a Just LHsExpr GhcPs f_Expr) -- foldMap f = f , ft_tup :: TyCon -> [State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] (Maybe (LHsExpr GhcPs)) ft_tup = \t :: TyCon t g :: [State [RdrName] (Maybe (LHsExpr GhcPs))] g -> do [Maybe (LHsExpr GhcPs)] gg <- [State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] [Maybe (LHsExpr GhcPs)] forall (t :: * -> *) (m :: * -> *) a. (Traversable t, Monad m) => t (m a) -> m (t a) sequence [State [RdrName] (Maybe (LHsExpr GhcPs))] g LHsExpr GhcPs lam <- (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs)) -> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ ([LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [Maybe (LHsExpr GhcPs)] -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => ([LPat GhcPs] -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs) mkSimpleTupleCase [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_foldMap TyCon t [Maybe (LHsExpr GhcPs)] gg Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return (LHsExpr GhcPs -> Maybe (LHsExpr GhcPs) forall a. a -> Maybe a Just LHsExpr GhcPs lam) -- foldMap f = \x -> case x of (..,) , ft_ty_app :: Type -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) ft_ty_app = \_ g :: State [RdrName] (Maybe (LHsExpr GhcPs)) g -> (LHsExpr GhcPs -> LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs foldMap_Expr) (Maybe (LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b <$> State [RdrName] (Maybe (LHsExpr GhcPs)) g -- foldMap f = foldMap g , ft_forall :: TcTyVar -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) ft_forall = \_ g :: State [RdrName] (Maybe (LHsExpr GhcPs)) g -> State [RdrName] (Maybe (LHsExpr GhcPs)) g , ft_co_var :: State [RdrName] (Maybe (LHsExpr GhcPs)) ft_co_var = String -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall a. String -> a panic "contravariant in ft_foldMap" , ft_fun :: State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) ft_fun = String -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall a. String -> a panic "function in ft_foldMap" , ft_bad_app :: State [RdrName] (Maybe (LHsExpr GhcPs)) ft_bad_app = String -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall a. String -> a panic "in other argument in ft_foldMap" } match_foldMap :: [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_foldMap :: [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_foldMap = HsMatchContext RdrName -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *). Monad m => HsMatchContext RdrName -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> m (LMatch GhcPs (LHsExpr GhcPs)) mkSimpleConMatch2 HsMatchContext RdrName forall id. HsMatchContext id CaseAlt ((LHsExpr GhcPs -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall a b. (a -> b) -> a -> b $ \_ xs :: [LHsExpr GhcPs] xs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return ([LHsExpr GhcPs] -> LHsExpr GhcPs mkFoldMap [LHsExpr GhcPs] xs) where -- mappend v1 (mappend v2 ..) mkFoldMap :: [LHsExpr GhcPs] -> LHsExpr GhcPs mkFoldMap :: [LHsExpr GhcPs] -> LHsExpr GhcPs mkFoldMap [] = LHsExpr GhcPs mempty_Expr mkFoldMap xs :: [LHsExpr GhcPs] xs = (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs) -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a foldr1 (\x :: LHsExpr GhcPs x y :: LHsExpr GhcPs y -> IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id) nlHsApps RdrName IdP GhcPs mappend_RDR [LHsExpr GhcPs x,LHsExpr GhcPs y]) [LHsExpr GhcPs] xs -- See Note [FFoldType and functorLikeTraverse] -- Yields NullM an expression if we're folding over an expression -- that may or may not be null. Yields IsNull if it's certainly -- null, and yields NotNull if it's certainly not null. -- See Note [Deriving null] ft_null :: FFoldType (State [RdrName] (NullM (LHsExpr GhcPs))) ft_null :: FFoldType (State [RdrName] (NullM (LHsExpr GhcPs))) ft_null = FT :: forall a. a -> a -> a -> (a -> a -> a) -> (TyCon -> [a] -> a) -> (Type -> a -> a) -> a -> (TcTyVar -> a -> a) -> FFoldType a FT { ft_triv :: State [RdrName] (NullM (LHsExpr GhcPs)) ft_triv = NullM (LHsExpr GhcPs) -> State [RdrName] (NullM (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return NullM (LHsExpr GhcPs) forall a. NullM a IsNull -- null = \_ -> True , ft_var :: State [RdrName] (NullM (LHsExpr GhcPs)) ft_var = NullM (LHsExpr GhcPs) -> State [RdrName] (NullM (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return NullM (LHsExpr GhcPs) forall a. NullM a NotNull -- null = \_ -> False , ft_tup :: TyCon -> [State [RdrName] (NullM (LHsExpr GhcPs))] -> State [RdrName] (NullM (LHsExpr GhcPs)) ft_tup = \t :: TyCon t g :: [State [RdrName] (NullM (LHsExpr GhcPs))] g -> do [NullM (LHsExpr GhcPs)] gg <- [State [RdrName] (NullM (LHsExpr GhcPs))] -> State [RdrName] [NullM (LHsExpr GhcPs)] forall (t :: * -> *) (m :: * -> *) a. (Traversable t, Monad m) => t (m a) -> m (t a) sequence [State [RdrName] (NullM (LHsExpr GhcPs))] g case [NullM (LHsExpr GhcPs)] -> Maybe [Maybe (LHsExpr GhcPs)] forall a. [NullM a] -> Maybe [Maybe a] convert [NullM (LHsExpr GhcPs)] gg of Nothing -> NullM (LHsExpr GhcPs) -> State [RdrName] (NullM (LHsExpr GhcPs)) forall (f :: * -> *) a. Applicative f => a -> f a pure NullM (LHsExpr GhcPs) forall a. NullM a NotNull Just ggg :: [Maybe (LHsExpr GhcPs)] ggg -> LHsExpr GhcPs -> NullM (LHsExpr GhcPs) forall a. a -> NullM a NullM (LHsExpr GhcPs -> NullM (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] (NullM (LHsExpr GhcPs)) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b <$> ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs)) -> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ ([LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [Maybe (LHsExpr GhcPs)] -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => ([LPat GhcPs] -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs) mkSimpleTupleCase [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_null TyCon t [Maybe (LHsExpr GhcPs)] ggg) -- null = \x -> case x of (..,) , ft_ty_app :: Type -> State [RdrName] (NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs)) ft_ty_app = \_ g :: State [RdrName] (NullM (LHsExpr GhcPs)) g -> ((NullM (LHsExpr GhcPs) -> NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs))) -> State [RdrName] (NullM (LHsExpr GhcPs)) -> (NullM (LHsExpr GhcPs) -> NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs)) forall a b c. (a -> b -> c) -> b -> a -> c flip (NullM (LHsExpr GhcPs) -> NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs)) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap State [RdrName] (NullM (LHsExpr GhcPs)) g ((NullM (LHsExpr GhcPs) -> NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs))) -> (NullM (LHsExpr GhcPs) -> NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs)) forall a b. (a -> b) -> a -> b $ \nestedResult :: NullM (LHsExpr GhcPs) nestedResult -> case NullM (LHsExpr GhcPs) nestedResult of -- If e definitely contains the parameter, -- then we can test if (G e) contains it by -- simply checking if (G e) is null NotNull -> LHsExpr GhcPs -> NullM (LHsExpr GhcPs) forall a. a -> NullM a NullM LHsExpr GhcPs null_Expr -- This case is unreachable--it will actually be -- caught by ft_triv IsNull -> NullM (LHsExpr GhcPs) forall a. NullM a IsNull -- The general case uses (all null), -- (all (all null)), etc. NullM nestedTest :: LHsExpr GhcPs nestedTest -> LHsExpr GhcPs -> NullM (LHsExpr GhcPs) forall a. a -> NullM a NullM (LHsExpr GhcPs -> NullM (LHsExpr GhcPs)) -> LHsExpr GhcPs -> NullM (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs all_Expr LHsExpr GhcPs nestedTest -- null fa = null fa, or null fa = all null fa, or null fa = True , ft_forall :: TcTyVar -> State [RdrName] (NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs)) ft_forall = \_ g :: State [RdrName] (NullM (LHsExpr GhcPs)) g -> State [RdrName] (NullM (LHsExpr GhcPs)) g , ft_co_var :: State [RdrName] (NullM (LHsExpr GhcPs)) ft_co_var = String -> State [RdrName] (NullM (LHsExpr GhcPs)) forall a. String -> a panic "contravariant in ft_null" , ft_fun :: State [RdrName] (NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs)) ft_fun = String -> State [RdrName] (NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs)) -> State [RdrName] (NullM (LHsExpr GhcPs)) forall a. String -> a panic "function in ft_null" , ft_bad_app :: State [RdrName] (NullM (LHsExpr GhcPs)) ft_bad_app = String -> State [RdrName] (NullM (LHsExpr GhcPs)) forall a. String -> a panic "in other argument in ft_null" } match_null :: [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_null :: [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_null = HsMatchContext RdrName -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *). Monad m => HsMatchContext RdrName -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> m (LMatch GhcPs (LHsExpr GhcPs)) mkSimpleConMatch2 HsMatchContext RdrName forall id. HsMatchContext id CaseAlt ((LHsExpr GhcPs -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall a b. (a -> b) -> a -> b $ \_ xs :: [LHsExpr GhcPs] xs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return ([LHsExpr GhcPs] -> LHsExpr GhcPs mkNull [LHsExpr GhcPs] xs) where -- v1 && v2 && .. mkNull :: [LHsExpr GhcPs] -> LHsExpr GhcPs mkNull :: [LHsExpr GhcPs] -> LHsExpr GhcPs mkNull [] = LHsExpr GhcPs true_Expr mkNull xs :: [LHsExpr GhcPs] xs = (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs) -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a foldr1 (\x :: LHsExpr GhcPs x y :: LHsExpr GhcPs y -> IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id) nlHsApps RdrName IdP GhcPs and_RDR [LHsExpr GhcPs x,LHsExpr GhcPs y]) [LHsExpr GhcPs] xs data NullM a = IsNull -- Definitely null | NotNull -- Definitely not null | NullM a -- Unknown {- ************************************************************************ * * Traversable instances see http://www.mail-archive.com/haskell-prime@haskell.org/msg02116.html * * ************************************************************************ Again, Traversable is much like Functor and Foldable. The cases are: $(traverse 'a 'a) = f $(traverse 'a '(b1,b2)) = \x -> case x of (x1,x2) -> liftA2 (,) ($(traverse 'a 'b1) x1) ($(traverse 'a 'b2) x2) $(traverse 'a '(T b1 b2)) = traverse $(traverse 'a 'b2) -- when a only occurs in the last parameter, b2 Like -XDeriveFoldable, -XDeriveTraversable filters out arguments whose types do not mention the last type parameter. Therefore, the following datatype: data Foo a = Foo Int a Int would have the following derived Traversable instance: instance Traversable Foo where traverse f (Foo x1 x2 x3) = fmap (\b2 -> Foo x1 b2 x3) ( $(traverse 'a 'a) x2 ) since the two Int arguments do not produce any effects in a traversal. One can envision a case for types that do not mention the last type parameter: $(traverse 'a 'b) = pure -- when b does not contain a But this case will never materialize, since the aforementioned filtering removes all such types from consideration. See Note [Generated code for DeriveFoldable and DeriveTraversable]. -} gen_Traversable_binds :: SrcSpan -> TyCon -> (LHsBinds GhcPs, BagDerivStuff) -- When the argument is phantom, we can use traverse = pure . coerce -- See Note [Phantom types with Functor, Foldable, and Traversable] gen_Traversable_binds :: SrcSpan -> TyCon -> (LHsBinds GhcPs, BagDerivStuff) gen_Traversable_binds loc :: SrcSpan loc tycon :: TyCon tycon | Role Phantom <- [Role] -> Role forall a. [a] -> a last (TyCon -> [Role] tyConRoles TyCon tycon) = (LHsBind GhcPs -> LHsBinds GhcPs forall a. a -> Bag a unitBag LHsBind GhcPs traverse_bind, BagDerivStuff forall a. Bag a emptyBag) where traverse_name :: GenLocated SrcSpan RdrName traverse_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName forall l e. l -> e -> GenLocated l e L SrcSpan loc RdrName traverse_RDR traverse_bind :: LHsBind GhcPs traverse_bind = GenLocated SrcSpan RdrName -> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs mkRdrFunBind GenLocated SrcSpan RdrName traverse_name [LMatch GhcPs (LHsExpr GhcPs)] traverse_eqns traverse_eqns :: [LMatch GhcPs (LHsExpr GhcPs)] traverse_eqns = [HsMatchContext (NameOrRdrName (IdP GhcPs)) -> [LPat GhcPs] -> LHsExpr GhcPs -> LMatch GhcPs (LHsExpr GhcPs) forall (p :: Pass) (body :: * -> *). HsMatchContext (NameOrRdrName (IdP (GhcPass p))) -> [LPat (GhcPass p)] -> Located (body (GhcPass p)) -> LMatch (GhcPass p) (Located (body (GhcPass p))) mkSimpleMatch HsMatchContext RdrName HsMatchContext (NameOrRdrName (IdP GhcPs)) traverse_match_ctxt [LPat GhcPs nlWildPat, LPat GhcPs z_Pat] (IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id) nlHsApps RdrName IdP GhcPs pure_RDR [LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs coerce_Expr LHsExpr GhcPs z_Expr])] traverse_match_ctxt :: HsMatchContext RdrName traverse_match_ctxt = GenLocated SrcSpan RdrName -> HsMatchContext RdrName forall id. Located id -> HsMatchContext id mkPrefixFunRhs GenLocated SrcSpan RdrName traverse_name gen_Traversable_binds loc :: SrcSpan loc tycon :: TyCon tycon = (LHsBind GhcPs -> LHsBinds GhcPs forall a. a -> Bag a unitBag LHsBind GhcPs traverse_bind, BagDerivStuff forall a. Bag a emptyBag) where data_cons :: [DataCon] data_cons = TyCon -> [DataCon] tyConDataCons TyCon tycon traverse_name :: GenLocated SrcSpan RdrName traverse_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName forall l e. l -> e -> GenLocated l e L SrcSpan loc RdrName traverse_RDR -- See Note [EmptyDataDecls with Functor, Foldable, and Traversable] traverse_bind :: LHsBind GhcPs traverse_bind = Arity -> (LHsExpr GhcPs -> LHsExpr GhcPs) -> GenLocated SrcSpan RdrName -> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs mkRdrFunBindEC 2 (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs pure_Expr) GenLocated SrcSpan RdrName traverse_name [LMatch GhcPs (LHsExpr GhcPs)] traverse_eqns traverse_eqns :: [LMatch GhcPs (LHsExpr GhcPs)] traverse_eqns = (DataCon -> LMatch GhcPs (LHsExpr GhcPs)) -> [DataCon] -> [LMatch GhcPs (LHsExpr GhcPs)] forall a b. (a -> b) -> [a] -> [b] map DataCon -> LMatch GhcPs (LHsExpr GhcPs) traverse_eqn [DataCon] data_cons traverse_eqn :: DataCon -> LMatch GhcPs (LHsExpr GhcPs) traverse_eqn con :: DataCon con = State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) -> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs) forall s a. State s a -> s -> a evalState ([LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_for_con [LPat GhcPs f_Pat] DataCon con ([Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> State [RdrName] [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b =<< State [RdrName] [Maybe (LHsExpr GhcPs)] parts) [RdrName] bs_RDRs where parts :: State [RdrName] [Maybe (LHsExpr GhcPs)] parts = [State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] [Maybe (LHsExpr GhcPs)] forall (t :: * -> *) (m :: * -> *) a. (Traversable t, Monad m) => t (m a) -> m (t a) sequence ([State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] [Maybe (LHsExpr GhcPs)]) -> [State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] [Maybe (LHsExpr GhcPs)] forall a b. (a -> b) -> a -> b $ FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs))) -> DataCon -> [State [RdrName] (Maybe (LHsExpr GhcPs))] forall a. FFoldType a -> DataCon -> [a] foldDataConArgs FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs))) ft_trav DataCon con -- Yields 'Just' an expression if we're folding over a type that mentions -- the last type parameter of the datatype. Otherwise, yields 'Nothing'. -- See Note [FFoldType and functorLikeTraverse] ft_trav :: FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs))) ft_trav :: FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs))) ft_trav = FT :: forall a. a -> a -> a -> (a -> a -> a) -> (TyCon -> [a] -> a) -> (Type -> a -> a) -> a -> (TcTyVar -> a -> a) -> FFoldType a FT { ft_triv :: State [RdrName] (Maybe (LHsExpr GhcPs)) ft_triv = Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return Maybe (LHsExpr GhcPs) forall a. Maybe a Nothing -- traverse f = pure x , ft_var :: State [RdrName] (Maybe (LHsExpr GhcPs)) ft_var = Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return (LHsExpr GhcPs -> Maybe (LHsExpr GhcPs) forall a. a -> Maybe a Just LHsExpr GhcPs f_Expr) -- traverse f = f x , ft_tup :: TyCon -> [State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] (Maybe (LHsExpr GhcPs)) ft_tup = \t :: TyCon t gs :: [State [RdrName] (Maybe (LHsExpr GhcPs))] gs -> do [Maybe (LHsExpr GhcPs)] gg <- [State [RdrName] (Maybe (LHsExpr GhcPs))] -> State [RdrName] [Maybe (LHsExpr GhcPs)] forall (t :: * -> *) (m :: * -> *) a. (Traversable t, Monad m) => t (m a) -> m (t a) sequence [State [RdrName] (Maybe (LHsExpr GhcPs))] gs LHsExpr GhcPs lam <- (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs)) -> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)) -> State [RdrName] (LHsExpr GhcPs) forall a b. (a -> b) -> a -> b $ ([LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [Maybe (LHsExpr GhcPs)] -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => ([LPat GhcPs] -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs))) -> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs) mkSimpleTupleCase [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_for_con TyCon t [Maybe (LHsExpr GhcPs)] gg Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall (m :: * -> *) a. Monad m => a -> m a return (LHsExpr GhcPs -> Maybe (LHsExpr GhcPs) forall a. a -> Maybe a Just LHsExpr GhcPs lam) -- traverse f = \x -> case x of (a1,a2,..) -> -- liftA2 (,,) (g1 a1) (g2 a2) <*> .. , ft_ty_app :: Type -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) ft_ty_app = \_ g :: State [RdrName] (Maybe (LHsExpr GhcPs)) g -> (LHsExpr GhcPs -> LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) nlHsApp LHsExpr GhcPs traverse_Expr) (Maybe (LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b <$> State [RdrName] (Maybe (LHsExpr GhcPs)) g -- traverse f = traverse g , ft_forall :: TcTyVar -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) ft_forall = \_ g :: State [RdrName] (Maybe (LHsExpr GhcPs)) g -> State [RdrName] (Maybe (LHsExpr GhcPs)) g , ft_co_var :: State [RdrName] (Maybe (LHsExpr GhcPs)) ft_co_var = String -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall a. String -> a panic "contravariant in ft_trav" , ft_fun :: State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) ft_fun = String -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall a. String -> a panic "function in ft_trav" , ft_bad_app :: State [RdrName] (Maybe (LHsExpr GhcPs)) ft_bad_app = String -> State [RdrName] (Maybe (LHsExpr GhcPs)) forall a. String -> a panic "in other argument in ft_trav" } -- Con a1 a2 ... -> liftA2 (\b1 b2 ... -> Con b1 b2 ...) (g1 a1) -- (g2 a2) <*> ... match_for_con :: [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_for_con :: [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) match_for_con = HsMatchContext RdrName -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall (m :: * -> *). Monad m => HsMatchContext RdrName -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> m (LMatch GhcPs (LHsExpr GhcPs)) mkSimpleConMatch2 HsMatchContext RdrName forall id. HsMatchContext id CaseAlt ((LHsExpr GhcPs -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))) -> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs)) -> [LPat GhcPs] -> DataCon -> [Maybe (LHsExpr GhcPs)] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)) forall a b. (a -> b) -> a -> b $ \con :: LHsExpr GhcPs con xs :: [LHsExpr GhcPs] xs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs) forall (m :: * -> *) a. Monad m => a -> m a return (LHsExpr GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs mkApCon LHsExpr GhcPs con [LHsExpr GhcPs] xs) where -- liftA2 (\b1 b2 ... -> Con b1 b2 ...) x1 x2 <*> .. mkApCon :: LHsExpr GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs mkApCon :: LHsExpr GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs mkApCon con :: LHsExpr GhcPs con [] = IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id) nlHsApps RdrName IdP GhcPs pure_RDR [LHsExpr GhcPs con] mkApCon con :: LHsExpr GhcPs con [x :: LHsExpr GhcPs x] = IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id) nlHsApps RdrName IdP GhcPs fmap_RDR [LHsExpr GhcPs con,LHsExpr GhcPs x] mkApCon con :: LHsExpr GhcPs con (x1 :: LHsExpr GhcPs x1:x2 :: LHsExpr GhcPs x2:xs :: [LHsExpr GhcPs] xs) = (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs) -> LHsExpr GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (t :: * -> *) b a. Foldable t => (b -> a -> b) -> b -> t a -> b foldl' LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs forall (id :: Pass). (IdP (GhcPass id) ~ RdrName) => LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) appAp (IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id) nlHsApps RdrName IdP GhcPs liftA2_RDR [LHsExpr GhcPs con,LHsExpr GhcPs x1,LHsExpr GhcPs x2]) [LHsExpr GhcPs] xs where appAp :: LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id) appAp x :: LHsExpr (GhcPass id) x y :: LHsExpr (GhcPass id) y = IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id) forall (id :: Pass). IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id) nlHsApps RdrName IdP (GhcPass id) ap_RDR [LHsExpr (GhcPass id) x,LHsExpr (GhcPass id) y] ----------------------------------------------------------------------- f_Expr, z_Expr, fmap_Expr, replace_Expr, mempty_Expr, foldMap_Expr, traverse_Expr, coerce_Expr, pure_Expr, true_Expr, false_Expr, all_Expr, null_Expr :: LHsExpr GhcPs f_Expr :: LHsExpr GhcPs f_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs f_RDR z_Expr :: LHsExpr GhcPs z_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs z_RDR fmap_Expr :: LHsExpr GhcPs fmap_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs fmap_RDR replace_Expr :: LHsExpr GhcPs replace_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs replace_RDR mempty_Expr :: LHsExpr GhcPs mempty_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs mempty_RDR foldMap_Expr :: LHsExpr GhcPs foldMap_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs foldMap_RDR traverse_Expr :: LHsExpr GhcPs traverse_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs traverse_RDR coerce_Expr :: LHsExpr GhcPs coerce_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar (TcTyVar -> RdrName forall thing. NamedThing thing => thing -> RdrName getRdrName TcTyVar coerceId) pure_Expr :: LHsExpr GhcPs pure_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs pure_RDR true_Expr :: LHsExpr GhcPs true_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs true_RDR false_Expr :: LHsExpr GhcPs false_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs false_RDR all_Expr :: LHsExpr GhcPs all_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs all_RDR null_Expr :: LHsExpr GhcPs null_Expr = IdP GhcPs -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar RdrName IdP GhcPs null_RDR f_RDR, z_RDR :: RdrName f_RDR :: RdrName f_RDR = FastString -> RdrName mkVarUnqual (String -> FastString fsLit "f") z_RDR :: RdrName z_RDR = FastString -> RdrName mkVarUnqual (String -> FastString fsLit "z") as_RDRs, bs_RDRs :: [RdrName] as_RDRs :: [RdrName] as_RDRs = [ FastString -> RdrName mkVarUnqual (String -> FastString mkFastString ("a"String -> String -> String forall a. [a] -> [a] -> [a] ++Arity -> String forall a. Show a => a -> String show Arity i)) | Arity i <- [(1::Int) .. ] ] bs_RDRs :: [RdrName] bs_RDRs = [ FastString -> RdrName mkVarUnqual (String -> FastString mkFastString ("b"String -> String -> String forall a. [a] -> [a] -> [a] ++Arity -> String forall a. Show a => a -> String show Arity i)) | Arity i <- [(1::Int) .. ] ] as_Vars, bs_Vars :: [LHsExpr GhcPs] as_Vars :: [LHsExpr GhcPs] as_Vars = (RdrName -> LHsExpr GhcPs) -> [RdrName] -> [LHsExpr GhcPs] forall a b. (a -> b) -> [a] -> [b] map RdrName -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar [RdrName] as_RDRs bs_Vars :: [LHsExpr GhcPs] bs_Vars = (RdrName -> LHsExpr GhcPs) -> [RdrName] -> [LHsExpr GhcPs] forall a b. (a -> b) -> [a] -> [b] map RdrName -> LHsExpr GhcPs forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id) nlHsVar [RdrName] bs_RDRs f_Pat, z_Pat :: LPat GhcPs f_Pat :: LPat GhcPs f_Pat = IdP GhcPs -> LPat GhcPs forall (id :: Pass). IdP (GhcPass id) -> LPat (GhcPass id) nlVarPat RdrName IdP GhcPs f_RDR z_Pat :: LPat GhcPs z_Pat = IdP GhcPs -> LPat GhcPs forall (id :: Pass). IdP (GhcPass id) -> LPat (GhcPass id) nlVarPat RdrName IdP GhcPs z_RDR {- Note [DeriveFoldable with ExistentialQuantification] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Functor and Traversable instances can only be derived for data types whose last type parameter is truly universally polymorphic. For example: data T a b where T1 :: b -> T a b -- YES, b is unconstrained T2 :: Ord b => b -> T a b -- NO, b is constrained by (Ord b) T3 :: b ~ Int => b -> T a b -- NO, b is constrained by (b ~ Int) T4 :: Int -> T a Int -- NO, this is just like T3 T5 :: Ord a => a -> b -> T a b -- YES, b is unconstrained, even -- though a is existential T6 :: Int -> T Int b -- YES, b is unconstrained For Foldable instances, however, we can completely lift the constraint that the last type parameter be truly universally polymorphic. This means that T (as defined above) can have a derived Foldable instance: instance Foldable (T a) where foldr f z (T1 b) = f b z foldr f z (T2 b) = f b z foldr f z (T3 b) = f b z foldr f z (T4 b) = z foldr f z (T5 a b) = f b z foldr f z (T6 a) = z foldMap f (T1 b) = f b foldMap f (T2 b) = f b foldMap f (T3 b) = f b foldMap f (T4 b) = mempty foldMap f (T5 a b) = f b foldMap f (T6 a) = mempty In a Foldable instance, it is safe to fold over an occurrence of the last type parameter that is not truly universally polymorphic. However, there is a bit of subtlety in determining what is actually an occurrence of a type parameter. T3 and T4, as defined above, provide one example: data T a b where ... T3 :: b ~ Int => b -> T a b T4 :: Int -> T a Int ... instance Foldable (T a) where ... foldr f z (T3 b) = f b z foldr f z (T4 b) = z ... foldMap f (T3 b) = f b foldMap f (T4 b) = mempty ... Notice that the argument of T3 is folded over, whereas the argument of T4 is not. This is because we only fold over constructor arguments that syntactically mention the universally quantified type parameter of that particular data constructor. See foldDataConArgs for how this is implemented. As another example, consider the following data type. The argument of each constructor has the same type as the last type parameter: data E a where E1 :: (a ~ Int) => a -> E a E2 :: Int -> E Int E3 :: (a ~ Int) => a -> E Int E4 :: (a ~ Int) => Int -> E a Only E1's argument is an occurrence of a universally quantified type variable that is syntactically equivalent to the last type parameter, so only E1's argument will be folded over in a derived Foldable instance. See Trac #10447 for the original discussion on this feature. Also see https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/DeriveFunctor for a more in-depth explanation. Note [FFoldType and functorLikeTraverse] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Deriving Functor, Foldable, and Traversable all require generating expressions which perform an operation on each argument of a data constructor depending on the argument's type. In particular, a generated operation can be different depending on whether the type mentions the last type variable of the datatype (e.g., if you have data T a = MkT a Int, then a generated foldr expression would fold over the first argument of MkT, but not the second). This pattern is abstracted with the FFoldType datatype, which provides hooks for the user to specify how a constructor argument should be folded when it has a type with a particular "shape". The shapes are as follows (assume that a is the last type variable in a given datatype): * ft_triv: The type does not mention the last type variable at all. Examples: Int, b * ft_var: The type is syntactically equal to the last type variable. Moreover, the type appears in a covariant position (see the Deriving Functor instances section of the user's guide for an in-depth explanation of covariance vs. contravariance). Example: a (covariantly) * ft_co_var: The type is syntactically equal to the last type variable. Moreover, the type appears in a contravariant position. Example: a (contravariantly) * ft_fun: A function type which mentions the last type variable in the argument position, result position or both. Examples: a -> Int, Int -> a, Maybe a -> [a] * ft_tup: A tuple type which mentions the last type variable in at least one of its fields. The TyCon argument of ft_tup represents the particular tuple's type constructor. Examples: (a, Int), (Maybe a, [a], Either a Int), (# Int, a #) * ft_ty_app: A type is being applied to the last type parameter, where the applied type does not mention the last type parameter (if it did, it would fall under ft_bad_app). The Type argument to ft_ty_app represents the applied type. Note that functions, tuples, and foralls are distinct cases and take precedence of ft_ty_app. (For example, (Int -> a) would fall under (ft_fun Int a), not (ft_ty_app ((->) Int) a). Examples: Maybe a, Either b a * ft_bad_app: A type application uses the last type parameter in a position other than the last argument. This case is singled out because Functor, Foldable, and Traversable instances cannot be derived for datatypes containing arguments with such types. Examples: Either a Int, Const a b * ft_forall: A forall'd type mentions the last type parameter on its right- hand side (and is not quantified on the left-hand side). This case is present mostly for plumbing purposes. Example: forall b. Either b a If FFoldType describes a strategy for folding subcomponents of a Type, then functorLikeTraverse is the function that applies that strategy to the entirety of a Type, returning the final folded-up result. foldDataConArgs applies functorLikeTraverse to every argument type of a constructor, returning a list of the fold results. This makes foldDataConArgs a natural way to generate the subexpressions in a generated fmap, foldr, foldMap, or traverse definition (the subexpressions must then be combined in a method-specific fashion to form the final generated expression). Deriving Generic1 also does validity checking by looking for the last type variable in certain positions of a constructor's argument types, so it also uses foldDataConArgs. See Note [degenerate use of FFoldType] in TcGenGenerics. Note [Generated code for DeriveFoldable and DeriveTraversable] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ We adapt the algorithms for -XDeriveFoldable and -XDeriveTraversable based on that of -XDeriveFunctor. However, there an important difference between deriving the former two typeclasses and the latter one, which is best illustrated by the following scenario: data WithInt a = WithInt a Int# deriving (Functor, Foldable, Traversable) The generated code for the Functor instance is straightforward: instance Functor WithInt where fmap f (WithInt a i) = WithInt (f a) i But if we use too similar of a strategy for deriving the Foldable and Traversable instances, we end up with this code: instance Foldable WithInt where foldMap f (WithInt a i) = f a <> mempty instance Traversable WithInt where traverse f (WithInt a i) = fmap WithInt (f a) <*> pure i This is unsatisfying for two reasons: 1. The Traversable instance doesn't typecheck! Int# is of kind #, but pure expects an argument whose type is of kind *. This effectively prevents Traversable from being derived for any datatype with an unlifted argument type (Trac #11174). 2. The generated code contains superfluous expressions. By the Monoid laws, we can reduce (f a <> mempty) to (f a), and by the Applicative laws, we can reduce (fmap WithInt (f a) <*> pure i) to (fmap (\b -> WithInt b i) (f a)). We can fix both of these issues by incorporating a slight twist to the usual algorithm that we use for -XDeriveFunctor. The differences can be summarized as follows: 1. In the generated expression, we only fold over arguments whose types mention the last type parameter. Any other argument types will simply produce useless 'mempty's or 'pure's, so they can be safely ignored. 2. In the case of -XDeriveTraversable, instead of applying ConName, we apply (\b_i ... b_k -> ConName a_1 ... a_n), where * ConName has n arguments * {b_i, ..., b_k} is a subset of {a_1, ..., a_n} whose indices correspond to the arguments whose types mention the last type parameter. As a consequence, taking the difference of {a_1, ..., a_n} and {b_i, ..., b_k} yields the all the argument values of ConName whose types do not mention the last type parameter. Note that [i, ..., k] is a strictly increasing—but not necessarily consecutive—integer sequence. For example, the datatype data Foo a = Foo Int a Int a would generate the following Traversable instance: instance Traversable Foo where traverse f (Foo a1 a2 a3 a4) = fmap (\b2 b4 -> Foo a1 b2 a3 b4) (f a2) <*> f a4 Technically, this approach would also work for -XDeriveFunctor as well, but we decide not to do so because: 1. There's not much benefit to generating, e.g., ((\b -> WithInt b i) (f a)) instead of (WithInt (f a) i). 2. There would be certain datatypes for which the above strategy would generate Functor code that would fail to typecheck. For example: data Bar f a = Bar (forall f. Functor f => f a) deriving Functor With the conventional algorithm, it would generate something like: fmap f (Bar a) = Bar (fmap f a) which typechecks. But with the strategy mentioned above, it would generate: fmap f (Bar a) = (\b -> Bar b) (fmap f a) which does not typecheck, since GHC cannot unify the rank-2 type variables in the types of b and (fmap f a). Note [Phantom types with Functor, Foldable, and Traversable] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Given a type F :: * -> * whose type argument has a phantom role, we can always produce lawful Functor and Traversable instances using fmap _ = coerce traverse _ = pure . coerce Indeed, these are equivalent to any *strictly lawful* instances one could write, except that this definition of 'traverse' may be lazier. That is, if instances obey the laws under true equality (rather than up to some equivalence relation), then they will be essentially equivalent to these. These definitions are incredibly cheap, so we want to use them even if it means ignoring some non-strictly-lawful instance in an embedded type. Foldable has far fewer laws to work with, which leaves us unwelcome freedom in implementing it. At a minimum, we would like to ensure that a derived foldMap is always at least as good as foldMapDefault with a derived traverse. To accomplish that, we must define foldMap _ _ = mempty in these cases. This may have different strictness properties from a standard derivation. Consider data NotAList a = Nil | Cons (NotAList a) deriving Foldable The usual deriving mechanism would produce foldMap _ Nil = mempty foldMap f (Cons x) = foldMap f x which is strict in the entire spine of the NotAList. Final point: why do we even care about such types? Users will rarely if ever map, fold, or traverse over such things themselves, but other derived instances may: data Hasn'tAList a = NotHere a (NotAList a) deriving Foldable Note [EmptyDataDecls with Functor, Foldable, and Traversable] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ There are some slightly tricky decisions to make about how to handle Functor, Foldable, and Traversable instances for types with no constructors. For fmap, the two basic options are fmap _ _ = error "Sorry, no constructors" or fmap _ z = case z of In most cases, the latter is more helpful: if the thunk passed to fmap throws an exception, we're generally going to be much more interested in that exception than in the fact that there aren't any constructors. In order to match the semantics for phantoms (see note above), we need to be a bit careful about 'traverse'. The obvious definition would be traverse _ z = case z of but this is stricter than the one for phantoms. We instead use traverse _ z = pure $ case z of For foldMap, the obvious choices are foldMap _ _ = mempty or foldMap _ z = case z of We choose the first one to be consistent with what foldMapDefault does for a derived Traversable instance. -}