Data.Comp.Automata

Stateful Term Homomorphisms

type QHom f q g = forall a. ([below :: a -> q], [above :: q]) => f a -> Context g a

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 -> p

This function provides access to components of the states from below.

above :: ([above :: q], p :< q) => p

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 g

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 g

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)

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 g

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 g

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)

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)

This type represents transition functions of deterministic bottom-up tree transducers (DUTTs).

runUpTrans :: (Functor f, Functor g) => UpTrans f q g -> Term f -> Term g

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) h

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 h

This combinator composes a homomorphism followed by a DUTT.

compHomUpTrans :: (Functor g, Functor h) => Hom g h -> UpTrans f q g -> UpTrans f q h

This combinator composes a DUTT followed by a homomorphism.

compUpTransSig :: UpTrans g q h -> SigFun f g -> UpTrans f q h

This combinator composes a signature function followed by a DUTT.

compSigUpTrans :: Functor g => SigFun g h -> UpTrans f q g -> UpTrans f q h

This combinator composes a DUTT followed by a signature function.

compAlgUpTrans :: Functor g => Alg g a -> UpTrans f q g -> Alg f (q, a)

This function composes a DUTT with an algebra.

Deterministic Bottom-Up Tree State Transformations

Monolithic State

type UpState f q = Alg f q

This type represents transition functions of deterministic bottom-up tree acceptors (DUTAs).

tagUpState :: Functor f => (q -> p) -> (p -> q) -> UpState f q -> UpState f p

Changes the state space of the DUTA using the given isomorphism.

runUpState :: Functor f => UpState f q -> Term f -> q

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)

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 -> q

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 q

This combinator turns an arbitrary DUTA into a GDUTA.

upState :: DUpState f q q -> UpState f q

This combinator turns a GDUTA with the smallest possible state space into a DUTA.

runDUpState :: Functor f => DUpState f q q -> Term f -> q

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)

This combinator constructs the product of two GDUTA.

(<*>) :: (p :< c, q :< c) => DUpState f c p -> DUpState f c q -> DUpState f c (p, q)

Deterministic Top-Down Tree Transducers

type DownTrans f q g = forall a. (q, f a) -> Context g (q, a)

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 a

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) h

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 h

This function composes a DDTT after a function.

compSigDownTrans :: Functor g => SigFun g h -> DownTrans f q g -> DownTrans f q h

This function composes a signature function after a DDTT.

compDownTransHom :: (Functor g, Functor h) => DownTrans g q h -> Hom f g -> DownTrans f q h

This function composes a DDTT after a homomorphism.

compHomDownTrans :: (Functor g, Functor h) => Hom g h -> DownTrans f q g -> DownTrans f q h

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 q

This type represents transition functions of deterministic top-down tree acceptors (DDTAs).

tagDownState :: (q -> p) -> (p -> q) -> DownState f q -> DownState f p

Changes the state space of the DDTA using the given isomorphism.

prodDownState :: DownState f p -> DownState f q -> DownState f (p, q)

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 q

This type represents transition functions of generalised deterministic top-down tree acceptors (GDDTAs) which have access

dDownState :: DownState f q -> DDownState f p q

This combinator turns an arbitrary DDTA into a GDDTA.

downState :: DDownState f q q -> DownState f q

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)

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)

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 -> u

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

(&) :: Ord k => Map k v -> Map k v -> Map k v

left-biased union of two mappings.

(|->) :: k -> a -> Map k a

This operator constructs a singleton mapping.

o :: Map k a

This is the empty mapping.

Product State Spaces

module Data.Comp.Automata.Product