compdata-0.1: Compositional Data Types

Portabilitynon-portable (GHC Extensions)
Stabilityexperimental
MaintainerPatrick Bahr <paba@diku.dk>

Data.Comp.Automata

Description

This module defines tree automata based on compositional data types.

Synopsis

Documentation

type DUTATrans f q = Alg f qSource

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

data DUTA f q Source

This data type represents deterministic bottom-up tree acceptors (DUTAs).

Constructors

DUTA 

Fields

dutaTrans :: DUTATrans f q
 
dutaAccept :: q -> Bool
 

runDUTATrans :: Functor f => DUTATrans f q -> Term f -> qSource

This function runs the transition function of a DUTA on the given term.

duta :: Functor f => DUTA f q -> Term f -> BoolSource

This function checks whether a given DUTA accepts a term.

type NUTATrans f q = AlgM [] f qSource

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

data NUTA f q Source

This type represents non-deterministic bottom-up tree acceptors.

Constructors

NUTA 

Fields

nutaTrans :: AlgM [] f q
 
nutaAccept :: q -> Bool
 

runNUTATrans :: Traversable f => NUTATrans f q -> Term f -> [q]Source

This function runs the given transition function of a NUTA on the given term

nuta :: Traversable f => NUTA f q -> Term f -> BoolSource

This function checks whether a given NUTA accepts a term.

determNUTA :: Traversable f => NUTA f q -> DUTA f [q]Source

This function determinises the given NUTA.

type DUTTTrans f g q = forall a. f (q, a) -> (q, Cxt Hole g a)Source

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

duttTransAlg :: (Functor f, Functor g) => DUTTTrans f g q -> Alg f (q, Term g)Source

This function transforms a DUTT transition function into an algebra.

runDUTTTrans :: (Functor f, Functor g) => DUTTTrans f g q -> Term f -> (q, Term g)Source

This function runs the given DUTT transition function on the given term.

data DUTT f g q Source

This data type represents deterministic bottom-up tree transducers.

Constructors

DUTT 

Fields

duttTrans :: DUTTTrans f g q
 
duttAccept :: q -> Bool
 

dutt :: (Functor f, Functor g) => DUTT f g q -> Term f -> Maybe (Term g)Source

This function transforms the given term according to the given DUTT and returns the resulting term provided it is accepted by the DUTT.

type NUTTTrans f g q = forall a. f (q, a) -> [(q, Cxt Hole g a)]Source

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

nuttTransAlg :: (Functor f, Functor g) => NUTTTrans f g q -> AlgM [] f (q, Term g)Source

This function transforms a NUTT transition function into a monadic algebra.

runNUTTTrans :: (Traversable f, Functor g) => NUTTTrans f g q -> Term f -> [(q, Term g)]Source

This function runs the given NUTT transition function on the given term.

data NUTT f g q Source

This data type represents non-deterministic bottom-up tree transducers (NUTTs).

Constructors

NUTT 

Fields

nuttTrans :: NUTTTrans f g q
 
nuttAccept :: q -> Bool
 

nutt :: (Traversable f, Functor g) => NUTT f g q -> Term f -> [Term g]Source

This function transforms the given term according to the given NUTT and returns a list containing all accepted results.