compdata-0.6: Compositional Data Types

Portabilitynon-portable (GHC Extensions)
Stabilityexperimental
MaintainerTom Hvitved <hvitved@diku.dk>
Safe HaskellSafe-Infered

Data.Comp.Param.Algebra

Contents

Description

This module defines the notion of algebras and catamorphisms, and their generalizations to e.g. monadic versions and other (co)recursion schemes.

Synopsis

Algebras & Catamorphisms

type Alg f a = f a a -> aSource

This type represents an algebra over a difunctor f and carrier a.

free :: forall h f a b. Difunctor f => Alg f a -> (b -> a) -> Cxt h f a b -> aSource

Construct a catamorphism for contexts over f with holes of type b, from the given algebra.

cata :: forall f a. Difunctor f => Alg f a -> Term f -> aSource

Construct a catamorphism from the given algebra.

cata' :: Difunctor f => Alg f a -> Cxt h f a a -> aSource

A generalisation of cata from terms over f to contexts over f, where the holes have the type of the algebra carrier.

appCxt :: Difunctor f => Context f a (Cxt h f a b) -> Cxt h f a bSource

This function applies a whole context into another context.

Monadic Algebras & Catamorphisms

type AlgM m f a = f a a -> m aSource

This type represents a monadic algebra. It is similar to Alg but the return type is monadic.

algM :: (Ditraversable f, Monad m) => AlgM m f a -> Alg f (m a)Source

Convert a monadic algebra into an ordinary algebra with a monadic carrier.

freeM :: forall m h f a b. (Ditraversable f, Monad m) => AlgM m f a -> (b -> m a) -> Cxt h f a b -> m aSource

Construct a monadic catamorphism for contexts over f with holes of type b, from the given monadic algebra.

cataM :: forall m f a. (Ditraversable f, Monad m) => AlgM m f a -> Term f -> m aSource

Construct a monadic catamorphism from the given monadic algebra.

cataM' :: forall m h f a. (Ditraversable f, Monad m) => AlgM m f a -> Cxt h f a (m a) -> m aSource

A generalisation of cataM from terms over f to contexts over f, where the holes have the type of the monadic algebra carrier.

Term Homomorphisms

type CxtFun f g = forall h a b. Cxt h f a b -> Cxt h g a bSource

This type represents a context function.

type SigFun f g = forall a b. f a b -> g a bSource

This type represents a signature function.

type Hom f g = SigFun f (Context g)Source

This type represents a term homomorphism.

appHom :: forall f g. (Difunctor f, Difunctor g) => Hom f g -> CxtFun f gSource

Apply a term homomorphism recursively to a term/context.

appHom' :: forall f g. Difunctor g => Hom f g -> CxtFun f gSource

Apply a term homomorphism recursively to a term/context.

compHom :: (Difunctor g, Difunctor h) => Hom g h -> Hom f g -> Hom f hSource

Compose two term homomorphisms.

appSigFun :: forall f g. Difunctor f => SigFun f g -> CxtFun f gSource

This function applies a signature function to the given context.

appSigFun' :: forall f g. Difunctor g => SigFun f g -> CxtFun f gSource

This function applies a signature function to the given context. This is a top-bottom variant of appSigFun.

compSigFun :: SigFun g h -> SigFun f g -> SigFun f hSource

This function composes two signature functions.

compHomSigFun :: Hom g h -> SigFun f g -> Hom f hSource

This function composes a term homomorphism and a signature function.

compSigFunHom :: Difunctor g => SigFun g h -> Hom f g -> Hom f hSource

This function composes a term homomorphism and a signature function.

hom :: Difunctor g => SigFun f g -> Hom f gSource

Lifts the given signature function to the canonical term homomorphism.

compAlg :: (Difunctor f, Difunctor g) => Alg g a -> Hom f g -> Alg f aSource

Compose an algebra with a term homomorphism to get a new algebra.

compAlgSigFun :: Alg g a -> SigFun f g -> Alg f aSource

Monadic Term Homomorphisms

type CxtFunM m f g = forall h. SigFunM m (Cxt h f) (Cxt h g)Source

This type represents a monadic context function.

type SigFunM m f g = forall a b. f a b -> m (g a b)Source

This type represents a monadic signature function.

type HomM m f g = SigFunM m f (Context g)Source

This type represents a monadic term homomorphism.

type SigFunMD m f g = forall a b. f a (m b) -> m (g a b)Source

This type represents a monadic signature function. It is similar to SigFunM but has monadic values also in the domain.

type HomMD m f g = SigFunMD m f (Context g)Source

This type represents a monadic term homomorphism. It is similar to HomM but has monadic values also in the domain.

sigFunM :: Monad m => SigFun f g -> SigFunM m f gSource

Lift the given signature function to a monadic signature function. Note that term homomorphisms are instances of signature functions. Hence this function also applies to term homomorphisms.

appHomM :: forall f g m. (Ditraversable f, Difunctor g, Monad m) => HomM m f g -> CxtFunM m f gSource

Apply a monadic term homomorphism recursively to a term/context. The monad is sequenced bottom-up.

appTHomM :: (Ditraversable f, ParamFunctor m, Monad m, Difunctor g) => HomM m f g -> Term f -> m (Term g)Source

A restricted form of |appHomM| which only works for terms.

appHomM' :: forall f g m. (Ditraversable g, Monad m) => HomM m f g -> CxtFunM m f gSource

Apply a monadic term homomorphism recursively to a term/context. The monad is sequence top-down.

appTHomM' :: (Ditraversable g, ParamFunctor m, Monad m, Difunctor g) => HomM m f g -> Term f -> m (Term g)Source

A restricted form of |appHomM'| which only works for terms.

homM :: (Difunctor g, Monad m) => SigFunM m f g -> HomM m f gSource

Lift the given signature function to a monadic term homomorphism.

homMD :: forall f g m. (Difunctor f, Difunctor g, Monad m) => HomMD m f g -> CxtFunM m f gSource

This function constructs the unique monadic homomorphism from the initial term algebra to the given term algebra.

appSigFunM :: forall m f g. (Ditraversable f, Monad m) => SigFunM m f g -> CxtFunM m f gSource

This function applies a monadic signature function to the given context.

appTSigFunM :: (Ditraversable f, ParamFunctor m, Monad m, Difunctor g) => SigFunM m f g -> Term f -> m (Term g)Source

A restricted form of |appSigFunM| which only works for terms.

appSigFunM' :: forall m f g. (Ditraversable g, Monad m) => SigFunM m f g -> CxtFunM m f gSource

This function applies a monadic signature function to the given context. This is a 'top-down variant of appSigFunM.

appTSigFunM' :: (Ditraversable g, ParamFunctor m, Monad m, Difunctor g) => SigFunM m f g -> Term f -> m (Term g)Source

A restricted form of |appSigFunM'| which only works for terms.

appSigFunMD :: forall f g m. (Ditraversable f, Difunctor g, Monad m) => SigFunMD m f g -> CxtFunM m f gSource

This function applies a signature function to the given context.

appTSigFunMD :: (Ditraversable f, ParamFunctor m, Monad m, Difunctor g) => SigFunMD m f g -> Term f -> m (Term g)Source

A restricted form of |appSigFunMD| which only works for terms.

compHomM :: (Ditraversable g, Difunctor h, Monad m) => HomM m g h -> HomM m f g -> HomM m f hSource

Compose two monadic term homomorphisms.

compHomM' :: (Ditraversable h, Monad m) => HomM m g h -> HomM m f g -> HomM m f hSource

Compose two monadic term homomorphisms.

compSigFunM :: Monad m => SigFunM m g h -> SigFunM m f g -> SigFunM m f hSource

This function composes two monadic signature functions.

compSigFunHomM :: (Ditraversable g, Monad m) => SigFunM m g h -> HomM m f g -> HomM m f hSource

Compose two monadic term homomorphisms.

compSigFunHomM' :: (Ditraversable h, Monad m) => SigFunM m g h -> HomM m f g -> HomM m f hSource

Compose two monadic term homomorphisms.

compAlgSigFunM :: Monad m => AlgM m g a -> SigFunM m f g -> AlgM m f aSource

Compose a monadic algebra with a monadic signature function to get a new monadic algebra.

compAlgSigFunM' :: AlgM m g a -> SigFun f g -> AlgM m f aSource

Compose a monadic algebra with a signature function to get a new monadic algebra.

compAlgM :: (Ditraversable g, Monad m) => AlgM m g a -> HomM m f g -> AlgM m f aSource

Compose a monadic algebra with a monadic term homomorphism to get a new monadic algebra.

compAlgM' :: (Ditraversable g, Monad m) => AlgM m g a -> Hom f g -> AlgM m f aSource

Compose a monadic algebra with a term homomorphism to get a new monadic algebra.

Coalgebras & Anamorphisms

type Coalg f a = forall b. a -> [(a, b)] -> Either b (f b (a, [(a, b)]))Source

This type represents a coalgebra over a difunctor f and carrier a. The list of (a,b)s represent the parameters that may occur in the constructed value. The first component represents the seed of the parameter, and the second component is the (polymorphic) parameter itself. If f is itself a binder, then the parameters bound by f can be passed to the covariant argument, thereby making them available to sub terms.

ana :: Difunctor f => Coalg f a -> a -> Term fSource

Construct an anamorphism from the given coalgebra.

type CoalgM m f a = forall b. a -> [(a, b)] -> m (Either b (f b (a, [(a, b)])))Source

This type represents a monadic coalgebra over a difunctor f and carrier a.

anaM :: forall a m f. (Ditraversable f, Monad m) => CoalgM m f a -> a -> forall a. m (Trm f a)Source

Construct a monadic anamorphism from the given monadic coalgebra.

R-Algebras & Paramorphisms

type RAlg f a = f a (Trm f a, a) -> aSource

This type represents an r-algebra over a difunctor f and carrier a.

para :: forall f a. Difunctor f => RAlg f a -> Term f -> aSource

Construct a paramorphism from the given r-algebra.

type RAlgM m f a = f a (Trm f a, a) -> m aSource

This type represents a monadic r-algebra over a difunctor f and carrier a.

paraM :: forall m f a. (Ditraversable f, Monad m) => RAlgM m f a -> Term f -> m aSource

Construct a monadic paramorphism from the given monadic r-algebra.

R-Coalgebras & Apomorphisms

type RCoalg f a = forall b. a -> [(a, b)] -> Either b (f b (Either (Trm f b) (a, [(a, b)])))Source

This type represents an r-coalgebra over a difunctor f and carrier a.

apo :: Difunctor f => RCoalg f a -> a -> Term fSource

Construct an apomorphism from the given r-coalgebra.

type RCoalgM m f a = forall b. a -> [(a, b)] -> m (Either b (f b (Either (Trm f b) (a, [(a, b)]))))Source

This type represents a monadic r-coalgebra over a functor f and carrier a.

apoM :: forall f m a. (Ditraversable f, Monad m) => RCoalgM m f a -> a -> forall a. m (Trm f a)Source

Construct a monadic apomorphism from the given monadic r-coalgebra.

CV-Algebras & Histomorphisms

type CVAlg f a f' = f a (Trm f' a) -> aSource

This type represents a cv-algebra over a difunctor f and carrier a.

histo :: forall f f' a. (Difunctor f, DistAnn f a f') => CVAlg f a f' -> Term f -> aSource

Construct a histomorphism from the given cv-algebra.

type CVAlgM m f a f' = f a (Trm f' a) -> m aSource

This type represents a monadic cv-algebra over a functor f and carrier a.

histoM :: forall f f' m a. (Ditraversable f, Monad m, DistAnn f a f') => CVAlgM m f a f' -> Term f -> m aSource

Construct a monadic histomorphism from the given monadic cv-algebra.

CV-Coalgebras & Futumorphisms

type CVCoalg f a = forall b. a -> [(a, b)] -> Either b (f b (Context f b (a, [(a, b)])))Source

This type represents a cv-coalgebra over a difunctor f and carrier a. The list of (a,b)s represent the parameters that may occur in the constructed value. The first component represents the seed of the parameter, and the second component is the (polymorphic) parameter itself. If f is itself a binder, then the parameters bound by f can be passed to the covariant argument, thereby making them available to sub terms.

futu :: Difunctor f => CVCoalg f a -> a -> Term fSource

Construct a futumorphism from the given cv-coalgebra.

type CVCoalg' f a = forall b. a -> [(a, b)] -> Context f b (a, [(a, b)])Source

This type represents a generalised cv-coalgebra over a difunctor f and carrier a.

futu' :: Difunctor f => CVCoalg' f a -> a -> Term fSource

Construct a futumorphism from the given generalised cv-coalgebra.

type CVCoalgM m f a = forall b. a -> [(a, b)] -> m (Either b (f b (Context f b (a, [(a, b)]))))Source

This type represents a monadic cv-coalgebra over a difunctor f and carrier a.

futuM :: forall f a m. (Ditraversable f, Monad m) => CVCoalgM m f a -> a -> forall a. m (Trm f a)Source

Construct a monadic futumorphism from the given monadic cv-coalgebra.