Portability | non-portable (GHC Extensions) |
---|---|
Stability | experimental |
Maintainer | Patrick Bahr <paba@diku.dk> |
Safe Haskell | None |
- Stateful Term Homomorphisms
- Deterministic Bottom-Up Tree Transducers
- Deterministic Bottom-Up Tree State Transformations
- Deterministic Top-Down Tree Transducers
- Deterministic Top-Down Tree State Transformations
- Bidirectional Tree State Transformations
- Operators for Finite Mappings
- Product State Spaces
This module defines stateful term homomorphisms. This (slightly oxymoronic) notion extends per se stateless term homomorphisms with a state that is maintained separately by a bottom-up or top-down state transformation. Additionally, this module also provides combinators to run state transformations themselves.
Like regular term homomorphisms also stateful homomorphisms (as well as transducers) can be lifted to annotated signatures (cf. Data.Comp.Annotation).
The recursion schemes provided in this module are derived from tree automata. They allow for a higher degree of modularity and make it possible to apply fusion. The implementation is based on the paper Modular Tree Automata (Mathematics of Program Construction, 263-299, 2012, http://dx.doi.org/10.1007/978-3-642-31113-0_14).
- type QHom f q g = forall a. ([below :: a -> q], [above :: q]) => f a -> Context g a
- below :: ([below :: a -> q], p :< q) => a -> p
- above :: ([above :: q], p :< q) => p
- pureHom :: (forall q. QHom f q g) -> Hom f g
- upTrans :: (Functor f, Functor g) => UpState f q -> QHom f q g -> UpTrans f q g
- runUpHom :: (Functor f, Functor g) => UpState f q -> QHom f q g -> Term f -> Term g
- runUpHomSt :: (Functor f, Functor g) => UpState f q -> QHom f q g -> Term f -> (q, Term g)
- downTrans :: (Traversable f, Functor g) => DownState f q -> QHom f q g -> DownTrans f q g
- runDownHom :: (Traversable f, Functor g) => DownState f q -> QHom f q g -> q -> Term f -> Term g
- runQHom :: (Traversable f, Functor g) => DUpState f (u, d) u -> DDownState f (u, d) d -> QHom f (u, d) g -> d -> Term f -> (u, Term g)
- type UpTrans f q g = forall a. f (q, a) -> (q, Context g a)
- type UpTrans' f q g = forall a. f (q, Context g a) -> (q, Context g a)
- mkUpTrans :: Functor f => UpTrans' f q g -> UpTrans f q g
- runUpTrans :: (Functor f, Functor g) => UpTrans f q g -> Term f -> Term g
- compUpTrans :: (Functor f, Functor g, Functor h) => UpTrans g p h -> UpTrans f q g -> UpTrans f (q, p) h
- compUpTransHom :: (Functor g, Functor h) => UpTrans g q h -> Hom f g -> UpTrans f q h
- compHomUpTrans :: (Functor g, Functor h) => Hom g h -> UpTrans f q g -> UpTrans f q h
- compUpTransSig :: UpTrans g q h -> SigFun f g -> UpTrans f q h
- compSigUpTrans :: Functor g => SigFun g h -> UpTrans f q g -> UpTrans f q h
- compAlgUpTrans :: Functor g => Alg g a -> UpTrans f q g -> Alg f (q, a)
- type UpState f q = Alg f q
- tagUpState :: Functor f => (q -> p) -> (p -> q) -> UpState f q -> UpState f p
- runUpState :: Functor f => UpState f q -> Term f -> q
- prodUpState :: Functor f => UpState f p -> UpState f q -> UpState f (p, q)
- type DUpState f p q = forall a. ([below :: a -> p], [above :: p], q :< p) => f a -> q
- dUpState :: Functor f => UpState f q -> DUpState f p q
- upState :: DUpState f q q -> UpState f q
- runDUpState :: Functor f => DUpState f q q -> Term f -> q
- prodDUpState :: (p :< c, q :< c) => DUpState f c p -> DUpState f c q -> DUpState f c (p, q)
- (<*>) :: (p :< c, q :< c) => DUpState f c p -> DUpState f c q -> DUpState f c (p, q)
- type DownTrans f q g = forall a. q -> f (q -> a) -> Context g a
- type DownTrans' f q g = forall a. q -> f (q -> Context g a) -> Context g a
- mkDownTrans :: Functor f => DownTrans' f q g -> DownTrans f q g
- runDownTrans :: (Functor f, Functor g) => DownTrans f q g -> q -> Cxt h f a -> Cxt h g a
- compDownTrans :: (Functor f, Functor g, Functor h) => DownTrans g p h -> DownTrans f q g -> DownTrans f (q, p) h
- compDownTransSig :: DownTrans g q h -> SigFun f g -> DownTrans f q h
- compSigDownTrans :: Functor g => SigFun g h -> DownTrans f q g -> DownTrans f q h
- compDownTransHom :: (Functor g, Functor h) => DownTrans g q h -> Hom f g -> DownTrans f q h
- compHomDownTrans :: (Functor g, Functor h) => Hom g h -> DownTrans f q g -> DownTrans f q h
- type DownState f q = forall a. Ord a => (q, f a) -> Map a q
- tagDownState :: (q -> p) -> (p -> q) -> DownState f q -> DownState f p
- prodDownState :: DownState f p -> DownState f q -> DownState f (p, q)
- type DDownState f p q = forall i. (Ord i, [below :: i -> p], [above :: p], q :< p) => f i -> Map i q
- dDownState :: DownState f q -> DDownState f p q
- downState :: DDownState f q q -> DownState f q
- prodDDownState :: (p :< c, q :< c) => DDownState f c p -> DDownState f c q -> DDownState f c (p, q)
- (>*<) :: (p :< c, q :< c, Functor f) => DDownState f c p -> DDownState f c q -> DDownState f c (p, q)
- runDState :: Traversable f => DUpState f (u, d) u -> DDownState f (u, d) d -> d -> Term f -> u
- (&) :: Ord k => Map k v -> Map k v -> Map k v
- (|->) :: k -> a -> Map k a
- o :: Map k a
- module Data.Comp.Automata.Product
Stateful Term Homomorphisms
type QHom f q g = forall a. ([below :: a -> q], [above :: q]) => f a -> Context g aSource
This type represents stateful term homomorphisms. Stateful term homomorphisms have access to a state that is provided (separately) by a bottom-up or top-down state transformation function (or both).
below :: ([below :: a -> q], p :< q) => a -> pSource
This function provides access to components of the states from below.
above :: ([above :: q], p :< q) => pSource
This function provides access to components of the state from above
pureHom :: (forall q. QHom f q g) -> Hom f gSource
This function turns a stateful homomorphism with a fully polymorphic state type into a (stateless) homomorphism.
Bottom-Up State Propagation
upTrans :: (Functor f, Functor g) => UpState f q -> QHom f q g -> UpTrans f q gSource
This function constructs a UTT from a given stateful term homomorphism with the state propagated by the given UTA.
runUpHom :: (Functor f, Functor g) => UpState f q -> QHom f q g -> Term f -> Term gSource
This function applies a given stateful term homomorphism with a state space propagated by the given UTA to a term.
runUpHomSt :: (Functor f, Functor g) => UpState f q -> QHom f q g -> Term f -> (q, Term g)Source
This is a variant of runUpHom
that also returns the final state
of the run.
Top-Down State Propagation
downTrans :: (Traversable f, Functor g) => DownState f q -> QHom f q g -> DownTrans f q gSource
This function constructs a DTT from a given stateful term-- homomorphism with the state propagated by the given DTA.
runDownHom :: (Traversable f, Functor g) => DownState f q -> QHom f q g -> q -> Term f -> Term gSource
This function applies a given stateful term homomorphism with a state space propagated by the given DTA to a term.
Bidirectional State Propagation
runQHom :: (Traversable f, Functor g) => DUpState f (u, d) u -> DDownState f (u, d) d -> QHom f (u, d) g -> d -> Term f -> (u, Term g)Source
This combinator runs a stateful term homomorphisms with a state space produced both on a bottom-up and a top-down state transformation.
Deterministic Bottom-Up Tree Transducers
type UpTrans f q g = forall a. f (q, a) -> (q, Context g a)Source
This type represents transition functions of total, deterministic bottom-up tree transducers (UTTs).
runUpTrans :: (Functor f, Functor g) => UpTrans f q g -> Term f -> Term gSource
This function runs the given UTT on the given term.
compUpTrans :: (Functor f, Functor g, Functor h) => UpTrans g p h -> UpTrans f q g -> UpTrans f (q, p) hSource
This function composes two UTTs. (see TATA, Theorem 6.4.5)
compUpTransHom :: (Functor g, Functor h) => UpTrans g q h -> Hom f g -> UpTrans f q hSource
This combinator composes a homomorphism followed by a UTT.
compHomUpTrans :: (Functor g, Functor h) => Hom g h -> UpTrans f q g -> UpTrans f q hSource
This combinator composes a UTT followed by a homomorphism.
compUpTransSig :: UpTrans g q h -> SigFun f g -> UpTrans f q hSource
This combinator composes a signature function followed by a UTT.
compSigUpTrans :: Functor g => SigFun g h -> UpTrans f q g -> UpTrans f q hSource
This combinator composes a UTT followed by a signature function.
compAlgUpTrans :: Functor g => Alg g a -> UpTrans f q g -> Alg f (q, a)Source
This function composes a UTT with an algebra.
Deterministic Bottom-Up Tree State Transformations
Monolithic State
type UpState f q = Alg f qSource
This type represents transition functions of total, deterministic bottom-up tree acceptors (UTAs).
tagUpState :: Functor f => (q -> p) -> (p -> q) -> UpState f q -> UpState f pSource
Changes the state space of the UTA using the given isomorphism.
runUpState :: Functor f => UpState f q -> Term f -> qSource
This combinator runs the given UTA on a term returning the final state of the run.
prodUpState :: Functor f => UpState f p -> UpState f q -> UpState f (p, q)Source
This function combines the product UTA of the two given UTAs.
Modular State
type DUpState f p q = forall a. ([below :: a -> p], [above :: p], q :< p) => f a -> qSource
This type represents transition functions of generalised deterministic bottom-up tree acceptors (GUTAs) which have access to an extended state space.
dUpState :: Functor f => UpState f q -> DUpState f p qSource
This combinator turns an arbitrary UTA into a GUTA.
upState :: DUpState f q q -> UpState f qSource
This combinator turns a GUTA with the smallest possible state space into a UTA.
runDUpState :: Functor f => DUpState f q q -> Term f -> qSource
This combinator runs a GUTA on a term.
prodDUpState :: (p :< c, q :< c) => DUpState f c p -> DUpState f c q -> DUpState f c (p, q)Source
This combinator constructs the product of two GUTA.
Deterministic Top-Down Tree Transducers
type DownTrans f q g = forall a. q -> f (q -> a) -> Context g aSource
This type represents transition functions of total deterministic top-down tree transducers (DTTs).
type DownTrans' f q g = forall a. q -> f (q -> Context g a) -> Context g aSource
mkDownTrans :: Functor f => DownTrans' f q g -> DownTrans f q gSource
This function turns a DTT defined using the type DownTrans'
in
to the canonical form of type DownTrans
.
runDownTrans :: (Functor f, Functor g) => DownTrans f q g -> q -> Cxt h f a -> Cxt h g aSource
Thsis function runs the given DTT on the given tree.
compDownTrans :: (Functor f, Functor g, Functor h) => DownTrans g p h -> DownTrans f q g -> DownTrans f (q, p) hSource
This function composes two DTTs. (see W.C. Rounds /Mappings and grammars on trees/, Theorem 2.)
compDownTransSig :: DownTrans g q h -> SigFun f g -> DownTrans f q hSource
This function composes a DTT after a function.
compSigDownTrans :: Functor g => SigFun g h -> DownTrans f q g -> DownTrans f q hSource
This function composes a signature function after a DTT.
compDownTransHom :: (Functor g, Functor h) => DownTrans g q h -> Hom f g -> DownTrans f q hSource
This function composes a DTT after a homomorphism.
compHomDownTrans :: (Functor g, Functor h) => Hom g h -> DownTrans f q g -> DownTrans f q hSource
This function composes a homomorphism after a DTT.
Deterministic Top-Down Tree State Transformations
Monolithic State
type DownState f q = forall a. Ord a => (q, f a) -> Map a qSource
This type represents transition functions of total, deterministic top-down tree acceptors (DTAs).
tagDownState :: (q -> p) -> (p -> q) -> DownState f q -> DownState f pSource
Changes the state space of the DTA using the given isomorphism.
prodDownState :: DownState f p -> DownState f q -> DownState f (p, q)Source
This function constructs the product DTA of the given two DTAs.
Modular State
type DDownState f p q = forall i. (Ord i, [below :: i -> p], [above :: p], q :< p) => f i -> Map i qSource
This type represents transition functions of generalised deterministic top-down tree acceptors (GDTAs) which have access
dDownState :: DownState f q -> DDownState f p qSource
This combinator turns an arbitrary DTA into a GDTA.
downState :: DDownState f q q -> DownState f qSource
This combinator turns a GDTA with the smallest possible state space into a DTA.
prodDDownState :: (p :< c, q :< c) => DDownState f c p -> DDownState f c q -> DDownState f c (p, q)Source
This combinator constructs the product of two dependant top-down state transformations.
(>*<) :: (p :< c, q :< c, Functor f) => DDownState f c p -> DDownState f c q -> DDownState f c (p, q)Source
This is a synonym for prodDDownState
.
Bidirectional Tree State Transformations
runDState :: Traversable f => DUpState f (u, d) u -> DDownState f (u, d) d -> d -> Term f -> uSource
This combinator combines a bottom-up and a top-down state transformations. Both state transformations can depend mutually recursive on each other.
Operators for Finite Mappings
Product State Spaces
module Data.Comp.Automata.Product