Safe Haskell | Safe-Infered |
---|
- 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
- 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
- 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 => 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)
- 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 a) -> Context g (q, a)
- 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
Bottom-Up State Propagation
upTrans :: (Functor f, Functor g) => UpState f q -> QHom f q g -> UpTrans f q gSource
This function constructs a DUTT from a given stateful term homomorphism with the state propagated by the given DUTA.
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 DUTA 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 => DownState f q -> QHom f q g -> DownTrans f q gSource
This function constructs a DDTT from a given stateful term-- homomorphism with the state propagated by the given DDTA.
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 DDTA 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 deterministic bottom-up tree transducers (DUTTs).
runUpTrans :: (Functor f, Functor g) => UpTrans f q g -> Term f -> Term gSource
This function runs the given DUTT 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 DUTTs. (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 DUTT.
compHomUpTrans :: (Functor g, Functor h) => Hom g h -> UpTrans f q g -> UpTrans f q hSource
This combinator composes a DUTT 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 DUTT.
compSigUpTrans :: Functor g => SigFun g h -> UpTrans f q g -> UpTrans f q hSource
This combinator composes a DUTT followed by a signature function.
compAlgUpTrans :: Functor g => Alg g a -> UpTrans f q g -> Alg f (q, a)Source
This function composes a DUTT with an algebra.
Deterministic Bottom-Up Tree State Transformations
Monolithic State
type UpState f q = Alg f qSource
This type represents transition functions of deterministic bottom-up tree acceptors (DUTAs).
tagUpState :: Functor f => (q -> p) -> (p -> q) -> UpState f q -> UpState f pSource
Changes the state space of the DUTA using the given isomorphism.
runUpState :: Functor f => UpState f q -> Term f -> qSource
This combinator runs the given DUTA 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 DUTA of the two given DUTAs.
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 (GDUTAs) which have access to an extended state space.
dUpState :: Functor f => UpState f q -> DUpState f p qSource
This combinator turns an arbitrary DUTA into a GDUTA.
upState :: DUpState f q q -> UpState f qSource
This combinator turns a GDUTA with the smallest possible state space into a DUTA.
runDUpState :: Functor f => DUpState f q q -> Term f -> qSource
This combinator runs a GDUTA 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 GDUTA.
Deterministic Top-Down Tree Transducers
type DownTrans f q g = forall a. (q, f a) -> Context g (q, a)Source
This type represents transition functions of deterministic top-down tree transducers (DDTTs).
runDownTrans :: (Functor f, Functor g) => DownTrans f q g -> q -> Cxt h f a -> Cxt h g aSource
Thsis function runs the given DDTT 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 DDTTs. (see Z. Fulop, H. Vogler Syntax-Directed Semantics, Theorem 3.39)
compDownTransSig :: DownTrans g q h -> SigFun f g -> DownTrans f q hSource
This function composes a DDTT 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 DDTT.
compDownTransHom :: (Functor g, Functor h) => DownTrans g q h -> Hom f g -> DownTrans f q hSource
This function composes a DDTT 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 DDTT.
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 deterministic top-down tree acceptors (DDTAs).
tagDownState :: (q -> p) -> (p -> q) -> DownState f q -> DownState f pSource
Changes the state space of the DDTA using the given isomorphism.
prodDownState :: DownState f p -> DownState f q -> DownState f (p, q)Source
This function constructs the product DDTA of the given two DDTAs.
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 (GDDTAs) which have access
dDownState :: DownState f q -> DDownState f p qSource
This combinator turns an arbitrary DDTA into a GDDTA.
downState :: DDownState f q q -> DownState f qSource
This combinator turns a GDDTA with the smallest possible state space into a DDTA.
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