Portability | non-portable (GHC Extensions) |
---|---|

Stability | experimental |

Maintainer | Patrick Bahr <paba@diku.dk> |

Safe Haskell | None |

- 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

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 state transformation. Additionally, this module also provides combinators to run state transformations themselves.

Like regular term homomorphisms also stateful homomorphisms (as well as transducers) can be lifted to annotated signatures (cf. Data.Comp.Annotation).

The recursion schemes provided in this module are derived from tree
automata. They allow for a higher degree of modularity and make it
possible to apply fusion. The implementation is based on the paper
*Modular Tree Automata* (Mathematics of Program Construction,
263-299, 2012, http://dx.doi.org/10.1007/978-3-642-31113-0_14).

- 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
- pureHom :: (forall q. QHom f q g) -> Hom f g
- 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

pureHom :: (forall q. QHom f q g) -> Hom f gSource

This function turns a stateful homomorphism with a fully polymorphic state type into a (stateless) homomorphism.

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