compdata-0.6: Compositional Data Types

Portability non-portable (GHC Extensions) experimental Tom Hvitved Safe-Infered

Data.Comp.Param.Algebra

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.