Copyright | (c) 2010-2012 Patrick Bahr |
---|---|

License | BSD3 |

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

Stability | experimental |

Portability | non-portable (GHC Extensions) |

Safe Haskell | None |

Language | Haskell98 |

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, Functor g) => 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)
- type UpTrans' f q g = forall a. f (q, Context g a) -> (q, Context g a)
- mkUpTrans :: Functor f => UpTrans' f q g -> UpTrans f q g
- 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 (q -> a) -> Context g a
- type DownTrans' f q g = forall a. q -> f (q -> Context g a) -> Context g a
- mkDownTrans :: Functor f => DownTrans' f q g -> DownTrans f q g
- 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 a Source

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 Source

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

above :: (?above :: q, p :< q) => p Source

This function provides access to components of the state from "above"

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

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 g Source

This function constructs a UTT from a given stateful term homomorphism with the state propagated by the given UTA.

runUpHom :: (Functor f, Functor g) => UpState f q -> QHom f q g -> Term f -> Term g Source

This function applies a given stateful term homomorphism with a state space propagated by the given UTA 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, Functor g) => DownState f q -> QHom f q g -> DownTrans f q g Source

This function constructs a DTT from a given stateful term-- homomorphism with the state propagated by the given DTA.

runDownHom :: (Traversable f, Functor g) => DownState f q -> QHom f q g -> q -> Term f -> Term g Source

This function applies a given stateful term homomorphism with a state space propagated by the given DTA 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 total, deterministic bottom-up tree transducers (UTTs).

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

This function runs the given UTT on the given term.

compUpTrans :: (Functor f, Functor g, Functor h) => UpTrans g p h -> UpTrans f q g -> UpTrans f (q, p) h Source

This function composes two UTTs. (see TATA, Theorem 6.4.5)

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

This combinator composes a homomorphism followed by a UTT.

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

This combinator composes a UTT followed by a homomorphism.

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

This combinator composes a signature function followed by a UTT.

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

This combinator composes a UTT followed by a signature function.

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

This function composes a UTT with an algebra.

# Deterministic Bottom-Up Tree State Transformations

## Monolithic State

type UpState f q = Alg f q Source

This type represents transition functions of total, deterministic bottom-up tree acceptors (UTAs).

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

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

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

This combinator runs the given UTA 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 UTA of the two given UTAs.

## Modular State

type DUpState f p q = forall a. (?below :: a -> p, ?above :: p, q :< p) => f a -> q Source

This type represents transition functions of generalised deterministic bottom-up tree acceptors (GUTAs) which have access to an extended state space.

dUpState :: Functor f => UpState f q -> DUpState f p q Source

This combinator turns an arbitrary UTA into a GUTA.

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

This combinator turns a GUTA with the smallest possible state space into a UTA.

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

This combinator runs a GUTA 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 GUTA.

# Deterministic Top-Down Tree Transducers

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

This type represents transition functions of total deterministic top-down tree transducers (DTTs).

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

mkDownTrans :: Functor f => DownTrans' f q g -> DownTrans f q g Source

This function turns a DTT defined using the type `DownTrans'`

in
to the canonical form of type `DownTrans`

.

runDownTrans :: (Functor f, Functor g) => DownTrans f q g -> q -> Cxt h f a -> Cxt h g a Source

Thsis function runs the given DTT on the given tree.

compDownTrans :: (Functor f, Functor g, Functor h) => DownTrans g p h -> DownTrans f q g -> DownTrans f (q, p) h Source

This function composes two DTTs. (see W.C. Rounds /Mappings and grammars on trees/, Theorem 2.)

compDownTransSig :: DownTrans g q h -> SigFun f g -> DownTrans f q h Source

This function composes a DTT after a function.

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

This function composes a signature function after a DTT.

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

This function composes a DTT after a homomorphism.

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

This function composes a homomorphism after a DTT.

# Deterministic Top-Down Tree State Transformations

## Monolithic State

type DownState f q = forall a. Ord a => (q, f a) -> Map a q Source

This type represents transition functions of total, deterministic top-down tree acceptors (DTAs).

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

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

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

This function constructs the product DTA of the given two DTAs.

## Modular State

type DDownState f p q = forall i. (Ord i, ?below :: i -> p, ?above :: p, q :< p) => f i -> Map i q Source

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

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

This combinator turns an arbitrary DTA into a GDTA.

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

This combinator turns a GDTA with the smallest possible state space into a DTA.

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

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