compdata-0.6: Compositional Data Types

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

Data.Comp.MultiParam.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. HDifunctor 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. HDifunctor f => Alg f a -> Term f :-> aSource

Construct a catamorphism from the given algebra.

cata' :: HDifunctor 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 :: HDifunctor f => Cxt Hole f a (Cxt h f a b) :-> Cxt h f a bSource

This function applies a whole context into another context.

type AlgM m f a = NatM m (f a a) aSource

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

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

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

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

type AlgM' m f a = NatM m (f a (Compose m a)) aSource

This type represents a monadic algebra, but where the covariant argument is also a monadic computation.

newtype Compose f g a

Right-to-left composition of functors. The composition of applicative functors is always applicative, but the composition of monads is not always a monad.

Constructors

 Compose FieldsgetCompose :: f (g a)

Instances

 (Functor f, Functor g) => Functor (Compose f g) (Applicative f, Applicative g) => Applicative (Compose f g) (Foldable f, Foldable g) => Foldable (Compose f g) (Traversable f, Traversable g) => Traversable (Compose f g) (Alternative f, Applicative g) => Alternative (Compose f g)

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

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

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

# Term Homomorphisms

type CxtFun f g = forall h. SigFun (Cxt h f) (Cxt h g)Source

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. (HDifunctor f, HDifunctor g) => Hom f g -> CxtFun f gSource

Apply a term homomorphism recursively to a term/context.

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

Apply a term homomorphism recursively to a term/context. This is a top-down variant of `appHom`.

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

Compose two term homomorphisms.

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

This function applies a signature function to the given context.

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

This function applies a signature function to the given context.

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

This function composes two signature functions.

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

Lifts the given signature function to the canonical term homomorphism.

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

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

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. NatM m (f a b) (g a b)Source

This type represents a monadic signature function.

type HomM m f g = SigFunM m f (Cxt Hole g)Source

This type represents a monadic term homomorphism.

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.

hom' :: (HDifunctor f, HDifunctor g, Monad m) => SigFunM m f g -> HomM m f gSource

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

Apply a monadic term homomorphism recursively to a term/context.

appTHomM :: (HDitraversable f, Monad m, ParamFunctor m, HDifunctor g) => HomM m f g -> Term f i -> m (Term g i)Source

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

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

Apply a monadic term homomorphism recursively to a term/context. This is a top-down variant of `appHomM`.

appTHomM' :: (HDitraversable g, Monad m, ParamFunctor m, HDifunctor g) => HomM m f g -> Term f i -> m (Term g i)Source

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

homM :: (HDifunctor g, Monad m) => SigFun f g -> HomM m f gSource

Lift the given signature function to a monadic term homomorphism.

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

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

appTSigFunM :: (HDitraversable f, Monad m, ParamFunctor m, HDifunctor g) => SigFunM m f g -> Term f i -> m (Term g i)Source

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

appSigFunM' :: forall m f g. (HDitraversable 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' :: (HDitraversable g, Monad m, ParamFunctor m, HDifunctor g) => SigFunM m f g -> Term f i -> m (Term g i)Source

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

compHomM :: (HDitraversable g, HDifunctor h, Monad m) => HomM m g h -> HomM m f g -> HomM m f hSource