-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Library for strategic programming
--   
--   This is a version of the StrategyLib library originally shipped with
--   Strafunski, Cabalized and updated to newer versions of GHC. A
--   description of much of StrategyLib can be found in the paper "Design
--   Patterns for Functional Strategic Programming."
@package Strafunski-StrategyLib
@version 5.0.0.10


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module defines additional instances of the Monoid class.
module Data.Generics.Strafunski.StrategyLib.MoreMonoids

-- | Any <a>Num</a> is a <a>Monoid</a>.
instance GHC.Num.Num a => GHC.Base.Monoid a


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module defines auxilliary monadic functions, some of which serve
--   as parametric polymorphic prototypes for actual strategy combinators.
module Data.Generics.Strafunski.StrategyLib.MonadicFunctions

-- | Force success. If the argument value corresponds to failure, a
--   run-time error will occur.
succeed :: Maybe x -> x

-- | Sequential composition of monadic functions
mseq :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c

-- | Sequential composition with value passing; a kind of monadic let.
mlet :: Monad m => (a -> m b) -> (b -> a -> m c) -> a -> m c

-- | Choice combinator for monadic functions
mchoice :: MonadPlus m => (a -> m b) -> (a -> m b) -> a -> m b

-- | Type guard described by the argument type of a function.
argtype :: MonadPlus m => (x -> y) -> x -> m ()

-- | Type guard described by a type of a value.
valtype :: MonadPlus m => x -> x -> m ()

-- | A kind of monadic conditional.
ifM :: MonadPlus m => m a -> (a -> m c) -> (m c) -> (m c)

module Data.Generics.Strafunski.StrategyLib.Models.Deriving.TermRep
class Data x => Term x
instance (Data.Typeable.Internal.Typeable x, Data.Data.Data x) => Data.Generics.Strafunski.StrategyLib.Models.Deriving.TermRep.Term x


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module defines a generic algorithm for import chasing. This
--   algorithm is not strategic in nature itself, but usually it will be
--   instantiated with strategic functions for a particular object
--   language.
module Data.Generics.Strafunski.StrategyLib.ChaseImports

-- | The type of names of chaseable things. Synonym of <a>String</a>.
type ChaseName = String

-- | A generic import chasing function. The type of the final result is a
--   parameter, which will usually be instantiated to a list of parsed
--   modules.
chaseWith :: [FilePath] -> [ChaseName] -> [ChaseName] -> accu -> ([FilePath] -> ChaseName -> IO (Either cu String)) -> (cu -> [ChaseName]) -> (ChaseName -> [ChaseName] -> cu -> accu -> IO accu) -> (ChaseName -> accu -> IO accu) -> IO accu

-- | Read a file from a number of possible directories, given a base name
--   and a list of possible extensions. Returns the content of the file it
--   found.
chaseFile :: [FilePath] -> String -> [String] -> IO String

-- | Find a file in a number of possible directories, given a base name and
--   a list of possible extensions. Returns the full name of the file it
--   found.
findFile :: [FilePath] -> String -> [String] -> IO FilePath


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module provides non-strategic functionality for running monads
--   and unlifting monad transformers. In a sense, this is dual to the
--   <a>return</a> and <a>lift</a> functionality of the <a>Monad</a> and
--   <a>MonadTrans</a> classes.
module Control.Monad.Run

-- | The algebra for the partiality effect of <a>Maybe</a> and
--   <a>MaybeT</a>.
data MaybeAlg a b
MaybeAlg :: b -> (a -> b) -> MaybeAlg a b
[nothing] :: MaybeAlg a b -> b
[just] :: MaybeAlg a b -> a -> b

-- | The algebra for the error effect of <a>Either</a> and <a>ErrorT</a>.
data ErrorAlg e a b
ErrorAlg :: (e -> b) -> (a -> b) -> ErrorAlg e a b
[left] :: ErrorAlg e a b -> e -> b
[right] :: ErrorAlg e a b -> a -> b

-- | The algebra for the non-determinacy effect of '[]' and <a>ListT</a>.
data ListAlg a b
ListAlg :: b -> (a -> b -> b) -> ListAlg a b
[nil] :: ListAlg a b -> b
[cons] :: ListAlg a b -> a -> b -> b

-- | The algebra for the state effect of <a>State</a> and <a>StateT</a>.
data StateAlg s a b
StateAlg :: s -> ((a, s) -> b) -> StateAlg s a b

-- | initial state
[first] :: StateAlg s a b -> s

-- | state transformer
[next] :: StateAlg s a b -> (a, s) -> b

-- | The class of monads for which a <a>run</a> function is defined that
--   executes the computation of the monad.
class MonadRun s m | m -> s

-- | The overloaded function run takes as first argument an "algebra" which
--   captures the ingredients necessary to run the particular monad at
--   hand. This algebra is parameterized with the domain and co-domain of
--   run.
run :: MonadRun s m => s a b -> m a -> b

-- | Running the <a>Identity</a> monad. The algebra for the <a>Identity</a>
--   monad is a unary function.

-- | Running the <a>Maybe</a> monad.

-- | Running the error monad.

-- | Running the list monad.

-- | Running the <a>State</a> monad.

-- | Running the <a>IO</a> monad. Note: uses <a>unsafePerformIO</a>!

-- | Exchange one monad by another. This function runs one monad, and puts
--   its value in another. This is basically a monadic version of the
--   <a>run</a> function itself. Note that the two monads are unrelated, so
--   none of the effects of the incoming monad are transferred to the
--   result monad.
mrun :: (MonadRun s m, Monad m') => s a b -> m a -> m' b

-- | Just as a base monad can be run to remove the monad, so can a
--   transformed monad be unlifted to remove the transformer and obtain the
--   original monad.
class MonadUnTrans s t | t -> s

-- | The overloaded function <a>unlift</a> for monad transformers takes as
--   first argument an "algebra" just like the run function for base
--   monads. For each monad transformer, the same algebra is used as for
--   the base monad of which the transformer is the parameterized variant.
unlift :: (MonadUnTrans s t, Monad m) => s a b -> t m a -> m b

-- | Unlifting the list monad transformer.

-- | Unlifting the partiality monad transformer.

-- | Unlifting the error monad transformer.

-- | Unlifting the state monad transformer

-- | Monadic choice combinator that confines the partiality effect to the
--   first argument. This is a variation on <a>mplus</a> which allows the
--   partiality effect to spread to both arguments and to the result.
mplus' :: (Monad m, MonadUnTrans MaybeAlg t) => t m b -> m b -> m b

-- | Monadic choice combinator. Generalization of <a>mplus'</a> that takes
--   a list of choice arguments rather than a single one.
mswitch :: (Monad m, MonadUnTrans MaybeAlg t) => [t m b] -> m b -> m b

-- | Specialization of <a>mswitch</a> for MaybeT.
mayswitch :: (Monad m) => [MaybeT m b] -> m b -> m b

-- | Monadic function choice combinator that confines the partiality effect
--   to the first argument. This is a variation on <tt>mchoice</tt> which
--   allows the partiality effect to spread to both arguments and to the
--   result.
mchoice' :: (Monad m, MonadUnTrans MaybeAlg t) => (a -> t m b) -> (a -> m b) -> a -> m b

-- | Monadic function choice combinator. Generalization of <a>mchoice'</a>
--   that takes a list of choice arguments rather than a single one.
mchoices :: (Monad m, MonadUnTrans MaybeAlg t, MonadPlus (t m)) => [a -> t m b] -> (a -> m b) -> a -> m b

-- | Implementation variant of <a>mswitch</a> in terms of foldr.
mswitch0 :: (Monad m, MonadUnTrans MaybeAlg t) => [t m b] -> m b -> m b

-- | Implementation variant of <a>mswitch</a> with <a>mplus'</a> expanded:
mswitch1 :: (Monad m, MonadUnTrans MaybeAlg t) => [t m b] -> m b -> m b

-- | Implementation variant of <a>mswitch</a> where the unlift is postponed
--   to the very end.
mswitch' :: (Monad m, MonadUnTrans MaybeAlg t, MonadPlus (t m)) => [t m b] -> m b -> m b
instance Control.Monad.Run.MonadRun (->) Data.Functor.Identity.Identity
instance Control.Monad.Run.MonadRun Control.Monad.Run.MaybeAlg GHC.Base.Maybe
instance Control.Monad.Run.MonadRun (Control.Monad.Run.ErrorAlg e) (Data.Either.Either e)
instance Control.Monad.Run.MonadRun Control.Monad.Run.ListAlg []
instance Control.Monad.Run.MonadRun (Control.Monad.Run.StateAlg s) (Control.Monad.Trans.State.Lazy.State s)
instance Control.Monad.Run.MonadRun (->) GHC.Types.IO
instance Control.Monad.Run.MonadUnTrans Control.Monad.Run.ListAlg Control.Monad.Trans.List.ListT
instance Control.Monad.Run.MonadUnTrans Control.Monad.Run.MaybeAlg Control.Monad.Trans.Maybe.MaybeT
instance Control.Monad.Run.MonadUnTrans (Control.Monad.Run.ErrorAlg e) (Control.Monad.Trans.Error.ErrorT e)
instance Control.Monad.Run.MonadUnTrans (Control.Monad.Run.StateAlg s) (Control.Monad.Trans.State.Lazy.StateT s)

module Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives
class Data x => Term x
data Monad m => TP m
data Monad m => TU a m
paraTP :: Monad m => (forall t. t -> m t) -> TP m
paraTU :: Monad m => (forall t. t -> m a) -> TU a m
applyTP :: (Monad m, Data x) => TP m -> x -> m x
applyTU :: (Monad m, Data x) => TU a m -> x -> m a
adhocTP :: (Monad m, Data t) => TP m -> (t -> m t) -> TP m
adhocTU :: (Monad m, Data t) => TU a m -> (t -> m a) -> TU a m
msubstTP :: (Monad m, Monad m') => (forall t. m t -> m' t) -> TP m -> TP m'
msubstTU :: (Monad m, Monad m') => (m a -> m' a) -> TU a m -> TU a m'
seqTP :: Monad m => TP m -> TP m -> TP m
seqTU :: Monad m => TP m -> TU a m -> TU a m
passTP :: Monad m => TU a m -> (a -> TP m) -> TP m
passTU :: Monad m => TU a m -> (a -> TU b m) -> TU b m
choiceTP :: MonadPlus m => TP m -> TP m -> TP m
choiceTU :: MonadPlus m => TU a m -> TU a m -> TU a m
mchoicesTP :: (Monad m, MonadPlus (t m), MonadUnTrans MaybeAlg t) => [TP (t m)] -> TP m -> TP m
mchoicesTU :: (Monad m, MonadPlus (t m), MonadUnTrans MaybeAlg t) => [TU a (t m)] -> TU a m -> TU a m
allTP :: Monad m => TP m -> TP m
allTU :: Monad m => (a -> a -> a) -> a -> TU a m -> TU a m
allTU' :: (Monad m, Monoid a) => TU a m -> TU a m
oneTP :: MonadPlus m => TP m -> TP m
oneTU :: MonadPlus m => TU a m -> TU a m
anyTP :: MonadPlus m => TP m -> TP m
anyTU :: MonadPlus m => (a -> a -> a) -> a -> TU a m -> TU a m
anyTU' :: (MonadPlus m, Monoid a) => TU a m -> TU a m
someTP :: MonadPlus m => TP m -> TP m
someTU :: MonadPlus m => (a -> a -> a) -> a -> TU a m -> TU a m
someTU' :: (Monoid a, MonadPlus m) => TU a m -> TU a m
injTP :: MonadPlus m => TP m -> TP m


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module is basically a wrapper for the strategy primitives plus
--   some extra basic strategy combinators that can be defined immediately
--   in terms of the primitive ones.
module Data.Generics.Strafunski.StrategyLib.StrategyPrelude

-- | Type-preserving identity. Returns the incoming term without change.
idTP :: Monad m => TP m

-- | Type-preserving failure. Always fails, independent of the incoming
--   term. Uses <a>MonadPlus</a> to model partiality.
failTP :: MonadPlus m => TP m

-- | Type-unifying failure. Always fails, independent of the incoming term.
--   Uses <a>MonadPlus</a> to model partiality.
failTU :: MonadPlus m => TU a m

-- | Type-unifying constant strategy. Always returns the argument value
--   <tt>a</tt>, independent of the incoming term.
constTU :: Monad m => a -> TU a m

-- | Type-unifying monadic constant strategy. Always performs the argument
--   computation <tt>a</tt>, independent of the incoming term. This is a
--   monadic variation of <a>constTU</a>.
compTU :: Monad m => m a -> TU a m

-- | Apply the monomorphic, type-preserving argument function, if its input
--   type matches the input term's type. Otherwise, fail.
monoTP :: (Term a, MonadPlus m) => (a -> m a) -> TP m

-- | Apply the monomorphic, type-unifying argument function, if its input
--   type matches the input term's type. Otherwise, fail.
monoTU :: (Term a, MonadPlus m) => (a -> m b) -> TU b m

-- | Sequential ccomposition of monomorphic function and type-unifying
--   strategy. In other words, after the type-unifying strategy <tt>s</tt>
--   has been applied, the monomorphic function <tt>f</tt> is applied to
--   the resulting value.
dotTU :: Monad m => (a -> b) -> TU a m -> TU b m

-- | Parallel combination of two type-unifying strategies with a binary
--   combinator. In other words, the values resulting from applying the
--   type-unifying strategies are combined to a final value by applying the
--   combinator <tt>o</tt>.
op2TU :: Monad m => (a -> b -> c) -> TU a m -> TU b m -> TU c m

-- | Reduce a type-preserving strategy to a type-unifying one that ignores
--   its result term and returns void, but retains its monadic effects.
voidTP :: Monad m => TP m -> TU () m

-- | Reduce a type-unifying strategy to a type-unifying one that ignores
--   its result value and returns void, but retains its monadic effects.
voidTU :: Monad m => TU u m -> TU () m

-- | Test for constant term, i.e. having no subterms.
con :: MonadPlus m => TP m

-- | Test for compound term, i.e. having at least one subterm.
com :: MonadPlus m => TP m


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module provides combinators which allow one to use strategies to
--   construct generic containers.
module Data.Generics.Strafunski.StrategyLib.ContainerTheme

-- | Pointwise modification of monomorphic functions
modify :: Eq x => (x -> y) -> x -> y -> (x -> y)

-- | Pointwise modification of type-preserving strategies
modifyTP :: (MonadPlus m, Eq t, Term t) => TP m -> t -> m t -> TP m

-- | Pointwise modification of type-unifying strategies
modifyTU :: (MonadPlus m, Eq t, Term t) => TU a m -> t -> m a -> TU a m

-- | Type of generic sets
type GSet = TU () Maybe

-- | Empty generic set.
emptyGSet :: GSet

-- | Completely filled generic set
fullGSet :: GSet

-- | Add an element to a generic set
addGSet :: (Eq t, Term t) => t -> GSet -> GSet

-- | Remove an element from a generic set
removeGSet :: (Eq t, Term t) => t -> GSet -> GSet

-- | Test whether a given element is contained in a generic set
containsGSet :: (Eq t, Term t) => t -> GSet -> Bool

-- | Type of generic maps
type GMap value = TU value Maybe

-- | Empty generic map
emptyGMap :: GMap v

-- | Remove an element from a generic map (my key)
removeGMap :: (Eq t, Term t) => t -> GMap v -> GMap v

-- | Test whether an element with given key is contained in a generic map
containsGMap :: (Eq t, Term t) => t -> GMap v -> Bool

-- | Add an entry with given key and value to a generic map
putGMap :: (Eq t, Term t) => t -> v -> GMap v -> GMap v

-- | Obtain the value for a given key from a generic map
getGMap :: (Eq t, Term t) => t -> GMap v -> Maybe v
type GList = (Integer -> TP Maybe, Integer)
sizeGList :: (t, t1) -> t1
indxGList :: (t1, t) -> t1
emptyGList :: GList
addGList :: Term t => t -> GList -> GList
putGList :: Term t => Integer -> t -> GList -> GList
getGList :: Term t => Integer -> GList -> Maybe t
mapGListTP :: TP Maybe -> GList -> GList
mapGListTU :: Term t => (t -> ()) -> TU a Maybe -> GList -> [Maybe a]
elemsGList :: Term t => (t -> ()) -> GList -> [t]
nth :: [a] -> Integer -> a
type Coder = (Int, TU Int Maybe)
noCode :: Coder
getCode :: Term x => Coder -> x -> Maybe Int
setCode :: (Term x, Eq x) => Coder -> x -> Int -> Coder
nextCode :: Coder -> (Int, Coder)
enCode :: (Term x, Eq x) => Coder -> x -> Coder


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module overloads basic combinators to enable uniform treatment of
--   TU and TP strategies. The overloading scheme is motivated in the "...
--   Polymorphic Symphony" paper. The names in the present module deviate
--   from the paper in that they are postfixed by an "...S" in order to
--   rule out name clashes and to avoid labour-intensive resolution. The
--   class constraints in this module seem to be outrageous but this has to
--   do with a type inferencing bug for class hierarchies in hugs. This bug
--   is removed in the October 2002 release.
module Data.Generics.Strafunski.StrategyLib.OverloadingTheme

-- | Overload completely unconstrained strategy combinators
class Monad m => Strategy s m
voidS :: Strategy s m => s m -> TU () m

-- | Sequential composition
seqS :: Strategy s m => TP m -> s m -> s m

-- | Sequential composition with value passing
passS :: Strategy s m => TU a m -> (a -> s m) -> s m

-- | Overload apply and adhoc combinators
class (Strategy s m, Monad m, Term t) => StrategyApply s m t x | s t -> x

-- | Strategy application
applyS :: StrategyApply s m t x => s m -> t -> m x

-- | Dynamic type case
adhocS :: StrategyApply s m t x => s m -> (t -> m x) -> s m

-- | Overload basic combinators which might involve a monoid
class (Monad m, Strategy s m) => StrategyMonoid s m

-- | Identity (success)
skipS :: StrategyMonoid s m => s m

-- | Push down to all children
allS :: StrategyMonoid s m => s m -> s m

-- | Combine sequentially
combS :: StrategyMonoid s m => s m -> s m -> s m

-- | Overload basic combinators which involve MonadPlus
class (Strategy s m, Monad m, MonadPlus m) => StrategyPlus s m

-- | Failure
failS :: StrategyPlus s m => s m

-- | Choice
choiceS :: StrategyPlus s m => s m -> s m -> s m

-- | Push down to a single child
oneS :: StrategyPlus s m => s m -> s m

-- | Overloaded lifting with failure
monoS :: (StrategyApply s m t x, StrategyPlus s m) => (t -> m x) -> s m

-- | Overload msubst combinator (Experimental)
class StrategyMSubst s

-- | Substitute one monad for another
msubstS :: (StrategyMSubst s, Monad m, Monad m') => (forall t. m t -> m' t) -> s m -> s m'
instance GHC.Base.Monad m => Data.Generics.Strafunski.StrategyLib.OverloadingTheme.Strategy Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TP m
instance GHC.Base.Monad m => Data.Generics.Strafunski.StrategyLib.OverloadingTheme.Strategy (Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TU a) m
instance (GHC.Base.Monad m, Data.Generics.Strafunski.StrategyLib.Models.Deriving.TermRep.Term t) => Data.Generics.Strafunski.StrategyLib.OverloadingTheme.StrategyApply Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TP m t t
instance (GHC.Base.Monad m, Data.Generics.Strafunski.StrategyLib.Models.Deriving.TermRep.Term t) => Data.Generics.Strafunski.StrategyLib.OverloadingTheme.StrategyApply (Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TU a) m t a
instance (GHC.Base.Monad m, Data.Generics.Strafunski.StrategyLib.OverloadingTheme.Strategy Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TP m) => Data.Generics.Strafunski.StrategyLib.OverloadingTheme.StrategyMonoid Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TP m
instance (GHC.Base.Monad m, GHC.Base.Monoid u, Data.Generics.Strafunski.StrategyLib.OverloadingTheme.Strategy (Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TU u) m) => Data.Generics.Strafunski.StrategyLib.OverloadingTheme.StrategyMonoid (Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TU u) m
instance (GHC.Base.Monad m, GHC.Base.MonadPlus m, Data.Generics.Strafunski.StrategyLib.OverloadingTheme.Strategy Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TP m) => Data.Generics.Strafunski.StrategyLib.OverloadingTheme.StrategyPlus Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TP m
instance (GHC.Base.Monad m, GHC.Base.MonadPlus m, Data.Generics.Strafunski.StrategyLib.OverloadingTheme.Strategy (Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TU u) m) => Data.Generics.Strafunski.StrategyLib.OverloadingTheme.StrategyPlus (Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TU u) m
instance Data.Generics.Strafunski.StrategyLib.OverloadingTheme.StrategyMSubst Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TP
instance Data.Generics.Strafunski.StrategyLib.OverloadingTheme.StrategyMSubst (Data.Generics.Strafunski.StrategyLib.Models.Deriving.StrategyPrimitives.TU a)


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module provides combinators to localize monadic effects.
module Data.Generics.Strafunski.StrategyLib.EffectTheme

-- | Replace the monad in a type-preserving strategy, given a monad algebra
--   (see <a>MonadRun</a>) for the monad that is replaced. The two monads
--   are unrelated, so none of the effects in the monad that is replaced
--   carry over to the one that replaces it.
mrunTP :: (Monad m, Monad m', MonadRun s m) => (forall a. s a a) -> TP m -> TP m'

-- | Replace the monad in a type-unifying strategy, given a monad algebra
--   (see <a>MonadRun</a>) for the monad that is replaced. The two monads
--   are unrelated, so none of the effects in the monad that is replaced
--   carry over to the one that replaces it.
mrunTU :: (Monad m, Monad m', MonadRun s m) => s a a -> TU a m -> TU a m'

-- | Add an effect to the monad in a type-preserving strategy. The monads
--   are related by a monad transformer, so the effects of the incoming
--   monad are preserved in the result monad. We use the <a>lift</a>
--   function of the monad transformer.
liftTP :: (Monad (t m), Monad m, MonadTrans t) => TP m -> TP (t m)

-- | Add an effect to the monad in a type-unifying strategy. The monads are
--   related by a monad transformer, so the effects of the incoming monad
--   are preserved in the result monad. We use the <a>lift</a> function of
--   the monad transformer.
liftTU :: (Monad (t m), Monad m, MonadTrans t) => TU a m -> TU a (t m)

-- | remove an effect from the monad of a type-preserving strategy. The
--   monads are related by a monad untransformer (see <a>MonadUnTrans</a>),
--   so the effects of the incoming monad are preserved in the result
--   monad, except for the effect for which a monad algebra is supplied.
unliftTP :: (Monad (t m), Monad m, MonadUnTrans s t) => (forall a. s a a) -> TP (t m) -> TP m

-- | remove an effect from the monad of a type-unifying strategy. The
--   monads are related by a monad untransformer (see <a>MonadUnTrans</a>),
--   so the effects of the incoming monad are preserved in the result
--   monad, except for the effect for which a monad algebra is supplied.
unliftTU :: (Monad (t m), Monad m, MonadUnTrans s t) => s a a -> TU a (t m) -> TU a m

-- | Localize the partiality effect in a type-preserving strategy. A
--   default value must be supplied to be used to recover from failure.
--   Since this default parameter is universally quantified, only
--   <a>undefined</a> and 'error ...' can be used to instantiate it. See
--   also 'unsafeGuaranteeSuccessTP.
guaranteeSuccessTP :: (Monad (t m), Monad m, MonadUnTrans MaybeAlg t) => (forall a. a) -> TP (t m) -> TP m

-- | Localize the partiality effect in a type-unifying strategy. A default
--   value must be supplied to be used to recover from failure.
guaranteeSuccessTU :: (Monad (t m), Monad m, MonadUnTrans MaybeAlg t) => a -> TU a (t m) -> TU a m

-- | Unsafe version of <a>guaranteeSuccessTP</a>. This version uses uses
--   <a>undefined</a> to recover from failure. For the type-preserving
--   case, this is the only possible default value.
unsafeGuaranteeSuccessTP :: (Monad (t m), Monad m, MonadUnTrans MaybeAlg t) => TP (t m) -> TP m

-- | Localize the state of a type-preserving strategy. The first argument
--   represents the initial state.
localStateTP :: (Monad (t m), Monad m, MonadUnTrans (StateAlg s) t) => s -> TP (t m) -> TP m

-- | Localize the state of a type-unifying strategy. The first argument
--   represents the initial state.
localStateTU :: (Monad (t m), Monad m, MonadUnTrans (StateAlg s) t) => s -> TU a (t m) -> TU a m


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module defines combinators to wire up control and data flow.
--   Whenever possible, we define the combinators in an overloaded fashion
--   but we provide type-specialised variants for TP and TU for
--   convenience.
module Data.Generics.Strafunski.StrategyLib.FlowTheme

-- | Attempt a strategy <tt>s</tt>, but recover if it fails.
tryS :: (StrategyPlus s m, StrategyMonoid s m) => s m -> s m

-- | Attempt a type-preserving strategy <tt>s</tt>, but if it fails, return
--   the input term unchanged.
tryTP :: MonadPlus m => TP m -> TP m

-- | Attempt a type-unifying strategy <tt>s</tt>, but if it fails, return
--   the <a>mempty</a> element of a <a>Monoid</a>.
tryTU :: (MonadPlus m, Monoid u) => TU u m -> TU u m

-- | Test for a strategy's success in a type-preserving context.
testS :: Strategy s m => s m -> TP m

-- | Test for a type-preserving strategy's success in a type-preserving
--   context.
testTP :: Monad m => TP m -> TP m

-- | Test for a type-unifying strategy's success in a type-preserving
--   context.
testTU :: Monad m => TU a m -> TP m

-- | If <tt>c</tt> succeeds, pass its value to the then-clause <tt>t</tt>,
--   otherwise revert to the else-clause <tt>e</tt>.
ifS :: StrategyPlus s m => TU u m -> (u -> s m) -> s m -> s m

-- | If <tt>c</tt> succeeds, pass its value to the then-clause <tt>t</tt>,
--   otherwise revert to the else-clause <tt>e</tt>.
ifTP :: MonadPlus m => TU u m -> (u -> TP m) -> TP m -> TP m

-- | If <tt>c</tt> succeeds, pass its value to the then-clause <tt>t</tt>,
--   otherwise revert to the else-clause <tt>e</tt>.
ifTU :: MonadPlus m => TU u m -> (u -> TU u' m) -> TU u' m -> TU u' m

-- | Guard then-clause <tt>t</tt> by the void-valued type-unifying
--   condition <tt>c</tt>.
ifthenS :: Strategy s m => TU () m -> s m -> s m

-- | Guard type-preserving then-clause <tt>t</tt> by the void-valued
--   type-unifying condition <tt>c</tt>.
ifthenTP :: Monad m => TU () m -> TP m -> TP m

-- | Guard type-unifying then-clause <tt>t</tt> by the void-valued
--   type-unifying condition <tt>c</tt>.
ifthenTU :: Monad m => TU () m -> TU u m -> TU u m

-- | Invert the success-value of strategy <tt>s</tt>.
notS :: StrategyPlus s m => s m -> TP m

-- | Invert the success-value of type-preserving strategy <tt>s</tt>. Its
--   output term (in case of success) will be ignored.
notTP :: MonadPlus m => TP m -> TP m

-- | Invert the success-value of type-unifying strategy <tt>s</tt>. Its
--   output value (in case of success) will be ignored.
notTU :: MonadPlus m => TU u m -> TP m

-- | Succeed if exactly one argument strategy succeeds.
xchoiceS :: StrategyPlus s m => s m -> s m -> s m

-- | Succeed if exactly one argument strategy succeeds.
xchoiceTP :: MonadPlus m => TP m -> TP m -> TP m

-- | Succeed if exactly one argument strategy succeeds.
xchoiceTU :: MonadPlus m => TU u m -> TU u m -> TU u m

-- | If predicate <tt>g</tt> holds for the input term, return it as output
--   term, otherwise fail.
filterTP :: (Term t, MonadPlus m) => (t -> Bool) -> TP m

-- | If predicate <tt>g</tt> holds for the input term, return it as output
--   value, otherwise fail.
filterTU :: (Term t, MonadPlus m) => (t -> Bool) -> TU t m

-- | If predicate <tt>g</tt> holds for the input term, return 1 otherwise
--   return 0.
tickTU :: (Monad m, Term t, Num n) => (t -> Bool) -> TU n m

-- | Type guard (function type), i.e., guard that does not observe values
type TypeGuard a = a -> ()

-- | Type guard (function). Typical usage:
--   
--   <pre>
--   full_tdTU (typeTickTU (typeGuard::TypeGuard MyType))
--   </pre>
typeGuard :: TypeGuard a

-- | If type guard holds for the input term, return 1 otherwise return 0.
typeTickTU :: (Term t, Monad m, Num n) => TypeGuard t -> TU n m

-- | If type guard holds for the input term, return it as output term,
--   otherwise fail.
typeFilterTP :: (Term t, MonadPlus m) => TypeGuard t -> TP m

-- | If type guard holds for the input term, return it as output value,
--   otherwise fail.
typeFilterTU :: (Term t, MonadPlus m) => TypeGuard t -> TU t m


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module defines combinators to define metrics extractors.
module Data.Generics.Strafunski.StrategyLib.MetricsTheme

-- | The type of metrics
type Metrics = MetricName -> Integer

-- | The type of metric names
type MetricName = String

-- | Create <a>Metrics</a> with given initial value for all metrics.
initMetrics :: Integer -> Metrics

-- | Create <a>Metrics</a> with 0 as initial value for all metrics.
initMetrics0 :: Metrics

-- | Create <a>Metrics</a> with initTypeMetrics :: MetricName -&gt; a -&gt;
--   Metrics initTypeMetrics key _ = incMetrics1 key initMetrics0
--   
--   Increment metric with the given name with the given value.
incMetrics :: MetricName -> Integer -> Metrics -> Metrics

-- | Increment metric with the given name by 1.
incMetrics1 :: MetricName -> Metrics -> Metrics

-- | Print value of metric with the given name.
putMetricLn :: MetricName -> Metrics -> IO ()

-- | Additionally collect type-based metrics.
typeMetric :: (MonadPlus m, Term a) => TU Metrics m -> (MetricName, a -> ()) -> TU Metrics m

-- | Generic algorithm for computing nesting depth
depthWith :: MonadPlus m => TU () m -> TU Int m
instance GHC.Base.Monoid Data.Generics.Strafunski.StrategyLib.MetricsTheme.Metrics


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module indicates how some strategy combinators could be denoted
--   via infix combinators.
module Data.Generics.Strafunski.StrategyLib.StrategyInfix

-- | Sequential composition
(>>>) :: Strategy s m => TP m -> s m -> s m
infixl 1 >>>

-- | Sequential composition with value passing
(>>>=) :: Strategy s m => TU a m -> (a -> s m) -> s m
infixl 1 >>>=

-- | Sequential composition, ignoring value from first strategy
(>>>-) :: Strategy s m => TU a m -> s m -> s m
infixl 1 >>>-

-- | Dynamic type-case
(-+) :: StrategyApply s m t x => s m -> (t -> m x) -> s m
infixl 2 -+


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module defines traversal schemes. Such schemes have formed the
--   core of StrategyLib since its first release. The portfolio as it
--   stands now captures part of the design in the paper "... Polymorphic
--   Symphony".
module Data.Generics.Strafunski.StrategyLib.TraversalTheme

-- | Full type-preserving traversal in top-down order.
full_tdTP :: Monad m => TP m -> TP m

-- | Full type-preserving traversal in bottom-up order.
full_buTP :: Monad m => TP m -> TP m

-- | Full type-unifying traversal in top-down order.
full_tdTU :: (Monad m, Monoid a) => TU a m -> TU a m

-- | Top-down type-preserving traversal that is cut of below nodes where
--   the argument strategy succeeds.
stop_tdTP :: MonadPlus m => TP m -> TP m

-- | Top-down type-unifying traversal that is cut of below nodes where the
--   argument strategy succeeds.
stop_tdTU :: (MonadPlus m, Monoid a) => TU a m -> TU a m

-- | Top-down type-preserving traversal that performs its argument strategy
--   at most once.
once_tdTP :: MonadPlus m => TP m -> TP m

-- | Top-down type-unifying traversal that performs its argument strategy
--   at most once.
once_tdTU :: MonadPlus m => TU a m -> TU a m

-- | Bottom-up type-preserving traversal that performs its argument
--   strategy at most once.
once_buTP :: MonadPlus m => TP m -> TP m

-- | Bottom-up type-unifying traversal that performs its argument strategy
--   at most once.
once_buTU :: MonadPlus m => TU a m -> TU a m

-- | Top-down type-unifying traversal with propagation of an environment.
once_peTU :: MonadPlus m => e -> (e -> TU e m) -> (e -> TU a m) -> TU a m

-- | Use <a>anyTP</a> instead.
anyTP' :: MonadPlus m => TP m -> TP m

-- | Use <a>someTP</a> instead.
someTP' :: MonadPlus m => TP m -> TP m

-- | Recursive completion of full type-preserving one-layer traverasal
all_recTU :: (Monoid a, Monad m) => (t -> TU a m -> TU a m) -> t -> TU a m

-- | Recursive completion of type-preserving one-layer traversal that
--   succeeds exactly once.
one_recTU :: MonadPlus m => (t -> TU a m -> TU a m) -> t -> TU a m

-- | Full top-down traversal (overloaded between <a>TU</a> and <a>TP</a>).
full_td :: StrategyMonoid s m => s m -> s m

-- | One-hit top-down traversal (overloaded between <a>TU</a> and
--   <a>TP</a>).
once_td :: StrategyPlus s m => s m -> s m

-- | One-hit bottom-up traversal (overloaded between <a>TU</a> and
--   <a>TP</a>).
once_bu :: StrategyPlus s m => s m -> s m

-- | One-hit top-down traversal with environment propagation (overloaded
--   between <a>TU</a> and <a>TP</a>).
once_pe :: StrategyPlus s m => (e -> s m) -> (e -> TU e m) -> e -> s m

-- | See <a>full_tdTP</a>.
topdown :: Monad m => TP m -> TP m

-- | See <a>full_tdTU</a>.
crush :: (Monad m, Monoid u) => TU u m -> TU u m

-- | Type-specialised version of <a>crush</a>, which works with lists
--   instead of any arbitrary monoid.
collect :: Monad m => TU [a] m -> TU [a] m

-- | See <a>once_tdTU</a>.
select :: MonadPlus m => TU u m -> TU u m

-- | See <a>once_peTU</a>.
selectenv :: MonadPlus m => e -> (e -> TU e m) -> (e -> TU a m) -> TU a m


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module defines combinators that iterate until some kind of
--   fixpoint is reached.
module Data.Generics.Strafunski.StrategyLib.FixpointTheme

-- | Exhaustive repeated application at the root of the input term
repeatTP :: MonadPlus m => TP m -> TP m

-- | Exhaustive repeated application throughout the input term.
reduce :: MonadPlus m => TP m -> TP m

-- | Exhaustive repeated application according to the left-most outermost
--   traversal strategy.
outermost :: MonadPlus m => TP m -> TP m

-- | Exhaustive repeated application according to the left-most innermost
--   traversal strategy, implemented in a naive way. Use <a>innermost</a>
--   instead.
innermost' :: MonadPlus m => TP m -> TP m

-- | Exhaustive repeated application according to the left-most innermost
--   traversal strategy, implemented in a more efficient way.
innermost :: MonadPlus m => TP m -> TP m


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module provides algorithms to collect names and their types.
module Data.Generics.Strafunski.StrategyLib.NameTheme

-- | Generic free name analysis algorithm (without types)
freeNames :: (Eq name, Term t) => TU [(name, tpe)] Identity -> TU [name] Identity -> t -> [name]

-- | Generic free name analysis algorithm with types
freeTypedNames :: (Eq name, Term t) => TU [(name, tpe)] Identity -> TU [name] Identity -> [(name, tpe)] -> t -> [(name, tpe)]

-- | Accumulate declarations for focus
boundTypedNames :: (Term f, Term t, Eq name) => TU [(name, tpe)] Identity -> (f -> Maybe f) -> t -> Maybe ([(name, tpe)], f)


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal. In
--   this module, we define path combinator to constrain selection and
--   transformation of nodes or subtrees by path conditions.
module Data.Generics.Strafunski.StrategyLib.PathTheme

-- | Select or transform a node below a node where a condition holds. We
--   find the top-most node which admits selection or transformation below
--   the top-most node which meets the condition. Thus, the distance
--   between guard and application node is minimized.
belowS :: (MonadPlus m, Strategy s m, StrategyPlus s m) => s m -> TU () m -> s m

-- | Select or transform a node below or at a node where a condition holds.
beloweqS :: (MonadPlus m, Strategy s m, StrategyPlus s m) => s m -> TU () m -> s m

-- | Apply a transformation strictly below a node where a condition holds.
belowTP :: MonadPlus m => TP m -> TU () m -> TP m

-- | Apply a transformation below or at a node where a condition holds.
beloweqTP :: MonadPlus m => TP m -> TU () m -> TP m

-- | Select or transform a node above a node where a condition holds. The
--   distance between guard and application node is minimized.
aboveS :: (MonadPlus m, Strategy s m, StrategyPlus s m) => s m -> TU () m -> s m

-- | Select or transform a node above or at a node where a condition holds.
aboveeqS :: (MonadPlus m, Strategy s m, StrategyPlus s m) => s m -> TU () m -> s m

-- | Apply a transformation strictly above a node where a condition holds.
aboveTP :: MonadPlus m => TP m -> TU () m -> TP m

-- | Apply a transformation above or at a node where a condition holds.
aboveeqTP :: MonadPlus m => TP m -> TU () m -> TP m


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module defines a number combinators for keyhole operations, i.e.
--   for operations that have ordinary parametric or adhoc polymorhpic
--   types, but employ strategies inside.
module Data.Generics.Strafunski.StrategyLib.KeyholeTheme

-- | Select the identified focus. Fails if no subterm can be selected.
selectFocus :: (Term f, Term t) => (f -> Maybe f) -> t -> Maybe f

-- | Replace the identified focus. Fails if no subterm can be replaced.
replaceFocus :: (Term t, Term t') => (t -> Maybe t) -> t' -> Maybe t'

-- | Delete the focus assuming it is an element in a list. Fails if no
--   deletion can be performed.
deleteFocus :: (Term f, Term [f], Term t) => (f -> Maybe f) -> t -> Maybe t

-- | Find the host of the focused entity, i.e. a superterm of the focussed
--   subterm.
selectHost :: (Term f, Term h, Term t) => (f -> Maybe f) -> (h -> Maybe h) -> t -> Maybe h
markHost :: (Term f, Term h, Term t) => (f -> Bool) -> (h -> h) -> t -> Maybe t

-- | Put all nodes of a certain type into a list.
listify :: (Term x, Term y) => x -> [y]

-- | Put all nodes of type <a>String</a> into a list. This is a
--   type-specialization of <a>listify</a>.
strings :: Term x => x -> [String]

-- | Apply the argument function to the unique subterm of the input term.
--   Fail if the input term has more subterms or if the subterm is not of
--   the appropriate type. This is a keyhole version of the traversal
--   combinator <a>injTP</a>
inj :: (MonadPlus m, Term x, Term c) => (c -> m c) -> (x -> m x)


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This module defines generic refactoring functionality. See the paper
--   "Towards Generic Refactoring" by Ralf Laemmel. See also
--   generic-refactoring in the examples directory.
module Data.Generics.Strafunski.StrategyLib.RefactoringTheme

-- | Class of abstractions
class (Term abstr, Eq name, Term [abstr], Term apply) => Abstraction abstr name tpe apply | abstr -> name, abstr -> tpe, abstr -> apply, apply -> name, apply -> abstr
getAbstrName :: Abstraction abstr name tpe apply => abstr -> Maybe name
getAbstrParas :: Abstraction abstr name tpe apply => abstr -> Maybe [(name, tpe)]
getAbstrBody :: Abstraction abstr name tpe apply => abstr -> Maybe apply
getApplyName :: Abstraction abstr name tpe apply => apply -> Maybe name
getApplyParas :: Abstraction abstr name tpe apply => apply -> Maybe [(name, tpe)]
constrAbstr :: Abstraction abstr name tpe apply => name -> [(name, tpe)] -> apply -> Maybe abstr
constrApply :: Abstraction abstr name tpe apply => name -> [(name, tpe)] -> Maybe apply

-- | Remove an unused abstraction
eliminate :: (Term prog, Abstraction abstr name tpe apply) => TU [(name, tpe)] Identity -> TU [name] Identity -> (abstr -> Maybe abstr) -> prog -> Maybe prog

-- | Insert a new abstraction
introduce :: (Term prog, Abstraction abstr name tpe apply) => TU [(name, tpe)] Identity -> TU [name] Identity -> ([abstr] -> Maybe [abstr]) -> abstr -> prog -> Maybe prog

-- | Extract an abstraction
extract :: (Term prog, Abstraction abstr name tpe apply) => TU [(name, tpe)] Identity -> TU [name] Identity -> (apply -> Maybe apply) -> ([abstr] -> [abstr]) -> ([abstr] -> Maybe [abstr]) -> ([(name, tpe)] -> apply -> Bool) -> name -> prog -> Maybe prog


-- | This module is part of <tt>StrategyLib</tt>, a library of functional
--   strategy combinators, including combinators for generic traversal.
--   This is the top-level module of the library. One only needs to import
--   this module to use the entire library. Some base modules are exported
--   as well because they are commonly used.
module Data.Generics.Strafunski.StrategyLib.StrategyLib

-- | Identity functor and monad. (a non-strict monad)
newtype Identity a :: * -> *
Identity :: a -> Identity a
[runIdentity] :: Identity a -> a

-- | A state monad parameterized by the type <tt>s</tt> of the state to
--   carry.
--   
--   The <a>return</a> function leaves the state unchanged, while
--   <tt>&gt;&gt;=</tt> uses the final state of the first computation as
--   the initial state of the second.
type State s = StateT s Identity

-- | A state transformer monad parameterized by:
--   
--   <ul>
--   <li><tt>s</tt> - The state.</li>
--   <li><tt>m</tt> - The inner monad.</li>
--   </ul>
--   
--   The <a>return</a> function leaves the state unchanged, while
--   <tt>&gt;&gt;=</tt> uses the final state of the first computation as
--   the initial state of the second.
newtype StateT s (m :: * -> *) a :: * -> (* -> *) -> * -> *
StateT :: (s -> m (a, s)) -> StateT s a
[runStateT] :: StateT s a -> s -> m (a, s)
