Data.Comp.MultiParam.Algebra

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

Algebras & Catamorphisms

type Alg f a = f a a :-> a

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 :-> a

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 :-> a

Construct a catamorphism from the given algebra.

cata' :: HDifunctor f => Alg f a -> Cxt h f a a :-> a

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 b

This function applies a whole context into another context.

Monadic Algebras & Catamorphisms

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

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 m a, Monad m) => AlgM m f a -> NatM m b a -> NatM m (Cxt h f a b) a

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 m a, Monad m) => AlgM m f a -> NatM m (Term f) a

Construct a monadic catamorphism from the given monadic algebra.

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

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

Fields

getCompose :: 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) a

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) a

Construct a monadic catamorphism from the given monadic algebra.

Term Homomorphisms

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

This type represents a context function.

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

This type represents a signature function.

type Hom f g = SigFun f (Context g)

This type represents a term homomorphism.

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

Apply a term homomorphism recursively to a term/context.

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

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 h

Compose two term homomorphisms.

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

This function applies a signature function to the given context.

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

This function applies a signature function to the given context.

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

This function composes two signature functions.

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

Lifts the given signature function to the canonical term homomorphism.

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

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

Monadic Term Homomorphisms

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

This type represents a monadic context function.

type SigFunM m f g = forall a b. NatM m (f a b) (g a b)

This type represents a monadic signature function.

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

This type represents a monadic term homomorphism.

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

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 g

Lift the give monadic signature function to a monadic term homomorphism.

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

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

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

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

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

Lift the given signature function to a monadic term homomorphism.

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

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

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

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

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

Compose two monadic term homomorphisms.

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

This function composes two monadic signature functions.

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

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

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

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