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.

- module Data.Comp.Automata.Product
- 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 :: 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
- runQHom :: (Zippable 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 :: Zippable 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

# Documentation

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 DUTA or a DDTA (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 :: 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.

## Bidirectional State Propagation

runQHom :: (Zippable 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. Flp, 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 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 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 :: Zippable 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.