Portability | non-portable (GHC Extensions) |
---|---|
Stability | experimental |
Maintainer | Patrick Bahr <paba@diku.dk> |
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 tree automaton.
- (&) :: Ord k => Map k v -> Map k v -> Map k v
- (|->) :: k -> a -> Map k a
- o :: Map k a
- below :: (?below :: a -> q, p :< q) => a -> p
- above :: (?above :: q, p :< q) => p
- explicit :: q -> (a -> q) -> ((?above :: q, ?below :: a -> q) => b) -> b
- type QHom f q g = forall a. (?below :: a -> q, ?above :: q) => f a -> Context g a
- type UpTrans f q g = forall a. f (q, a) -> (q, Context g a)
- upAlg :: Functor g => UpTrans f q g -> Alg f (q, Term g)
- runUpTrans :: (Functor f, Functor g) => UpTrans f q g -> Term f -> (q, Term g)
- runUpTrans' :: (Functor f, Functor g) => UpTrans f q g -> Context f (q, a) -> (q, Context g a)
- compUpTrans :: (Functor f, Functor g, Functor h) => UpTrans g p h -> UpTrans f q g -> UpTrans f (q, p) h
- 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)
- 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 -> (q, Term g)
- 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
- runDownTrans' :: (Functor f, Functor g) => DownTrans f q g -> q -> Cxt h f a -> Cxt h g (q, a)
- compDownTrans :: (Functor f, Functor g, Functor h) => DownTrans g p h -> DownTrans f q g -> DownTrans f (q, p) 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)
- data ProdState p q
- prodMap :: Ord i => p -> q -> Map i p -> Map i q -> Map i (p, q)
- appMap :: Zippable f => (forall i. Ord i => f i -> Map i q) -> q -> f b -> f (q, b)
- downTrans :: Zippable f => DownState f q -> QHom f q g -> DownTrans f q g
- runDownHom :: (Zippable f, Functor g) => DownState f q -> QHom f q g -> q -> Term f -> Term g
- 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 :: Zippable f => DUpState f (u, d) u -> DDownState f (u, d) d -> d -> Term f -> u
- module Data.Comp.Automata.Product
Documentation
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
explicit :: q -> (a -> q) -> ((?above :: q, ?below :: a -> q) => b) -> bSource
Turns the explicit parameters ?above
and ?below
into explicit
ones.
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 DUTA or a DDTA (or both).
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).
upAlg :: Functor g => UpTrans f q g -> Alg f (q, Term g)Source
This function transforms DUTT transition function into an algebra.
runUpTrans :: (Functor f, Functor g) => UpTrans f q g -> Term f -> (q, Term g)Source
This function runs the given DUTT on the given term.
runUpTrans' :: (Functor f, Functor g) => UpTrans f q g -> Context f (q, a) -> (q, Context g a)Source
This function generalises runUpTrans
to contexts. Therefore,
additionally, a transition function for the holes is needed.
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)
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.
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 -> (q, Term g)Source
This function applies a given stateful term homomorphism with a state space propagated by the given DUTA to a term.
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.
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.
runDownTrans' :: (Functor f, Functor g) => DownTrans f q g -> q -> Cxt h f a -> Cxt h g (q, a)Source
This 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. Flp, H. Vogler Syntax-Directed Semantics, Theorem 3.39)
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.
This type is needed to construct the product of two DDTAs.
prodMap :: Ord i => p -> q -> Map i p -> Map i q -> Map i (p, q)Source
This function constructs the pointwise product of two maps each with a default value.
appMap :: Zippable f => (forall i. Ord i => f i -> Map i q) -> q -> f b -> f (q, b)Source
Apply the given state mapping to the given functorial value by adding the state to the corresponding index if it is in the map and otherwise adding the provided default state.
downTrans :: Zippable 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 :: (Zippable 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.
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 to an extended state space.
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 GDDTA.
(>*<) :: (p :< c, q :< c, Functor f) => DDownState f c p -> DDownState f c q -> DDownState f c (p, q)Source
module Data.Comp.Automata.Product