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