    {- |
    /DEPRECATED/ Use "Data.Generics.Uniplate.Operations" instead.

    This is the main Uniplate module, which defines all the essential operations
    in a Haskell 98 compatible manner.

    Most functions have an example of a possible use for the function.
    To illustate, I have used the @Expr@ type as below:

    > data Expr = Val Int
    >           | Neg Expr
    >           | Add Expr Expr
    -}

    module Data.Generics.Uniplate
        {- DEPRECATED "Use Data.Generics.Uniplate.Operations instead" -}
        where

    import Control.Monad
    import Data.Generics.Uniplate.Internal.Utils

    -- * The Class

    -- | The type of replacing all the children of a node
    --
    --   Taking a value, the function should return all the immediate children
    --   of the same type, and a function to replace them.
    type UniplateType on = on -> ([on], [on] -> on)

    -- | The standard Uniplate class, all operations require this
    class Uniplate on where
        -- | The underlying method in the class
        --
        -- > uniplate (Add (Val 1) (Neg (Val 2))) = ([Val 1, Neg (Val 2)], \[a,b] -> Add a b)
        -- > uniplate (Val 1)                     = ([]                  , \[]    -> Val 1  )
        uniplate :: UniplateType on

    -- * The Operations

    -- ** Queries

    -- | Get all the children of a node, including itself and all children.
    --
    -- > universe (Add (Val 1) (Neg (Val 2))) =
    -- >     [Add (Val 1) (Neg (Val 2)), Val 1, Neg (Val 2), Val 2]
    --
    -- This method is often combined with a list comprehension, for example:
    --
    -- > vals x = [i | Val i <- universe x]
    universe :: Uniplate on => on -> [on]
    universe :: on -> [on]
    universe x :: on
    x = (forall b. (on -> b -> b) -> b -> b) -> [on]
    forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
    builder (on -> (on -> b -> b) -> b -> b
    forall on res.
    Uniplate on =>
    on -> (on -> res -> res) -> res -> res
    f on
    x)
        where
            f :: Uniplate on => on -> (on -> res -> res) -> res -> res
            f :: on -> (on -> res -> res) -> res -> res
    f x :: on
    x cons :: on -> res -> res
    cons nil :: res
    nil = on
    x on -> res -> res
    `cons` [res -> res] -> res -> res
    forall a. [a -> a] -> a -> a
    concatCont ((on -> res -> res) -> [on] -> [res -> res]
    forall a b. (a -> b) -> [a] -> [b]
    map (\x :: on
    x -> on -> (on -> res -> res) -> res -> res
    forall on res.
    Uniplate on =>
    on -> (on -> res -> res) -> res -> res
    f on
    x on -> res -> res
    cons) ([on] -> [res -> res]) -> [on] -> [res -> res]
    forall a b. (a -> b) -> a -> b
    $ on -> [on]
    forall on. Uniplate on => on -> [on]
    children on
    x) res
    nil

    -- | Get the direct children of a node. Usually using 'universe' is more appropriate.
    --
    -- @children = fst . 'uniplate'@
    children :: Uniplate on => on -> [on]
    children :: on -> [on]
    children = ([on], [on] -> on) -> [on]
    forall a b. (a, b) -> a
    fst (([on], [on] -> on) -> [on])
    -> (on -> ([on], [on] -> on)) -> on -> [on]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . on -> ([on], [on] -> on)
    forall on. Uniplate on => UniplateType on
    uniplate

    -- ** Transformations

    -- | Transform every element in the tree, in a bottom-up manner.
    --
    -- For example, replacing negative literals with literals:
    --
    -- > negLits = transform f
    -- >    where f (Neg (Lit i)) = Lit (negate i)
    -- >          f x = x
    transform :: Uniplate on => (on -> on) -> on -> on
    transform :: (on -> on) -> on -> on
    transform f :: on -> on
    f x :: on
    x = on -> on
    f (on -> on) -> on -> on
    forall a b. (a -> b) -> a -> b
    $ [on] -> on
    generate ([on] -> on) -> [on] -> on
    forall a b. (a -> b) -> a -> b
    $ (on -> on) -> [on] -> [on]
    forall a b. (a -> b) -> [a] -> [b]
    map ((on -> on) -> on -> on
    forall on. Uniplate on => (on -> on) -> on -> on
    transform on -> on
    f) [on]
    current
        where (current :: [on]
    current, generate :: [on] -> on
    generate) = UniplateType on
    forall on. Uniplate on => UniplateType on
    uniplate on
    x

    -- | Monadic variant of 'transform'
    transformM :: (Monad m, Uniplate on) => (on -> m on) -> on -> m on
    transformM :: (on -> m on) -> on -> m on
    transformM f :: on -> m on
    f x :: on
    x = (on -> m on) -> [on] -> m [on]
    forall (t :: * -> *) (m :: * -> *) a b.
    (Traversable t, Monad m) =>
    (a -> m b) -> t a -> m (t b)
    mapM ((on -> m on) -> on -> m on
    forall (m :: * -> *) on.
    (Monad m, Uniplate on) =>
    (on -> m on) -> on -> m on
    transformM on -> m on
    f) [on]
    current m [on] -> ([on] -> m on) -> m on
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= on -> m on
    f (on -> m on) -> ([on] -> on) -> [on] -> m on
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [on] -> on
    generate
        where (current :: [on]
    current, generate :: [on] -> on
    generate) = UniplateType on
    forall on. Uniplate on => UniplateType on
    uniplate on
    x

    -- | Rewrite by applying a rule everywhere you can. Ensures that the rule cannot
    -- be applied anywhere in the result:
    --
    -- > propRewrite r x = all (isNothing . r) (universe (rewrite r x))
    --
    -- Usually 'transform' is more appropriate, but 'rewrite' can give better
    -- compositionality. Given two single transformations @f@ and @g@, you can
    -- construct @f `mplus` g@ which performs both rewrites until a fixed point.
    rewrite :: Uniplate on => (on -> Maybe on) -> on -> on
    rewrite :: (on -> Maybe on) -> on -> on
    rewrite f :: on -> Maybe on
    f = (on -> on) -> on -> on
    forall on. Uniplate on => (on -> on) -> on -> on
    transform on -> on
    g
        where g :: on -> on
    g x :: on
    x = on -> (on -> on) -> Maybe on -> on
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe on
    x ((on -> Maybe on) -> on -> on
    forall on. Uniplate on => (on -> Maybe on) -> on -> on
    rewrite on -> Maybe on
    f) (on -> Maybe on
    f on
    x)

    -- | Monadic variant of 'rewrite'
    rewriteM :: (Monad m, Uniplate on) => (on -> m (Maybe on)) -> on -> m on
    rewriteM :: (on -> m (Maybe on)) -> on -> m on
    rewriteM f :: on -> m (Maybe on)
    f = (on -> m on) -> on -> m on
    forall (m :: * -> *) on.
    (Monad m, Uniplate on) =>
    (on -> m on) -> on -> m on
    transformM on -> m on
    g
        where g :: on -> m on
    g x :: on
    x = on -> m (Maybe on)
    f on
    x m (Maybe on) -> (Maybe on -> m on) -> m on
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= m on -> (on -> m on) -> Maybe on -> m on
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe (on -> m on
    forall (m :: * -> *) a. Monad m => a -> m a
    return on
    x) ((on -> m (Maybe on)) -> on -> m on
    forall (m :: * -> *) on.
    (Monad m, Uniplate on) =>
    (on -> m (Maybe on)) -> on -> m on
    rewriteM on -> m (Maybe on)
    f)

    -- | Perform a transformation on all the immediate children, then combine them back.
    -- This operation allows additional information to be passed downwards, and can be
    -- used to provide a top-down transformation.
    descend :: Uniplate on => (on -> on) -> on -> on
    descend :: (on -> on) -> on -> on
    descend f :: on -> on
    f x :: on
    x = [on] -> on
    generate ([on] -> on) -> [on] -> on
    forall a b. (a -> b) -> a -> b
    $ (on -> on) -> [on] -> [on]
    forall a b. (a -> b) -> [a] -> [b]
    map on -> on
    f [on]
    current
        where (current :: [on]
    current, generate :: [on] -> on
    generate) = UniplateType on
    forall on. Uniplate on => UniplateType on
    uniplate on
    x

    -- | Monadic variant of 'descend'
    descendM :: (Monad m, Uniplate on) => (on -> m on) -> on -> m on
    descendM :: (on -> m on) -> on -> m on
    descendM f :: on -> m on
    f x :: on
    x = ([on] -> on) -> m [on] -> m on
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM [on] -> on
    generate (m [on] -> m on) -> m [on] -> m on
    forall a b. (a -> b) -> a -> b
    $ (on -> m on) -> [on] -> m [on]
    forall (t :: * -> *) (m :: * -> *) a b.
    (Traversable t, Monad m) =>
    (a -> m b) -> t a -> m (t b)
    mapM on -> m on
    f [on]
    current
        where (current :: [on]
    current, generate :: [on] -> on
    generate) = UniplateType on
    forall on. Uniplate on => UniplateType on
    uniplate on
    x

    -- ** Others

    -- | Return all the contexts and holes.
    --
    -- > propUniverse x = universe x == map fst (contexts x)
    -- > propId x = all (== x) [b a | (a,b) <- contexts x]
    contexts :: Uniplate on => on -> [(on, on -> on)]
    contexts :: on -> [(on, on -> on)]
    contexts x :: on
    x = (on
    x,on -> on
    forall a. a -> a
    id) (on, on -> on) -> [(on, on -> on)] -> [(on, on -> on)]
    forall a. a -> [a] -> [a]
    : [(on, on -> on)] -> [(on, on -> on)]
    forall b c. Uniplate b => [(b, b -> c)] -> [(b, b -> c)]
    f (on -> [(on, on -> on)]
    forall on. Uniplate on => on -> [(on, on -> on)]
    holes on
    x)
      where
        f :: [(b, b -> c)] -> [(b, b -> c)]
    f xs :: [(b, b -> c)]
    xs = [ (b
    y, b -> c
    ctx (b -> c) -> (b -> b) -> b -> c
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . b -> b
    context)
               | (child :: b
    child, ctx :: b -> c
    ctx) <- [(b, b -> c)]
    xs
               , (y :: b
    y, context :: b -> b
    context) <- b -> [(b, b -> b)]
    forall on. Uniplate on => on -> [(on, on -> on)]
    contexts b
    child]

    -- | The one depth version of 'contexts'
    --
    -- > propChildren x = children x == map fst (holes x)
    -- > propId x = all (== x) [b a | (a,b) <- holes x]
    holes :: Uniplate on => on -> [(on, on -> on)]
    holes :: on -> [(on, on -> on)]
    holes x :: on
    x = ([on] -> ([on] -> on) -> [(on, on -> on)])
    -> ([on], [on] -> on) -> [(on, on -> on)]
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry [on] -> ([on] -> on) -> [(on, on -> on)]
    forall a c. [a] -> ([a] -> c) -> [(a, a -> c)]
    f (UniplateType on
    forall on. Uniplate on => UniplateType on
    uniplate on
    x)
      where f :: [a] -> ([a] -> c) -> [(a, a -> c)]
    f [] _ = []
            f (x :: a
    x:xs :: [a]
    xs) gen :: [a] -> c
    gen = (a
    x, [a] -> c
    gen ([a] -> c) -> (a -> [a]) -> a -> c
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    xs)) (a, a -> c) -> [(a, a -> c)] -> [(a, a -> c)]
    forall a. a -> [a] -> [a]
    :
                           [a] -> ([a] -> c) -> [(a, a -> c)]
    f [a]
    xs ([a] -> c
    gen ([a] -> c) -> ([a] -> [a]) -> [a] -> c
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :))

    -- | Perform a fold-like computation on each value,
    --   technically a paramorphism
    para :: Uniplate on => (on -> [r] -> r) -> on -> r
    para :: (on -> [r] -> r) -> on -> r
    para op :: on -> [r] -> r
    op x :: on
    x = on -> [r] -> r
    op on
    x ([r] -> r) -> [r] -> r
    forall a b. (a -> b) -> a -> b
    $ (on -> r) -> [on] -> [r]
    forall a b. (a -> b) -> [a] -> [b]
    map ((on -> [r] -> r) -> on -> r
    forall on r. Uniplate on => (on -> [r] -> r) -> on -> r
    para on -> [r] -> r
    op) ([on] -> [r]) -> [on] -> [r]
    forall a b. (a -> b) -> a -> b
    $ on -> [on]
    forall on. Uniplate on => on -> [on]
    children on
    x