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


-- | Generic rewriting library for regular datatypes.
--   
--   This package provides rewriting functionality for regular datatypes.
--   Regular datatypes are recursive datatypes such as lists, binary trees,
--   etc. This library cannot be used with mutually recursive datatypes or
--   with nested datatypes.
--   
--   This library has been described in the paper:
--   
--   <ul>
--   <li><i>A Lightweight Approach to Datatype-Generic Rewriting.</i>
--   Thomas van Noort, Alexey Rodriguez, Stefan Holdermans, Johan Jeuring,
--   Bastiaan Heeren. ACM SIGPLAN Workshop on Generic Programming
--   2008.</li>
--   </ul>
--   
--   More information about this library can be found at
--   <a>http://www.cs.uu.nl/wiki/GenericProgramming/Rewriting</a>.
@package rewriting
@version 0.2


-- | Summary: Generic functions for traversal strategies.
module Generics.Regular.Rewriting.Strategies

-- | Applies a function to the first subtree (possibly the tree itself) on
--   which it succeeds, using a preorder traversal.
once :: (Regular a, GMap (PF a), Functor m, MonadPlus m) => (a -> m a) -> a -> m a

-- | Applies a function to the first immediate child of a value on which it
--   succeeds.
one :: (Regular a, GMap (PF a), Functor m, MonadPlus m) => (a -> m a) -> a -> m a

-- | Applies a monadic function exhaustively in a top-down fashion.
topdownM :: (Regular a, GMap (PF a), Functor m, Monad m) => (a -> m a) -> a -> m a

-- | Applies a function exhaustively in a top-down fashion
topdown :: (Regular a, Functor (PF a)) => (a -> a) -> a -> a

-- | Applies a monadic function exhaustively in a bottom-up fashion.
bottomupM :: (Regular a, GMap (PF a), Functor m, Monad m) => (a -> m a) -> a -> m a

-- | Applies a function exhaustively in a bottom-up fashion
bottomup :: (Regular a, Functor (PF a)) => (a -> a) -> a -> a

-- | Applies a monadic function to all the immediate children of a value.
composM :: (Regular a, GMap (PF a), Functor m, Monad m) => (a -> m a) -> a -> m a

-- | Applies a function to all the immediate children of a value.
compos :: (Regular a, Functor (PF a)) => (a -> a) -> a -> a
instance (MonadPlus m) => Monad (S m)


-- | Summary: Functions for transforming a rule specification to a rule.
module Generics.Regular.Rewriting.Rules

-- | Specifies a rule as a value of a datatype.
data RuleSpec a
(:~>) :: a -> a -> RuleSpec a

-- | Returns the left-hand side of a rule.
lhsR :: RuleSpec a -> a

-- | Returns the right-hand side of a rule.
rhsR :: RuleSpec a -> a

-- | Allows metavariables on either side of a rule.
type Rule a = RuleSpec (SchemeOf a)

-- | Extends the pattern functor of a value.
type SchemeOf a = Scheme (PF a)
type Metavar = Int

-- | Constructs a metavariable.
metavar :: Metavar -> Scheme f

-- | Constructs a pattern functor value.
pf :: f (Scheme f) -> Scheme f

-- | Recursively converts a value to a <tt>SchemeOf</tt> value.
toScheme :: (Regular a, Functor (PF a)) => a -> SchemeOf a

-- | A view on schemes to easily distinguish metavariables from pattern
--   functor values.
data SchemeView f
Metavar :: Metavar -> SchemeView f
PF :: (f (Scheme f)) -> SchemeView f

-- | Returns the value corresponding to the <tt>SchemeView</tt>.
schemeView :: Scheme f -> SchemeView f

-- | Folds a <tt>Scheme</tt> value given a function to apply to
--   metavariables and a function to apply to a pattern functor value.
foldScheme :: (Functor f) => (Metavar -> a) -> (f a -> a) -> Scheme f -> a

-- | The type class <tt>Builder</tt> captures the functions, that are
--   defined by induction on the type argument, that construct appropriate
--   <tt>left</tt> and <tt>right</tt> values. These values are used to
--   transform a rule specification to a rule.
class (Regular (Target a)) => Builder a where { type family Target a :: *; }
base :: (Builder a) => a -> RuleSpec (Target a)
diag :: (Builder a) => a -> [RuleSpec (Target a)]

-- | Transforms a rule specification to a rule and returns <tt>Nothing</tt>
--   if an unbound metavariable occurs in the right-hand side of the rule.
ruleM :: (Builder r, CrushR (PF (Target r)), Zip (PF (Target r)), Functor (PF (Target r))) => r -> Maybe (Rule (Target r))

-- | Transforms a rule specification to a rule and throws a runtime error
--   if an unbound metavariable occurs in the right-hand side of the rule.
rule :: (Builder r, CrushR (PF (Target r)), Functor (PF (Target r)), Zip (PF (Target r))) => r -> Rule (Target r)
instance (Builder a, Regular b, LR (PF b)) => Builder (b -> a)
instance (Regular a) => Builder (RuleSpec a)


-- | Summary: Core machinery for rewriting terms.
module Generics.Regular.Rewriting.Machinery

-- | The <tt>Rewrite</tt> is a type class synonym, hiding some of the
--   implementation details.
--   
--   To be able to use the rewriting functions, the user is required to
--   provide an instance of this type class.
class (Regular a, CrushR (PF a), GMap (PF a), GShow (PF a), Zip (PF a), LR (PF a), Functor (PF a)) => Rewrite a

-- | Applies a rule specification to a term, obtaining a monadic value.
applyRuleM :: (Builder r, Rewrite (Target r), Monad m) => r -> Target r -> m (Target r)

-- | Applies a rule specification to a term, obtaining the original term
--   when rewriting fails.
applyRule :: (Builder r, Rewrite (Target r)) => r -> Target r -> Target r

-- | Rewrites a term, obtaining a monadic value.
rewriteM :: (Rewrite a, Monad m) => Rule a -> a -> m a

-- | Rewrites a term, obtaining the original term when rewriting fails.
rewrite :: (Rewrite a) => Rule a -> a -> a


-- | Summary: Types for structural representation. This module simply
--   reexports <a>Generics.Regular.Base</a>, and is provided for
--   backwards-compatibility only.
module Generics.Regular.Rewriting.Representations


-- | Summary: Base generic functions that are used for generic rewriting.
--   This module simply reexports <a>Generics.Regular.Functions</a>, and is
--   provided for backwards-compatibility only.
module Generics.Regular.Rewriting.Base


-- | By importing this module, the user is able to use all the rewriting
--   machinery. The user is only required to provide an instance of
--   <tt>Regular</tt> and <tt>Rewrite</tt> for the datatype.
--   
--   Consider a datatype representing logical propositions:
--   
--   <pre>
--   data Expr = Const Int | Expr :++: Expr | Expr :**: Expr deriving Show
--   
--   infixr 5 :++:
--   infixr 6 :**:
--   </pre>
--   
--   An instance of <tt>Regular</tt> would look like:
--   
--   <pre>
--   data Const
--   data Plus
--   data Times
--   
--   instance Constructor Const where conName _ = "Const"
--   instance Constructor Plus where 
--     conName _   = "(:++:)"
--     conFixity _ = Infix RightAssociative 5
--   instance Constructor Times where 
--     conName _   = "(:**:)"
--     conFixity _ = Infix RightAssociative 6
--   
--   type instance PF Expr =  C Const (K Int) 
--                        :+: C Plus  (I :*: I) 
--                        :+: C Times (I :*: I)
--   
--   instance Regular Expr where
--     from (Const n)    = L (C (K n))
--     from (e1 :++: e2) = R (L (C $ (I e1) :*: (I e2)))
--     from (e1 :**: e2) = R (R (C $ (I e1) :*: (I e2)))
--     to (L (C (K n)))                   = Const n
--     to (R (L (C ((I r1) :*: (I r2))))) = r1 :++: r2
--     to (R (R (C ((I r1) :*: (I r2))))) = r1 :**: r2
--   </pre>
--   
--   Alternatively, the above code could be derived using Template Haskell:
--   
--   <pre>
--   $(deriveConstructors ''Expr)
--   $(deriveRegular ''Expr "PFExpr")
--   type instance PF Expr = PFExpr
--   </pre>
--   
--   Additionally, the instance <tt>Rewrite</tt> would look like:
--   
--   <pre>
--   instance Rewrite Expr
--   </pre>
--   
--   Rules are built like this:
--   
--   <pre>
--   rule1 :: Rule Expr
--   rule1 = 
--     rule $ \x -&gt; x :++: Const 0 :~&gt;
--                 x
--   rule5 :: Rule Expr
--   rule5 = 
--     rule $ \x y z -&gt; x :**: (y :++: z) :~&gt;
--                     (x :**: y) :++: (x :**: z)
--   </pre>
--   
--   And applied as follows:
--   
--   <pre>
--   test1 :: Maybe Expr
--   test1 = rewriteM rule1 (Const 2 :++: Const 0)
--   test10 :: Maybe Expr
--   test10 = rewriteM rule5 ((Const 1) :**: ((Const 2) :++: (Const 3)))
--   </pre>
module Generics.Regular.Rewriting