    {-# LANGUAGE RankNTypes, CPP #-}
    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Data.Generics.Aliases
    -- Copyright   :  (c) The University of Glasgow, CWI 2001--2004
    -- License     :  BSD-style (see the LICENSE file)
    --
    -- Maintainer  :  generics@haskell.org
    -- Stability   :  experimental
    -- Portability :  non-portable (local universal quantification)
    --
    -- This module provides a number of declarations for typical generic
    -- function types, corresponding type case, and others.
    --
    -----------------------------------------------------------------------------

    module Data.Generics.Aliases (

            -- * Combinators which create generic functions via cast
            --
            -- $castcombinators

            -- ** Transformations
            mkT,
            extT,
            -- ** Queries
            mkQ,
            extQ,
            -- ** Monadic transformations
            mkM,
            extM,
            -- ** MonadPlus transformations
            mkMp,
            extMp,
            -- ** Readers
            mkR,
            extR,
            -- ** Builders
            extB,
            -- ** Other
            ext0,
            -- * Types for generic functions
            -- ** Transformations
            GenericT,
            GenericT'(..),
            -- ** Queries
            GenericQ,
            GenericQ'(..),
            -- ** Monadic transformations
            GenericM,
            GenericM'(..),
            -- ** Readers
            GenericR,
            -- ** Builders
            GenericB,
            -- ** Other
            Generic,
            Generic'(..),

            -- * Ingredients of generic functions
            orElse,

            -- * Function combinators on generic functions
            recoverMp,
            recoverQ,
            choiceMp,
            choiceQ,

            -- * Type extension for unary type constructors
            ext1,
            ext1T,
            ext1M,
            ext1Q,
            ext1R,
            ext1B,

            -- * Type extension for binary type constructors
            ext2,
            ext2T,
            ext2M,
            ext2Q,
            ext2R,
            ext2B

      ) where

    #ifdef __HADDOCK__
    import Prelude
    #endif
    import Control.Monad
    import Data.Data

    ------------------------------------------------------------------------------
    --
    --      Combinators to "make" generic functions
    --      We use type-safe cast in a number of ways to make generic functions.
    --
    ------------------------------------------------------------------------------

    -- $castcombinators
    --
    -- Other programming languages sometimes provide an operator @instanceof@ which
    -- can check whether an expression is an instance of a given type. This operator
    -- allows programmers to implement a function @f :: forall a. a -> a@ which exhibits
    -- a different behaviour depending on whether a `Bool` or a `Char` is passed.
    -- In Haskell this is not the case: A function with type @forall a. a -> a@
    -- can only be the identity function or a function which loops indefinitely
    -- or throws an exception. That is, it must implement exactly the same behaviour
    -- for any type at which it is used. But sometimes it is very useful to have
    -- a function which can accept (almost) any type and exhibit a different behaviour
    -- for different types. Haskell provides this functionality with the 'Typeable'
    -- typeclass, whose instances can be automatically derived by GHC for almost all
    -- types. This typeclass allows the definition of a functon 'cast' which has type
    -- @forall a b. (Typeable a, Typeable b) => a -> Maybe b@. The 'cast' function allows
    -- to implement a polymorphic function with different behaviour at different types:
    --
    -- >>> cast True :: Maybe Bool
    -- Just True
    --
    -- >>> cast True :: Maybe Int
    -- Nothing
    --
    -- This section provides combinators which make use of 'cast' internally to
    -- provide various polymorphic functions with type-specific behaviour.

    -- | Extend the identity function with a type-specific transformation.
    -- The function created by @mkT ext@ behaves like the identity function on all
    -- arguments which cannot be cast to type @b@, and like the function @ext@ otherwise.
    -- The name 'mkT' is short for "make transformation".
    --
    -- === __Examples__
    --
    -- >>> mkT not True
    -- False
    --
    -- >>> mkT not 'a'
    -- 'a'
    --
    -- @since 0.1.0.0
    mkT :: ( Typeable a
           , Typeable b
           )
        => (b -> b)
        -- ^ The type-specific transformation
        -> a
        -- ^ The argument we try to cast to type @b@
        -> a
    mkT :: forall a b. (Typeable a, Typeable b) => (b -> b) -> a -> a
    mkT = (a -> a) -> (b -> b) -> a -> a
    forall a b.
    (Typeable a, Typeable b) =>
    (a -> a) -> (b -> b) -> a -> a
    extT a -> a
    forall a. a -> a
    id

    -- | The function created by @mkQ def f@ returns the default result
    -- @def@ if its argument cannot be cast to type @b@, otherwise it returns
    -- the result of applying @f@ to its argument.
    -- The name 'mkQ' is short for "make query".
    --
    -- === __Examples__
    --
    -- >>> mkQ "default" (show :: Bool -> String) True
    -- "True"
    --
    -- >>> mkQ "default" (show :: Bool -> String) ()
    -- "default"
    --
    -- @since 0.1.0.0
    mkQ :: ( Typeable a
           , Typeable b
           )
        => r
        -- ^ The default result
        -> (b -> r)
        -- ^ The transformation to apply if the cast is successful
        -> a
        -- ^ The argument we try to cast to type @b@
        -> r
    (r
    r mkQ :: forall a b r. (Typeable a, Typeable b) => r -> (b -> r) -> a -> r
    `mkQ` b -> r
    br) a
    a = case a -> Maybe b
    forall a b. (Typeable a, Typeable b) => a -> Maybe b
    cast a
    a of
                            Just b
    b  -> b -> r
    br b
    b
                            Maybe b
    Nothing -> r
    r

    -- | Extend the default monadic action @pure :: Monad m => a -> m a@ by a type-specific
    -- monadic action. The function created by @mkM act@ behaves like 'pure' if its
    -- argument cannot be cast to type @b@, and like the monadic action @act@ otherwise.
    -- The name 'mkM' is short for "make monadic transformation".
    --
    -- === __Examples__
    --
    -- >>> mkM (\x -> [x, not x]) True
    -- [True,False]
    --
    -- >>> mkM (\x -> [x, not x]) (5 :: Int)
    -- [5]
    --
    -- @since 0.1.0.0
    mkM :: ( Monad m
           , Typeable a
           , Typeable b
           )
        => (b -> m b)
        -- ^ The type-specific monadic transformation
        -> a
        -- ^ The argument we try to cast to type @b@
        -> m a
    mkM :: forall (m :: * -> *) a b.
    (Monad m, Typeable a, Typeable b) =>
    (b -> m b) -> a -> m a
    mkM = (a -> m a) -> (b -> m b) -> a -> m a
    forall (m :: * -> *) a b.
    (Monad m, Typeable a, Typeable b) =>
    (a -> m a) -> (b -> m b) -> a -> m a
    extM a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return

    -- | Extend the default 'MonadPlus' action @const mzero@ by a type-specific 'MonadPlus'
    -- action. The function created by @mkMp act@ behaves like @const mzero@ if its argument
    -- cannot be cast to type @b@, and like the monadic action @act@ otherwise.
    -- The name 'mkMp' is short for "make MonadPlus transformation".
    --
    -- === __Examples__
    --
    -- >>> mkMp (\x -> Just (not x)) True
    -- Just False
    --
    -- >>> mkMp (\x -> Just (not x)) 'a'
    -- Nothing
    --
    -- @since 0.1.0.0
    mkMp :: ( MonadPlus m
            , Typeable a
            , Typeable b
            )
         => (b -> m b)
         -- ^ The type-specific MonadPlus action
         -> a
         -- ^ The argument we try to cast to type @b@
         -> m a
    mkMp :: forall (m :: * -> *) a b.
    (MonadPlus m, Typeable a, Typeable b) =>
    (b -> m b) -> a -> m a
    mkMp = (a -> m a) -> (b -> m b) -> a -> m a
    forall (m :: * -> *) a b.
    (Monad m, Typeable a, Typeable b) =>
    (a -> m a) -> (b -> m b) -> a -> m a
    extM (m a -> a -> m a
    forall a b. a -> b -> a
    const m a
    forall a. m a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero)

    -- | Make a generic reader from a type-specific case.
    -- The function created by @mkR f@ behaves like the reader @f@ if an expression
    -- of type @a@ can be cast to type @b@, and like the expression @mzero@ otherwise.
    -- The name 'mkR' is short for "make reader".
    --
    -- === __Examples__
    --
    -- >>> mkR (Just True) :: Maybe Bool
    -- Just True
    --
    -- >>> mkR (Just True) :: Maybe Int
    -- Nothing
    --
    -- @since 0.1.0.0
    mkR :: ( MonadPlus m
           , Typeable a
           , Typeable b
           )
        => m b
        -- ^ The type-specific reader
        -> m a
    mkR :: forall (m :: * -> *) a b.
    (MonadPlus m, Typeable a, Typeable b) =>
    m b -> m a
    mkR m b
    f = m a
    forall a. m a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero m a -> m b -> m a
    forall (m :: * -> *) a b.
    (Monad m, Typeable a, Typeable b) =>
    m a -> m b -> m a
    `extR` m b
    f

    -- | Flexible type extension
    --
    -- === __Examples__
    --
    -- >>> ext0 [1 :: Int, 2, 3] [True, False] :: [Int]
    -- [1,2,3]
    --
    -- >>> ext0 [1 :: Int, 2, 3] [4 :: Int, 5, 6] :: [Int]
    -- [4,5,6]
    --
    -- @since 0.1.0.0
    ext0 :: (Typeable a, Typeable b) => c a -> c b -> c a
    ext0 :: forall a b (c :: * -> *).
    (Typeable a, Typeable b) =>
    c a -> c b -> c a
    ext0 c a
    def c b
    ext = c a -> (c a -> c a) -> Maybe (c a) -> c a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe c a
    def c a -> c a
    forall a. a -> a
    id (c b -> Maybe (c a)
    forall {k} (a :: k) (b :: k) (c :: k -> *).
    (Typeable a, Typeable b) =>
    c a -> Maybe (c b)
    gcast c b
    ext)

    -- | Extend a generic transformation by a type-specific transformation.
    -- The function created by @extT def ext@ behaves like the generic transformation
    -- @def@ if its argument cannot be cast to the type @b@, and like the type-specific
    -- transformation @ext@ otherwise.
    -- The name 'extT' is short for "extend transformation".
    --
    -- === __Examples__
    --
    -- >>> extT id not True
    -- False
    --
    -- >>> extT id not 'a'
    -- 'a'
    --
    -- @since 0.1.0.0
    extT :: ( Typeable a
            , Typeable b
            )
         => (a -> a)
         -- ^ The transformation we want to extend
         -> (b -> b)
         -- ^ The type-specific transformation
         -> a
         -- ^ The argument we try to cast to type @b@
         -> a
    extT :: forall a b.
    (Typeable a, Typeable b) =>
    (a -> a) -> (b -> b) -> a -> a
    extT a -> a
    def b -> b
    ext = T a -> a -> a
    forall x. T x -> x -> x
    unT (((a -> a) -> T a
    forall x. (x -> x) -> T x
    T a -> a
    def) T a -> T b -> T a
    forall a b (c :: * -> *).
    (Typeable a, Typeable b) =>
    c a -> c b -> c a
    `ext0` ((b -> b) -> T b
    forall x. (x -> x) -> T x
    T b -> b
    ext))

    -- | Extend a generic query by a type-specific query. The function created by @extQ def ext@ behaves
    -- like the generic query @def@ if its argument cannot be cast to the type @b@, and like the type-specific
    -- query @ext@ otherwise.
    -- The name 'extQ' is short for "extend query".
    --
    -- === __Examples__
    --
    -- >>> extQ (const True) not True
    -- False
    --
    -- >>> extQ (const True) not 'a'
    -- True
    --
    -- @since 0.1.0.0
    extQ :: ( Typeable a
            , Typeable b
            )
         => (a -> r)
         -- ^ The query we want to extend
         -> (b -> r)
         -- ^ The type-specific query
         -> a
         -- ^ The argument we try to cast to type @b@
         -> r
    extQ :: forall a b r.
    (Typeable a, Typeable b) =>
    (a -> r) -> (b -> r) -> a -> r
    extQ a -> r
    f b -> r
    g a
    a = r -> (b -> r) -> Maybe b -> r
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe (a -> r
    f a
    a) b -> r
    g (a -> Maybe b
    forall a b. (Typeable a, Typeable b) => a -> Maybe b
    cast a
    a)

    -- | Extend a generic monadic transformation by a type-specific case.
    -- The function created by @extM def ext@ behaves like the monadic transformation
    -- @def@ if its argument cannot be cast to type @b@, and like the monadic transformation
    -- @ext@ otherwise.
    -- The name 'extM' is short for "extend monadic transformation".
    --
    -- === __Examples__
    --
    -- >>> extM (\x -> [x,x])(\x -> [not x, x]) True
    -- [False,True]
    --
    -- >>> extM (\x -> [x,x])(\x -> [not x, x]) (5 :: Int)
    -- [5,5]
    --
    -- @since 0.1.0.0
    extM :: ( Monad m
            , Typeable a
            , Typeable b
            )
         => (a -> m a)
         -- ^ The monadic transformation we want to extend
         -> (b -> m b)
         -- ^ The type-specific monadic transformation
         -> a
         -- ^ The argument we try to cast to type @b@
         -> m a
    extM :: forall (m :: * -> *) a b.
    (Monad m, Typeable a, Typeable b) =>
    (a -> m a) -> (b -> m b) -> a -> m a
    extM a -> m a
    def b -> m b
    ext = M m a -> a -> m a
    forall (m :: * -> *) x. M m x -> x -> m x
    unM (((a -> m a) -> M m a
    forall (m :: * -> *) x. (x -> m x) -> M m x
    M a -> m a
    def) M m a -> M m b -> M m a
    forall a b (c :: * -> *).
    (Typeable a, Typeable b) =>
    c a -> c b -> c a
    `ext0` ((b -> m b) -> M m b
    forall (m :: * -> *) x. (x -> m x) -> M m x
    M b -> m b
    ext))

    -- | Extend a generic MonadPlus transformation by a type-specific case.
    -- The function created by @extMp def ext@ behaves like 'MonadPlus' transformation @def@
    -- if its argument cannot be cast to type @b@, and like the transformation @ext@ otherwise.
    -- Note that 'extMp' behaves exactly like 'extM'.
    -- The name 'extMp' is short for "extend MonadPlus transformation".
    --
    -- === __Examples__
    --
    -- >>> extMp (\x -> [x,x])(\x -> [not x, x]) True
    -- [False,True]
    --
    -- >>> extMp (\x -> [x,x])(\x -> [not x, x]) (5 :: Int)
    -- [5,5]
    --
    -- @since 0.1.0.0
    extMp :: ( MonadPlus m
             , Typeable a
             , Typeable b
             )
          => (a -> m a)
          -- ^ The 'MonadPlus' transformation we want to extend
          -> (b -> m b)
          -- ^ The type-specific 'MonadPlus' transformation
          -> a
          -- ^ The argument we try to cast to type @b@
          -> m a
    extMp :: forall (m :: * -> *) a b.
    (MonadPlus m, Typeable a, Typeable b) =>
    (a -> m a) -> (b -> m b) -> a -> m a
    extMp = (a -> m a) -> (b -> m b) -> a -> m a
    forall (m :: * -> *) a b.
    (Monad m, Typeable a, Typeable b) =>
    (a -> m a) -> (b -> m b) -> a -> m a
    extM

    -- | Extend a generic builder by a type-specific case.
    -- The builder created by @extB def ext@ returns @def@ if @ext@ cannot be cast
    -- to type @a@, and like @ext@ otherwise.
    -- The name 'extB' is short for "extend builder".
    --
    -- === __Examples__
    --
    -- >>> extB True 'a'
    -- True
    --
    -- >>> extB True False
    -- False
    --
    -- @since 0.1.0.0
    extB :: ( Typeable a
            , Typeable b
            )
         => a
         -- ^ The default result
         -> b
         -- ^ The argument we try to cast to type @a@
         -> a
    extB :: forall a b. (Typeable a, Typeable b) => a -> b -> a
    extB a
    a = a -> (a -> a) -> Maybe a -> a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe a
    a a -> a
    forall a. a -> a
    id (Maybe a -> a) -> (b -> Maybe a) -> b -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . b -> Maybe a
    forall a b. (Typeable a, Typeable b) => a -> Maybe b
    cast

    -- | Extend a generic reader by a type-specific case.
    -- The reader created by @extR def ext@ behaves like the reader @def@
    -- if expressions of type @b@ cannot be cast to type @a@, and like the
    -- reader @ext@ otherwise.
    -- The name 'extR' is short for "extend reader".
    --
    -- === __Examples__
    --
    -- >>> extR (Just True) (Just 'a')
    -- Just True
    --
    -- >>> extR (Just True) (Just False)
    -- Just False
    --
    -- @since 0.1.0.0
    extR :: ( Monad m
            , Typeable a
            , Typeable b
            )
         => m a
         -- ^ The generic reader we want to extend
         -> m b
         -- ^ The type-specific reader
         -> m a
    extR :: forall (m :: * -> *) a b.
    (Monad m, Typeable a, Typeable b) =>
    m a -> m b -> m a
    extR m a
    def m b
    ext = R m a -> m a
    forall (m :: * -> *) x. R m x -> m x
    unR ((m a -> R m a
    forall (m :: * -> *) x. m x -> R m x
    R m a
    def) R m a -> R m b -> R m a
    forall a b (c :: * -> *).
    (Typeable a, Typeable b) =>
    c a -> c b -> c a
    `ext0` (m b -> R m b
    forall (m :: * -> *) x. m x -> R m x
    R m b
    ext))

    ------------------------------------------------------------------------------
    --
    --      Types for generic functions
    --
    ------------------------------------------------------------------------------

    -- | Generic transformations,
    --   i.e., take an \"a\" and return an \"a\"
    --
    -- @since 0.1.0.0
    type GenericT = forall a. Data a => a -> a

    -- | The type synonym `GenericT` has a polymorphic type, and can therefore not
    --   appear in places where monomorphic types are expected, for example in a list.
    --   The newtype `GenericT'` wraps `GenericT` in a newtype to lift this restriction.
    --
    -- @since 0.1.0.0
    newtype GenericT' = GT { GenericT' -> GenericT
    unGT :: GenericT }

    -- | Generic queries of type \"r\",
    --   i.e., take any \"a\" and return an \"r\"
    --
    -- @since 0.1.0.0
    type GenericQ r = forall a. Data a => a -> r

    -- | The type synonym `GenericQ` has a polymorphic type, and can therefore not
    --   appear in places where monomorphic types are expected, for example in a list.
    --   The newtype `GenericQ'` wraps `GenericQ` in a newtype to lift this restriction.
    --
    -- @since 0.1.0.0
    newtype GenericQ' r = GQ { forall r. GenericQ' r -> GenericQ r
    unGQ :: GenericQ r }

    -- | Generic monadic transformations,
    --   i.e., take an \"a\" and compute an \"a\"
    --
    -- @since 0.1.0.0
    type GenericM m = forall a. Data a => a -> m a

    -- | The type synonym `GenericM` has a polymorphic type, and can therefore not
    --   appear in places where monomorphic types are expected, for example in a list.
    --   The newtype `GenericM'` wraps `GenericM` in a newtype to lift this restriction.
    --
    -- @since 0.1.0.0
    newtype GenericM' m = GM { forall (m :: * -> *). GenericM' m -> GenericM m
    unGM :: GenericM m }

    -- | Generic builders
    --   i.e., produce an \"a\".
    --
    -- @since 0.1.0.0
    type GenericB = forall a. Data a => a

    -- | Generic readers, say monadic builders,
    --   i.e., produce an \"a\" with the help of a monad \"m\".
    --
    -- @since 0.1.0.0
    type GenericR m = forall a. Data a => m a

    -- | The general scheme underlying generic functions
    --   assumed by gfoldl; there are isomorphisms such as
    --   GenericT = Generic T.
    --
    -- @since 0.1.0.0
    type Generic c = forall a. Data a => a -> c a

    -- | The type synonym `Generic` has a polymorphic type, and can therefore not
    --   appear in places where monomorphic types are expected, for example in a list.
    --   The data type `Generic'` wraps `Generic` in a data type to lift this restriction.
    --
    -- @since 0.1.0.0
    data Generic' c = Generic' { forall (c :: * -> *). Generic' c -> Generic c
    unGeneric' :: Generic c }

    ------------------------------------------------------------------------------
    --
    -- Ingredients of generic functions
    --
    ------------------------------------------------------------------------------

    -- | Left-biased choice on maybes
    --
    -- === __Examples__
    --
    -- >>> orElse Nothing Nothing
    -- Nothing
    --
    -- >>> orElse Nothing (Just 'a')
    -- Just 'a'
    --
    -- >>> orElse (Just 'a') Nothing
    -- Just 'a'
    --
    -- >>> orElse (Just 'a') (Just 'b')
    -- Just 'a'
    --
    -- @since 0.1.0.0
    orElse :: Maybe a -> Maybe a -> Maybe a
    Maybe a
    x orElse :: forall a. Maybe a -> Maybe a -> Maybe a
    `orElse` Maybe a
    y = case Maybe a
    x of
                     Just a
    _  -> Maybe a
    x
                     Maybe a
    Nothing -> Maybe a
    y

    ------------------------------------------------------------------------------
    --
    -- Function combinators on generic functions
    --
    ------------------------------------------------------------------------------
    {-

    The following variations take "orElse" to the function
    level. Furthermore, we generalise from "Maybe" to any
    "MonadPlus". This makes sense for monadic transformations and
    queries. We say that the resulting combinators modell choice. We also
    provide a prime example of choice, that is, recovery from failure. In
    the case of transformations, we recover via return whereas for
    queries a given constant is returned.

    -}

    -- | Choice for monadic transformations
    --
    -- @since 0.1.0.0
    choiceMp :: MonadPlus m => GenericM m -> GenericM m -> GenericM m
    choiceMp :: forall (m :: * -> *).
    MonadPlus m =>
    GenericM m -> GenericM m -> GenericM m
    choiceMp GenericM m
    f GenericM m
    g a
    x = a -> m a
    GenericM m
    f a
    x m a -> m a -> m a
    forall a. m a -> m a -> m a
    forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
    `mplus` a -> m a
    GenericM m
    g a
    x

    -- | Choice for monadic queries
    --
    -- @since 0.1.0.0
    choiceQ :: MonadPlus m => GenericQ (m r) -> GenericQ (m r) -> GenericQ (m r)
    choiceQ :: forall (m :: * -> *) r.
    MonadPlus m =>
    GenericQ (m r) -> GenericQ (m r) -> GenericQ (m r)
    choiceQ GenericQ (m r)
    f GenericQ (m r)
    g a
    x = a -> m r
    GenericQ (m r)
    f a
    x m r -> m r -> m r
    forall a. m a -> m a -> m a
    forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
    `mplus` a -> m r
    GenericQ (m r)
    g a
    x

    -- | Recover from the failure of monadic transformation by identity
    --
    -- @since 0.1.0.0
    recoverMp :: MonadPlus m => GenericM m -> GenericM m
    recoverMp :: forall (m :: * -> *). MonadPlus m => GenericM m -> GenericM m
    recoverMp GenericM m
    f = a -> m a
    GenericM m
    f GenericM m -> GenericM m -> GenericM m
    forall (m :: * -> *).
    MonadPlus m =>
    GenericM m -> GenericM m -> GenericM m
    `choiceMp` a -> m a
    forall a. a -> m a
    GenericM m
    forall (m :: * -> *) a. Monad m => a -> m a
    return

    -- | Recover from the failure of monadic query by a constant
    --
    -- @since 0.1.0.0
    recoverQ :: MonadPlus m => r -> GenericQ (m r) -> GenericQ (m r)
    recoverQ :: forall (m :: * -> *) r.
    MonadPlus m =>
    r -> GenericQ (m r) -> GenericQ (m r)
    recoverQ r
    r GenericQ (m r)
    f = a -> m r
    GenericQ (m r)
    f GenericQ (m r) -> GenericQ (m r) -> GenericQ (m r)
    forall (m :: * -> *) r.
    MonadPlus m =>
    GenericQ (m r) -> GenericQ (m r) -> GenericQ (m r)
    `choiceQ` m r -> a -> m r
    forall a b. a -> b -> a
    const (r -> m r
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return r
    r)

    ------------------------------------------------------------------------------
    --      Type extension for unary type constructors
    ------------------------------------------------------------------------------

    #if __GLASGOW_HASKELL__ >= 707
    #define Typeable1 Typeable
    #define Typeable2 Typeable
    #endif

    -- | Flexible type extension
    --
    -- @since 0.3
    ext1 :: (Data a, Typeable1 t)
         => c a
         -> (forall d. Data d => c (t d))
         -> c a
    ext1 :: forall a (t :: * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    c a -> (forall d. Data d => c (t d)) -> c a
    ext1 c a
    def forall d. Data d => c (t d)
    ext = c a -> (c a -> c a) -> Maybe (c a) -> c a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe c a
    def c a -> c a
    forall a. a -> a
    id ((forall d. Data d => c (t d)) -> Maybe (c a)
    forall a (t :: * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    (forall d. Data d => c (t d)) -> Maybe (c a)
    forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a)
    dataCast1 c (t d)
    forall d. Data d => c (t d)
    ext)

    -- | Type extension of transformations for unary type constructors
    --
    -- @since 0.1.0.0
    ext1T :: (Data d, Typeable1 t)
          => (forall e. Data e => e -> e)
          -> (forall f. Data f => t f -> t f)
          -> d -> d
    ext1T :: forall d (t :: * -> *).
    (Data d, Typeable t) =>
    GenericT -> (forall f. Data f => t f -> t f) -> d -> d
    ext1T GenericT
    def forall f. Data f => t f -> t f
    ext = T d -> d -> d
    forall x. T x -> x -> x
    unT (((d -> d) -> T d
    forall x. (x -> x) -> T x
    T d -> d
    GenericT
    def) T d -> (forall d. Data d => T (t d)) -> T d
    forall a (t :: * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    c a -> (forall d. Data d => c (t d)) -> c a
    `ext1` ((t d -> t d) -> T (t d)
    forall x. (x -> x) -> T x
    T t d -> t d
    forall f. Data f => t f -> t f
    ext))

    -- | Type extension of monadic transformations for type constructors
    --
    -- @since 0.1.0.0
    ext1M :: (Monad m, Data d, Typeable1 t)
          => (forall e. Data e => e -> m e)
          -> (forall f. Data f => t f -> m (t f))
          -> d -> m d
    ext1M :: forall (m :: * -> *) d (t :: * -> *).
    (Monad m, Data d, Typeable t) =>
    (forall e. Data e => e -> m e)
    -> (forall f. Data f => t f -> m (t f)) -> d -> m d
    ext1M forall e. Data e => e -> m e
    def forall f. Data f => t f -> m (t f)
    ext = M m d -> d -> m d
    forall (m :: * -> *) x. M m x -> x -> m x
    unM (((d -> m d) -> M m d
    forall (m :: * -> *) x. (x -> m x) -> M m x
    M d -> m d
    forall e. Data e => e -> m e
    def) M m d -> (forall d. Data d => M m (t d)) -> M m d
    forall a (t :: * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    c a -> (forall d. Data d => c (t d)) -> c a
    `ext1` ((t d -> m (t d)) -> M m (t d)
    forall (m :: * -> *) x. (x -> m x) -> M m x
    M t d -> m (t d)
    forall f. Data f => t f -> m (t f)
    ext))

    -- | Type extension of queries for type constructors
    --
    -- @since 0.1.0.0
    ext1Q :: (Data d, Typeable1 t)
          => (d -> q)
          -> (forall e. Data e => t e -> q)
          -> d -> q
    ext1Q :: forall d (t :: * -> *) q.
    (Data d, Typeable t) =>
    (d -> q) -> (forall e. Data e => t e -> q) -> d -> q
    ext1Q d -> q
    def forall e. Data e => t e -> q
    ext = Q q d -> d -> q
    forall q x. Q q x -> x -> q
    unQ (((d -> q) -> Q q d
    forall q x. (x -> q) -> Q q x
    Q d -> q
    def) Q q d -> (forall d. Data d => Q q (t d)) -> Q q d
    forall a (t :: * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    c a -> (forall d. Data d => c (t d)) -> c a
    `ext1` ((t d -> q) -> Q q (t d)
    forall q x. (x -> q) -> Q q x
    Q t d -> q
    forall e. Data e => t e -> q
    ext))

    -- | Type extension of readers for type constructors
    --
    -- @since 0.1.0.0
    ext1R :: (Monad m, Data d, Typeable1 t)
          => m d
          -> (forall e. Data e => m (t e))
          -> m d
    ext1R :: forall (m :: * -> *) d (t :: * -> *).
    (Monad m, Data d, Typeable t) =>
    m d -> (forall e. Data e => m (t e)) -> m d
    ext1R m d
    def forall e. Data e => m (t e)
    ext = R m d -> m d
    forall (m :: * -> *) x. R m x -> m x
    unR ((m d -> R m d
    forall (m :: * -> *) x. m x -> R m x
    R m d
    def) R m d -> (forall d. Data d => R m (t d)) -> R m d
    forall a (t :: * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    c a -> (forall d. Data d => c (t d)) -> c a
    `ext1` (m (t d) -> R m (t d)
    forall (m :: * -> *) x. m x -> R m x
    R m (t d)
    forall e. Data e => m (t e)
    ext))

    -- | Type extension of builders for type constructors
    --
    -- @since 0.2
    ext1B :: (Data a, Typeable1 t)
          => a
          -> (forall b. Data b => (t b))
          -> a
    ext1B :: forall a (t :: * -> *).
    (Data a, Typeable t) =>
    a -> (forall b. Data b => t b) -> a
    ext1B a
    def forall b. Data b => t b
    ext = B a -> a
    forall x. B x -> x
    unB ((a -> B a
    forall x. x -> B x
    B a
    def) B a -> (forall d. Data d => B (t d)) -> B a
    forall a (t :: * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    c a -> (forall d. Data d => c (t d)) -> c a
    `ext1` (t d -> B (t d)
    forall x. x -> B x
    B t d
    forall b. Data b => t b
    ext))

    ------------------------------------------------------------------------------
    --      Type extension for binary type constructors
    ------------------------------------------------------------------------------

    -- | Flexible type extension
    ext2 :: (Data a, Typeable2 t)
         => c a
         -> (forall d1 d2. (Data d1, Data d2) => c (t d1 d2))
         -> c a
    ext2 :: forall a (t :: * -> * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    c a -> (forall d1 d2. (Data d1, Data d2) => c (t d1 d2)) -> c a
    ext2 c a
    def forall d1 d2. (Data d1, Data d2) => c (t d1 d2)
    ext = c a -> (c a -> c a) -> Maybe (c a) -> c a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe c a
    def c a -> c a
    forall a. a -> a
    id ((forall d1 d2. (Data d1, Data d2) => c (t d1 d2)) -> Maybe (c a)
    forall a (t :: * -> * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)
    forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)
    dataCast2 c (t d e)
    forall d1 d2. (Data d1, Data d2) => c (t d1 d2)
    ext)

    -- | Type extension of transformations for unary type constructors
    --
    -- @since 0.3
    ext2T :: (Data d, Typeable2 t)
          => (forall e. Data e => e -> e)
          -> (forall d1 d2. (Data d1, Data d2) => t d1 d2 -> t d1 d2)
          -> d -> d
    ext2T :: forall d (t :: * -> * -> *).
    (Data d, Typeable t) =>
    GenericT
    -> (forall d1 d2. (Data d1, Data d2) => t d1 d2 -> t d1 d2)
    -> d
    -> d
    ext2T GenericT
    def forall d1 d2. (Data d1, Data d2) => t d1 d2 -> t d1 d2
    ext = T d -> d -> d
    forall x. T x -> x -> x
    unT (((d -> d) -> T d
    forall x. (x -> x) -> T x
    T d -> d
    GenericT
    def) T d -> (forall d1 d2. (Data d1, Data d2) => T (t d1 d2)) -> T d
    forall a (t :: * -> * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    c a -> (forall d1 d2. (Data d1, Data d2) => c (t d1 d2)) -> c a
    `ext2` ((t d1 d2 -> t d1 d2) -> T (t d1 d2)
    forall x. (x -> x) -> T x
    T t d1 d2 -> t d1 d2
    forall d1 d2. (Data d1, Data d2) => t d1 d2 -> t d1 d2
    ext))

    -- | Type extension of monadic transformations for type constructors
    --
    -- @since 0.3
    ext2M :: (Monad m, Data d, Typeable2 t)
          => (forall e. Data e => e -> m e)
          -> (forall d1 d2. (Data d1, Data d2) => t d1 d2 -> m (t d1 d2))
          -> d -> m d
    ext2M :: forall (m :: * -> *) d (t :: * -> * -> *).
    (Monad m, Data d, Typeable t) =>
    (forall e. Data e => e -> m e)
    -> (forall d1 d2. (Data d1, Data d2) => t d1 d2 -> m (t d1 d2))
    -> d
    -> m d
    ext2M forall e. Data e => e -> m e
    def forall d1 d2. (Data d1, Data d2) => t d1 d2 -> m (t d1 d2)
    ext = M m d -> d -> m d
    forall (m :: * -> *) x. M m x -> x -> m x
    unM (((d -> m d) -> M m d
    forall (m :: * -> *) x. (x -> m x) -> M m x
    M d -> m d
    forall e. Data e => e -> m e
    def) M m d
    -> (forall d1 d2. (Data d1, Data d2) => M m (t d1 d2)) -> M m d
    forall a (t :: * -> * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    c a -> (forall d1 d2. (Data d1, Data d2) => c (t d1 d2)) -> c a
    `ext2` ((t d1 d2 -> m (t d1 d2)) -> M m (t d1 d2)
    forall (m :: * -> *) x. (x -> m x) -> M m x
    M t d1 d2 -> m (t d1 d2)
    forall d1 d2. (Data d1, Data d2) => t d1 d2 -> m (t d1 d2)
    ext))

    -- | Type extension of queries for type constructors
    --
    -- @since 0.3
    ext2Q :: (Data d, Typeable2 t)
          => (d -> q)
          -> (forall d1 d2. (Data d1, Data d2) => t d1 d2 -> q)
          -> d -> q
    ext2Q :: forall d (t :: * -> * -> *) q.
    (Data d, Typeable t) =>
    (d -> q)
    -> (forall d1 d2. (Data d1, Data d2) => t d1 d2 -> q) -> d -> q
    ext2Q d -> q
    def forall d1 d2. (Data d1, Data d2) => t d1 d2 -> q
    ext = Q q d -> d -> q
    forall q x. Q q x -> x -> q
    unQ (((d -> q) -> Q q d
    forall q x. (x -> q) -> Q q x
    Q d -> q
    def) Q q d
    -> (forall d1 d2. (Data d1, Data d2) => Q q (t d1 d2)) -> Q q d
    forall a (t :: * -> * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    c a -> (forall d1 d2. (Data d1, Data d2) => c (t d1 d2)) -> c a
    `ext2` ((t d1 d2 -> q) -> Q q (t d1 d2)
    forall q x. (x -> q) -> Q q x
    Q t d1 d2 -> q
    forall d1 d2. (Data d1, Data d2) => t d1 d2 -> q
    ext))

    -- | Type extension of readers for type constructors
    --
    -- @since 0.3
    ext2R :: (Monad m, Data d, Typeable2 t)
          => m d
          -> (forall d1 d2. (Data d1, Data d2) => m (t d1 d2))
          -> m d
    ext2R :: forall (m :: * -> *) d (t :: * -> * -> *).
    (Monad m, Data d, Typeable t) =>
    m d -> (forall d1 d2. (Data d1, Data d2) => m (t d1 d2)) -> m d
    ext2R m d
    def forall d1 d2. (Data d1, Data d2) => m (t d1 d2)
    ext = R m d -> m d
    forall (m :: * -> *) x. R m x -> m x
    unR ((m d -> R m d
    forall (m :: * -> *) x. m x -> R m x
    R m d
    def) R m d
    -> (forall d1 d2. (Data d1, Data d2) => R m (t d1 d2)) -> R m d
    forall a (t :: * -> * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    c a -> (forall d1 d2. (Data d1, Data d2) => c (t d1 d2)) -> c a
    `ext2` (m (t d1 d2) -> R m (t d1 d2)
    forall (m :: * -> *) x. m x -> R m x
    R m (t d1 d2)
    forall d1 d2. (Data d1, Data d2) => m (t d1 d2)
    ext))

    -- | Type extension of builders for type constructors
    --
    -- @since 0.3
    ext2B :: (Data a, Typeable2 t)
          => a
          -> (forall d1 d2. (Data d1, Data d2) => (t d1 d2))
          -> a
    ext2B :: forall a (t :: * -> * -> *).
    (Data a, Typeable t) =>
    a -> (forall d1 d2. (Data d1, Data d2) => t d1 d2) -> a
    ext2B a
    def forall d1 d2. (Data d1, Data d2) => t d1 d2
    ext = B a -> a
    forall x. B x -> x
    unB ((a -> B a
    forall x. x -> B x
    B a
    def) B a -> (forall d1 d2. (Data d1, Data d2) => B (t d1 d2)) -> B a
    forall a (t :: * -> * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    c a -> (forall d1 d2. (Data d1, Data d2) => c (t d1 d2)) -> c a
    `ext2` (t d1 d2 -> B (t d1 d2)
    forall x. x -> B x
    B t d1 d2
    forall d1 d2. (Data d1, Data d2) => t d1 d2
    ext))

    ------------------------------------------------------------------------------
    --
    --      Type constructors for type-level lambdas
    --
    ------------------------------------------------------------------------------

    -- | The type constructor for transformations
    newtype T x = T { forall x. T x -> x -> x
    unT :: x -> x }

    -- | The type constructor for transformations
    newtype M m x = M { forall (m :: * -> *) x. M m x -> x -> m x
    unM :: x -> m x }

    -- | The type constructor for queries
    newtype Q q x = Q { forall q x. Q q x -> x -> q
    unQ :: x -> q }

    -- | The type constructor for readers
    newtype R m x = R { forall (m :: * -> *) x. R m x -> m x
    unR :: m x }

    -- | The type constructor for builders
    newtype B x = B {forall x. B x -> x
    unB :: x}