    -- | Tree traversal for internal syntax.

    module Agda.Syntax.Internal.Generic where

    import Agda.Syntax.Common
    import Agda.Syntax.Internal
    import Agda.Utils.Functor
    import Agda.Utils.List1 (List1)

    -- | Generic term traversal.
    --
    --   Note: ignores sorts in terms!
    --   (Does not traverse into or collect from them.)

    class TermLike a where

      -- | Generic traversal with post-traversal action.
      --   Ignores sorts.
      traverseTermM :: Monad m => (Term -> m Term) -> a -> m a

      default traverseTermM :: (Monad m, Traversable f, TermLike b, f b ~ a)
                            => (Term -> m Term) -> a -> m a
      traverseTermM = (b -> m b) -> a -> m a
    (b -> m b) -> f b -> m (f b)
    forall (t :: * -> *) (f :: * -> *) a b.
    (Traversable t, Applicative f) =>
    (a -> f b) -> t a -> f (t b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> f a -> f (f b)
    traverse ((b -> m b) -> a -> m a)
    -> ((Term -> m Term) -> b -> m b) -> (Term -> m Term) -> a -> m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Term -> m Term) -> b -> m b
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> b -> m b
    traverseTermM

      -- | Generic fold, ignoring sorts.
      foldTerm :: Monoid m => (Term -> m) -> a -> m

      default foldTerm
        :: (Monoid m, Foldable f, TermLike b, f b ~ a) => (Term -> m) -> a -> m
      foldTerm = (b -> m) -> a -> m
    (b -> m) -> f b -> m
    forall m a. Monoid m => (a -> m) -> f a -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    foldMap ((b -> m) -> a -> m)
    -> ((Term -> m) -> b -> m) -> (Term -> m) -> a -> m
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Term -> m) -> b -> m
    forall m. Monoid m => (Term -> m) -> b -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm

    -- Constants

    instance TermLike Bool where
      traverseTermM :: forall (m :: * -> *). Monad m => (Term -> m Term) -> Bool -> m Bool
    traverseTermM Term -> m Term
    _ = Bool -> m Bool
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure
      foldTerm :: forall m. Monoid m => (Term -> m) -> Bool -> m
    foldTerm Term -> m
    _      = Bool -> m
    forall a. Monoid a => a
    mempty

    instance TermLike Int where
      traverseTermM :: forall (m :: * -> *). Monad m => (Term -> m Term) -> Int -> m Int
    traverseTermM Term -> m Term
    _ = Int -> m Int
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure
      foldTerm :: forall m. Monoid m => (Term -> m) -> Int -> m
    foldTerm Term -> m
    _      = Int -> m
    forall a. Monoid a => a
    mempty

    instance TermLike Integer where
      traverseTermM :: forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Integer -> m Integer
    traverseTermM Term -> m Term
    _ = Integer -> m Integer
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure
      foldTerm :: forall m. Monoid m => (Term -> m) -> Integer -> m
    foldTerm Term -> m
    _      = Integer -> m
    forall a. Monoid a => a
    mempty

    instance TermLike Char where
      traverseTermM :: forall (m :: * -> *). Monad m => (Term -> m Term) -> Char -> m Char
    traverseTermM Term -> m Term
    _ = Char -> m Char
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure
      foldTerm :: forall m. Monoid m => (Term -> m) -> Char -> m
    foldTerm Term -> m
    _      = Char -> m
    forall a. Monoid a => a
    mempty

    instance TermLike QName where
      traverseTermM :: forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> QName -> m QName
    traverseTermM Term -> m Term
    _ = QName -> m QName
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure
      foldTerm :: forall m. Monoid m => (Term -> m) -> QName -> m
    foldTerm Term -> m
    _      = QName -> m
    forall a. Monoid a => a
    mempty

    -- Functors

    instance TermLike a => TermLike (Elim' a)      where
    instance TermLike a => TermLike (Arg a)        where
    instance TermLike a => TermLike (Dom a)        where
    instance TermLike a => TermLike [a]            where
    instance TermLike a => TermLike (List1 a)      where
    instance TermLike a => TermLike (Maybe a)      where
    instance TermLike a => TermLike (Blocked a)    where
    instance TermLike a => TermLike (Abs a)        where
    instance TermLike a => TermLike (Tele a)       where
    instance TermLike a => TermLike (WithHiding a) where

    -- Tuples

    instance (TermLike a, TermLike b) => TermLike (a, b) where
      traverseTermM :: forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> (a, b) -> m (a, b)
    traverseTermM Term -> m Term
    f (a
    x, b
    y) = (,) (a -> b -> (a, b)) -> m a -> m (b -> (a, b))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> a -> m a
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> a -> m a
    traverseTermM Term -> m Term
    f a
    x m (b -> (a, b)) -> m b -> m (a, b)
    forall a b. m (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Term -> m Term) -> b -> m b
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> b -> m b
    traverseTermM Term -> m Term
    f b
    y
      foldTerm :: forall m. Monoid m => (Term -> m) -> (a, b) -> m
    foldTerm Term -> m
    f (a
    x, b
    y) = (Term -> m) -> a -> m
    forall m. Monoid m => (Term -> m) -> a -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f a
    x m -> m -> m
    forall a. Monoid a => a -> a -> a
    `mappend` (Term -> m) -> b -> m
    forall m. Monoid m => (Term -> m) -> b -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f b
    y

    instance (TermLike a, TermLike b, TermLike c) => TermLike (a, b, c) where
      traverseTermM :: forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> (a, b, c) -> m (a, b, c)
    traverseTermM Term -> m Term
    f (a
    x, b
    y, c
    z) = (,,) (a -> b -> c -> (a, b, c)) -> m a -> m (b -> c -> (a, b, c))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> a -> m a
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> a -> m a
    traverseTermM Term -> m Term
    f a
    x m (b -> c -> (a, b, c)) -> m b -> m (c -> (a, b, c))
    forall a b. m (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Term -> m Term) -> b -> m b
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> b -> m b
    traverseTermM Term -> m Term
    f b
    y m (c -> (a, b, c)) -> m c -> m (a, b, c)
    forall a b. m (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Term -> m Term) -> c -> m c
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> c -> m c
    traverseTermM Term -> m Term
    f c
    z
      foldTerm :: forall m. Monoid m => (Term -> m) -> (a, b, c) -> m
    foldTerm Term -> m
    f (a
    x, b
    y, c
    z) = [m] -> m
    forall a. Monoid a => [a] -> a
    mconcat [(Term -> m) -> a -> m
    forall m. Monoid m => (Term -> m) -> a -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f a
    x, (Term -> m) -> b -> m
    forall m. Monoid m => (Term -> m) -> b -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f b
    y, (Term -> m) -> c -> m
    forall m. Monoid m => (Term -> m) -> c -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f c
    z]

    instance (TermLike a, TermLike b, TermLike c, TermLike d) => TermLike (a, b, c, d) where
      traverseTermM :: forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> (a, b, c, d) -> m (a, b, c, d)
    traverseTermM Term -> m Term
    f (a
    x, b
    y, c
    z, d
    u) = (,,,) (a -> b -> c -> d -> (a, b, c, d))
    -> m a -> m (b -> c -> d -> (a, b, c, d))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> a -> m a
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> a -> m a
    traverseTermM Term -> m Term
    f a
    x m (b -> c -> d -> (a, b, c, d))
    -> m b -> m (c -> d -> (a, b, c, d))
    forall a b. m (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Term -> m Term) -> b -> m b
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> b -> m b
    traverseTermM Term -> m Term
    f b
    y m (c -> d -> (a, b, c, d)) -> m c -> m (d -> (a, b, c, d))
    forall a b. m (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Term -> m Term) -> c -> m c
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> c -> m c
    traverseTermM Term -> m Term
    f c
    z m (d -> (a, b, c, d)) -> m d -> m (a, b, c, d)
    forall a b. m (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Term -> m Term) -> d -> m d
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> d -> m d
    traverseTermM Term -> m Term
    f d
    u
      foldTerm :: forall m. Monoid m => (Term -> m) -> (a, b, c, d) -> m
    foldTerm Term -> m
    f (a
    x, b
    y, c
    z, d
    u) = [m] -> m
    forall a. Monoid a => [a] -> a
    mconcat [(Term -> m) -> a -> m
    forall m. Monoid m => (Term -> m) -> a -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f a
    x, (Term -> m) -> b -> m
    forall m. Monoid m => (Term -> m) -> b -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f b
    y, (Term -> m) -> c -> m
    forall m. Monoid m => (Term -> m) -> c -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f c
    z, (Term -> m) -> d -> m
    forall m. Monoid m => (Term -> m) -> d -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f d
    u]

    -- Real terms

    instance TermLike Term where

      traverseTermM :: forall (m :: * -> *). Monad m => (Term -> m Term) -> Term -> m Term
    traverseTermM Term -> m Term
    f = \case
        Var Int
    i Elims
    xs    -> Term -> m Term
    f (Term -> m Term) -> m Term -> m Term
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< Int -> Elims -> Term
    Var Int
    i (Elims -> Term) -> m Elims -> m Term
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Elims -> m Elims
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Elims -> m Elims
    traverseTermM Term -> m Term
    f Elims
    xs
        Def QName
    c Elims
    xs    -> Term -> m Term
    f (Term -> m Term) -> m Term -> m Term
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< QName -> Elims -> Term
    Def QName
    c (Elims -> Term) -> m Elims -> m Term
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Elims -> m Elims
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Elims -> m Elims
    traverseTermM Term -> m Term
    f Elims
    xs
        Con ConHead
    c ConInfo
    ci Elims
    xs -> Term -> m Term
    f (Term -> m Term) -> m Term -> m Term
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< ConHead -> ConInfo -> Elims -> Term
    Con ConHead
    c ConInfo
    ci (Elims -> Term) -> m Elims -> m Term
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Elims -> m Elims
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Elims -> m Elims
    traverseTermM Term -> m Term
    f Elims
    xs
        Lam ArgInfo
    h Abs Term
    b     -> Term -> m Term
    f (Term -> m Term) -> m Term -> m Term
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< ArgInfo -> Abs Term -> Term
    Lam ArgInfo
    h (Abs Term -> Term) -> m (Abs Term) -> m Term
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Abs Term -> m (Abs Term)
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Abs Term -> m (Abs Term)
    traverseTermM Term -> m Term
    f Abs Term
    b
        Pi Dom Type
    a Abs Type
    b      -> Term -> m Term
    f (Term -> m Term) -> m Term -> m Term
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< (Dom Type -> Abs Type -> Term) -> (Dom Type, Abs Type) -> Term
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry Dom Type -> Abs Type -> Term
    Pi ((Dom Type, Abs Type) -> Term) -> m (Dom Type, Abs Type) -> m Term
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> (Dom Type, Abs Type) -> m (Dom Type, Abs Type)
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> (Dom Type, Abs Type) -> m (Dom Type, Abs Type)
    traverseTermM Term -> m Term
    f (Dom Type
    a, Abs Type
    b)
        MetaV MetaId
    m Elims
    xs  -> Term -> m Term
    f (Term -> m Term) -> m Term -> m Term
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< MetaId -> Elims -> Term
    MetaV MetaId
    m (Elims -> Term) -> m Elims -> m Term
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Elims -> m Elims
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Elims -> m Elims
    traverseTermM Term -> m Term
    f Elims
    xs
        Level Level
    l     -> Term -> m Term
    f (Term -> m Term) -> m Term -> m Term
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< Level -> Term
    Level (Level -> Term) -> m Level -> m Term
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Level -> m Level
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Level -> m Level
    traverseTermM Term -> m Term
    f Level
    l
        t :: Term
    t@Lit{}     -> Term -> m Term
    f Term
    t
        Sort Sort
    s      -> Term -> m Term
    f (Term -> m Term) -> m Term -> m Term
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< Sort -> Term
    Sort (Sort -> Term) -> m Sort -> m Term
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Sort -> m Sort
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> Sort -> m Sort
    traverseTermM Term -> m Term
    f Sort
    s
        DontCare Term
    mv -> Term -> m Term
    f (Term -> m Term) -> m Term -> m Term
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< Term -> Term
    DontCare (Term -> Term) -> m Term -> m Term
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Term -> m Term
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> Term -> m Term
    traverseTermM Term -> m Term
    f Term
    mv
        Dummy String
    s Elims
    xs  -> Term -> m Term
    f (Term -> m Term) -> m Term -> m Term
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< String -> Elims -> Term
    Dummy String
    s (Elims -> Term) -> m Elims -> m Term
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Elims -> m Elims
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Elims -> m Elims
    traverseTermM Term -> m Term
    f Elims
    xs

      foldTerm :: forall m. Monoid m => (Term -> m) -> Term -> m
    foldTerm Term -> m
    f Term
    t = Term -> m
    f Term
    t m -> m -> m
    forall a. Monoid a => a -> a -> a
    `mappend` case Term
    t of
        Var Int
    i Elims
    xs    -> (Term -> m) -> Elims -> m
    forall m. Monoid m => (Term -> m) -> Elims -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Elims
    xs
        Def QName
    c Elims
    xs    -> (Term -> m) -> Elims -> m
    forall m. Monoid m => (Term -> m) -> Elims -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Elims
    xs
        Con ConHead
    c ConInfo
    ci Elims
    xs -> (Term -> m) -> Elims -> m
    forall m. Monoid m => (Term -> m) -> Elims -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Elims
    xs
        Lam ArgInfo
    h Abs Term
    b     -> (Term -> m) -> Abs Term -> m
    forall m. Monoid m => (Term -> m) -> Abs Term -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Abs Term
    b
        Pi Dom Type
    a Abs Type
    b      -> (Term -> m) -> (Dom Type, Abs Type) -> m
    forall m. Monoid m => (Term -> m) -> (Dom Type, Abs Type) -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f (Dom Type
    a, Abs Type
    b)
        MetaV MetaId
    m Elims
    xs  -> (Term -> m) -> Elims -> m
    forall m. Monoid m => (Term -> m) -> Elims -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Elims
    xs
        Level Level
    l     -> (Term -> m) -> Level -> m
    forall m. Monoid m => (Term -> m) -> Level -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Level
    l
        Lit Literal
    _       -> m
    forall a. Monoid a => a
    mempty
        Sort Sort
    s      -> (Term -> m) -> Sort -> m
    forall m. Monoid m => (Term -> m) -> Sort -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Sort
    s
        DontCare Term
    mv -> (Term -> m) -> Term -> m
    forall m. Monoid m => (Term -> m) -> Term -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Term
    mv
        Dummy String
    _ Elims
    xs  -> (Term -> m) -> Elims -> m
    forall m. Monoid m => (Term -> m) -> Elims -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Elims
    xs

    instance TermLike Level where
      traverseTermM :: forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Level -> m Level
    traverseTermM Term -> m Term
    f (Max Integer
    n [PlusLevel' Term]
    as) = Integer -> [PlusLevel' Term] -> Level
    forall t. Integer -> [PlusLevel' t] -> Level' t
    Max Integer
    n ([PlusLevel' Term] -> Level) -> m [PlusLevel' Term] -> m Level
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> [PlusLevel' Term] -> m [PlusLevel' Term]
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> [PlusLevel' Term] -> m [PlusLevel' Term]
    traverseTermM Term -> m Term
    f [PlusLevel' Term]
    as
      foldTerm :: forall m. Monoid m => (Term -> m) -> Level -> m
    foldTerm Term -> m
    f      (Max Integer
    n [PlusLevel' Term]
    as) = (Term -> m) -> [PlusLevel' Term] -> m
    forall m. Monoid m => (Term -> m) -> [PlusLevel' Term] -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f [PlusLevel' Term]
    as

    instance TermLike PlusLevel where
      traverseTermM :: forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> PlusLevel' Term -> m (PlusLevel' Term)
    traverseTermM Term -> m Term
    f (Plus Integer
    n Term
    l) = Integer -> Term -> PlusLevel' Term
    forall t. Integer -> t -> PlusLevel' t
    Plus Integer
    n (Term -> PlusLevel' Term) -> m Term -> m (PlusLevel' Term)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Term -> m Term
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> Term -> m Term
    traverseTermM Term -> m Term
    f Term
    l
      foldTerm :: forall m. Monoid m => (Term -> m) -> PlusLevel' Term -> m
    foldTerm Term -> m
    f (Plus Integer
    _ Term
    l)      = (Term -> m) -> Term -> m
    forall m. Monoid m => (Term -> m) -> Term -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Term
    l

    instance TermLike Type where
      traverseTermM :: forall (m :: * -> *). Monad m => (Term -> m Term) -> Type -> m Type
    traverseTermM Term -> m Term
    f (El Sort
    s Term
    t) = Sort -> Term -> Type
    forall t a. Sort' t -> a -> Type'' t a
    El Sort
    s (Term -> Type) -> m Term -> m Type
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Term -> m Term
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> Term -> m Term
    traverseTermM Term -> m Term
    f Term
    t
      foldTerm :: forall m. Monoid m => (Term -> m) -> Type -> m
    foldTerm Term -> m
    f (El Sort
    s Term
    t) = (Term -> m) -> Term -> m
    forall m. Monoid m => (Term -> m) -> Term -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Term
    t

    instance TermLike Sort where
      traverseTermM :: forall (m :: * -> *). Monad m => (Term -> m Term) -> Sort -> m Sort
    traverseTermM Term -> m Term
    f = \case
        Univ Univ
    u Level
    l   -> Univ -> Level -> Sort
    forall t. Univ -> Level' t -> Sort' t
    Univ Univ
    u (Level -> Sort) -> m Level -> m Sort
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Level -> m Level
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Level -> m Level
    traverseTermM Term -> m Term
    f Level
    l
        s :: Sort
    s@(Inf Univ
    _ Integer
    _)-> Sort -> m Sort
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Sort
    s
        s :: Sort
    s@Sort
    SizeUniv -> Sort -> m Sort
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Sort
    s
        s :: Sort
    s@Sort
    LockUniv -> Sort -> m Sort
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Sort
    s
        s :: Sort
    s@Sort
    LevelUniv -> Sort -> m Sort
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Sort
    s
        s :: Sort
    s@Sort
    IntervalUniv -> Sort -> m Sort
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Sort
    s
        PiSort Dom' Term Term
    a Sort
    b Abs Sort
    c -> Dom' Term Term -> Sort -> Abs Sort -> Sort
    forall t. Dom' t t -> Sort' t -> Abs (Sort' t) -> Sort' t
    PiSort   (Dom' Term Term -> Sort -> Abs Sort -> Sort)
    -> m (Dom' Term Term) -> m (Sort -> Abs Sort -> Sort)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Dom' Term Term -> m (Dom' Term Term)
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Dom' Term Term -> m (Dom' Term Term)
    traverseTermM Term -> m Term
    f Dom' Term Term
    a m (Sort -> Abs Sort -> Sort) -> m Sort -> m (Abs Sort -> Sort)
    forall a b. m (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Term -> m Term) -> Sort -> m Sort
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> Sort -> m Sort
    traverseTermM Term -> m Term
    f Sort
    b m (Abs Sort -> Sort) -> m (Abs Sort) -> m Sort
    forall a b. m (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Term -> m Term) -> Abs Sort -> m (Abs Sort)
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Abs Sort -> m (Abs Sort)
    traverseTermM Term -> m Term
    f Abs Sort
    c
        FunSort Sort
    a Sort
    b -> Sort -> Sort -> Sort
    forall t. Sort' t -> Sort' t -> Sort' t
    FunSort   (Sort -> Sort -> Sort) -> m Sort -> m (Sort -> Sort)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Sort -> m Sort
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> Sort -> m Sort
    traverseTermM Term -> m Term
    f Sort
    a m (Sort -> Sort) -> m Sort -> m Sort
    forall a b. m (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Term -> m Term) -> Sort -> m Sort
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> Sort -> m Sort
    traverseTermM Term -> m Term
    f Sort
    b
        UnivSort Sort
    a -> Sort -> Sort
    forall t. Sort' t -> Sort' t
    UnivSort (Sort -> Sort) -> m Sort -> m Sort
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Sort -> m Sort
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> Sort -> m Sort
    traverseTermM Term -> m Term
    f Sort
    a
        MetaS MetaId
    x Elims
    es -> MetaId -> Elims -> Sort
    forall t. MetaId -> [Elim' t] -> Sort' t
    MetaS MetaId
    x  (Elims -> Sort) -> m Elims -> m Sort
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Elims -> m Elims
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Elims -> m Elims
    traverseTermM Term -> m Term
    f Elims
    es
        DefS QName
    q Elims
    es  -> QName -> Elims -> Sort
    forall t. QName -> [Elim' t] -> Sort' t
    DefS QName
    q   (Elims -> Sort) -> m Elims -> m Sort
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Elims -> m Elims
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Elims -> m Elims
    traverseTermM Term -> m Term
    f Elims
    es
        s :: Sort
    s@(DummyS String
    _) -> Sort -> m Sort
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Sort
    s

      foldTerm :: forall m. Monoid m => (Term -> m) -> Sort -> m
    foldTerm Term -> m
    f = \case
        Univ Univ
    _ Level
    l   -> (Term -> m) -> Level -> m
    forall m. Monoid m => (Term -> m) -> Level -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Level
    l
        Inf Univ
    _ Integer
    _    -> m
    forall a. Monoid a => a
    mempty
        Sort
    SizeUniv   -> m
    forall a. Monoid a => a
    mempty
        Sort
    LockUniv   -> m
    forall a. Monoid a => a
    mempty
        Sort
    LevelUniv  -> m
    forall a. Monoid a => a
    mempty
        Sort
    IntervalUniv -> m
    forall a. Monoid a => a
    mempty
        PiSort Dom' Term Term
    a Sort
    b Abs Sort
    c -> (Term -> m) -> Dom' Term Term -> m
    forall m. Monoid m => (Term -> m) -> Dom' Term Term -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Dom' Term Term
    a m -> m -> m
    forall a. Semigroup a => a -> a -> a
    <> (Term -> m) -> Sort -> m
    forall m. Monoid m => (Term -> m) -> Sort -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Sort
    b m -> m -> m
    forall a. Semigroup a => a -> a -> a
    <> (Term -> m) -> Abs Sort -> m
    forall m. Monoid m => (Term -> m) -> Abs Sort -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Abs Sort
    c
        FunSort Sort
    a Sort
    b -> (Term -> m) -> Sort -> m
    forall m. Monoid m => (Term -> m) -> Sort -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Sort
    a m -> m -> m
    forall a. Semigroup a => a -> a -> a
    <> (Term -> m) -> Sort -> m
    forall m. Monoid m => (Term -> m) -> Sort -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Sort
    b
        UnivSort Sort
    a -> (Term -> m) -> Sort -> m
    forall m. Monoid m => (Term -> m) -> Sort -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Sort
    a
        MetaS MetaId
    _ Elims
    es -> (Term -> m) -> Elims -> m
    forall m. Monoid m => (Term -> m) -> Elims -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Elims
    es
        DefS QName
    _ Elims
    es  -> (Term -> m) -> Elims -> m
    forall m. Monoid m => (Term -> m) -> Elims -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Elims
    es
        DummyS String
    _   -> m
    forall a. Monoid a => a
    mempty

    instance TermLike EqualityView where

      traverseTermM :: forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> EqualityView -> m EqualityView
    traverseTermM Term -> m Term
    f = \case
        OtherType Type
    t -> Type -> EqualityView
    OtherType
          (Type -> EqualityView) -> m Type -> m EqualityView
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Type -> m Type
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> Type -> m Type
    traverseTermM Term -> m Term
    f Type
    t
        IdiomType Type
    t -> Type -> EqualityView
    IdiomType
          (Type -> EqualityView) -> m Type -> m EqualityView
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Term -> m Term) -> Type -> m Type
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> Type -> m Type
    traverseTermM Term -> m Term
    f Type
    t
        EqualityType Range
    r Sort
    s QName
    eq Args
    l Arg Term
    t Arg Term
    a Arg Term
    b -> Range
    -> Sort
    -> QName
    -> Args
    -> Arg Term
    -> Arg Term
    -> Arg Term
    -> EqualityView
    EqualityType Range
    r Sort
    s QName
    eq
          (Args -> Arg Term -> Arg Term -> Arg Term -> EqualityView)
    -> m Args -> m (Arg Term -> Arg Term -> Arg Term -> EqualityView)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Arg Term -> m (Arg Term)) -> Args -> m Args
    forall (t :: * -> *) (f :: * -> *) a b.
    (Traversable t, Applicative f) =>
    (a -> f b) -> t a -> f (t b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> [a] -> f [b]
    traverse ((Term -> m Term) -> Arg Term -> m (Arg Term)
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Arg Term -> m (Arg Term)
    traverseTermM Term -> m Term
    f) Args
    l
          m (Arg Term -> Arg Term -> Arg Term -> EqualityView)
    -> m (Arg Term) -> m (Arg Term -> Arg Term -> EqualityView)
    forall a b. m (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Term -> m Term) -> Arg Term -> m (Arg Term)
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Arg Term -> m (Arg Term)
    traverseTermM Term -> m Term
    f Arg Term
    t
          m (Arg Term -> Arg Term -> EqualityView)
    -> m (Arg Term) -> m (Arg Term -> EqualityView)
    forall a b. m (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Term -> m Term) -> Arg Term -> m (Arg Term)
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Arg Term -> m (Arg Term)
    traverseTermM Term -> m Term
    f Arg Term
    a
          m (Arg Term -> EqualityView) -> m (Arg Term) -> m EqualityView
    forall a b. m (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Term -> m Term) -> Arg Term -> m (Arg Term)
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *).
    Monad m =>
    (Term -> m Term) -> Arg Term -> m (Arg Term)
    traverseTermM Term -> m Term
    f Arg Term
    b

      foldTerm :: forall m. Monoid m => (Term -> m) -> EqualityView -> m
    foldTerm Term -> m
    f = \case
        OtherType Type
    t -> (Term -> m) -> Type -> m
    forall m. Monoid m => (Term -> m) -> Type -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Type
    t
        IdiomType Type
    t -> (Term -> m) -> Type -> m
    forall m. Monoid m => (Term -> m) -> Type -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f Type
    t
        EqualityType Range
    _r Sort
    _s QName
    _eq Args
    l Arg Term
    t Arg Term
    a Arg Term
    b -> (Term -> m) -> Args -> m
    forall m. Monoid m => (Term -> m) -> Args -> m
    forall a m. (TermLike a, Monoid m) => (Term -> m) -> a -> m
    foldTerm Term -> m
    f (Args
    l Args -> Args -> Args
    forall a. [a] -> [a] -> [a]
    ++ [Arg Term
    t, Arg Term
    a, Arg Term
    b])

    -- | Put it in a monad to make it possible to do strictly.
    copyTerm :: (TermLike a, Monad m) => a -> m a
    copyTerm :: forall a (m :: * -> *). (TermLike a, Monad m) => a -> m a
    copyTerm = (Term -> m Term) -> a -> m a
    forall a (m :: * -> *).
    (TermLike a, Monad m) =>
    (Term -> m Term) -> a -> m a
    forall (m :: * -> *). Monad m => (Term -> m Term) -> a -> m a
    traverseTermM Term -> m Term
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return