Data.Comp.Multi.Algebra

This module defines the notion of algebras and catamorphisms, and their generalizations to e.g. monadic versions and other (co)recursion schemes. All definitions are generalised versions of those in Data.Comp.Algebra.

Algebras & Catamorphisms

type HAlg f e = f e :-> e

hfree :: forall f h a b. HFunctor f => HAlg f b -> (a :-> b) -> HCxt h f a :-> b

hcata :: forall f a. HFunctor f => HAlg f a -> HTerm f :-> a

hcata' :: HFunctor f => HAlg f e -> HCxt h f e :-> e

appHCxt :: HFunctor f => HContext f (HCxt h f a) :-> HCxt h f a

This function applies a whole context into another context.

Monadic Algebras & Catamorphisms

type HAlgM m f e = NatM m (f e) e

hfreeM :: forall f m h a b. (HTraversable f, Monad m) => HAlgM m f b -> NatM m a b -> NatM m (HCxt h f a) b

hcataM :: forall f m a. (HTraversable f, Monad m) => HAlgM m f a -> NatM m (HTerm f) a

This is a monadic version of hcata.

hcataM' :: forall m h a f. (Monad m, HTraversable f) => HAlgM m f a -> NatM m (HCxt h f a) a

liftMHAlg :: forall m f. (Monad m, HTraversable f) => HAlg f I -> HAlg f m

This function lifts a many-sorted algebra to a monadic domain.

Term Homomorphisms

type HCxtFun f g = forall a h. HCxt h f a :-> HCxt h g a

This type represents context function.

type HSigFun f g = forall a. f a :-> g a

This type represents uniform signature function specification.

type HTermHom f g = HSigFun f (HContext g)

This type represents a term algebra.

appHTermHom :: (HFunctor f, HFunctor g) => HTermHom f g -> HCxtFun f g

This function applies the given term homomorphism to a term/context.

compHTermHom :: (HFunctor g, HFunctor h) => HTermHom g h -> HTermHom f g -> HTermHom f h

This function composes two term algebras.

appHSigFun :: (HFunctor f, HFunctor g) => HSigFun f g -> HCxtFun f g

This function applies a signature function to the given context.

compHSigFun :: HSigFun g h -> HSigFun f g -> HSigFun f h

This function composes two signature functions.

htermHom :: HFunctor g => HSigFun f g -> HTermHom f g

Lifts the given signature function to the canonical term homomorphism.

compHAlg :: HFunctor g => HAlg g a -> HTermHom f g -> HAlg f a

This function composes a term algebra with an algebra.

Monadic Term Homomorphisms

type HCxtFunM m f g = forall a h. NatM m (HCxt h f a) (HCxt h g a)

This type represents monadic context function.

type HSigFunM m f g = forall a. NatM m (f a) (g a)

This type represents monadic signature functions.

type HTermHomM m f g = HSigFunM m f (HContext g)

This type represents monadic term algebras.

hsigFunM :: Monad m => HSigFun f g -> HSigFunM m f g

This function lifts the given signature function to a monadic signature function. Note that term algebras are instances of signature functions. Hence this function also applies to term algebras.

appHTermHomM :: forall f g m. (HTraversable f, HFunctor g, Monad m) => HTermHomM m f g -> HCxtFunM m f g

This function applies the given monadic term homomorphism to the given term/context.

htermHomM :: (HFunctor g, Monad m) => HSigFun f g -> HTermHomM m f g

This function lifts the given signature function to a monadic term algebra.

appHSigFunM :: (HTraversable f, HFunctor g, Monad m) => HSigFunM m f g -> HCxtFunM m f g

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

compHTermHomM :: (HTraversable g, HFunctor h, Monad m) => HTermHomM m g h -> HTermHomM m f g -> HTermHomM m f h

This function composes two monadic term algebras.

compHSigFunM :: Monad m => HSigFunM m g h -> HSigFunM m f g -> HSigFunM m f h

This function composes two monadic signature functions.

compHAlgM :: (HTraversable g, Monad m) => HAlgM m g a -> HTermHomM m f g -> HAlgM m f a

This function composes a monadic term algebra with a monadic algebra

compHAlgM' :: (HTraversable g, Monad m) => HAlgM m g a -> HTermHom f g -> HAlgM m f a

This function composes a monadic term algebra with a monadic algebra.

Coalgebras & Anamorphisms

type HCoalg f a = a :-> f a

hana :: forall f a. HFunctor f => HCoalg f a -> a :-> HTerm f

This function unfolds the given value to a term using the given unravelling function. This is the unique homomorphism a -> HTerm f from the given coalgebra of type a -> f a to the final coalgebra HTerm f.

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

hanaM :: forall a m f. (HTraversable f, Monad m) => HCoalgM m f a -> NatM m a (HTerm f)

This function unfolds the given value to a term using the given monadic unravelling function. This is the unique homomorphism a -> HTerm f from the given coalgebra of type a -> f a to the final coalgebra HTerm f.

R-Algebras & Paramorphisms

type HRAlg f a = f (HTerm f :*: a) :-> a

This type represents r-algebras over functor f and with domain a.

hpara :: forall f a. HFunctor f => HRAlg f a -> HTerm f :-> a

This function constructs a paramorphism from the given r-algebra

type HRAlgM m f a = NatM m (f (HTerm f :*: a)) a

This type represents monadic r-algebras over monad m and functor f and with domain a.

hparaM :: forall f m a. (HTraversable f, Monad m) => HRAlgM m f a -> NatM m (HTerm f) a

This function constructs a monadic paramorphism from the given monadic r-algebra

R-Coalgebras & Apomorphisms

type HRCoalg f a = a :-> f (HTerm f :+: a)

This type represents r-coalgebras over functor f and with domain a.

hapo :: forall f a. HFunctor f => HRCoalg f a -> a :-> HTerm f

This function constructs an apomorphism from the given r-coalgebra.

type HRCoalgM m f a = NatM m a (f (HTerm f :+: a))

This type represents monadic r-coalgebras over monad m and functor f with domain a.

hapoM :: forall f m a. (HTraversable f, Monad m) => HRCoalgM m f a -> NatM m a (HTerm f)

This function constructs a monadic apomorphism from the given monadic r-coalgebra.

CV-Algebras & Histomorphisms

For this to work we need a more general version of :&&: which is of kind ((* -> *) -> * -> *) -> (* -> *) -> (* -> *) -> * -> *, i.e. one which takes a functor as second argument instead of a type.

CV-Coalgebras & Futumorphisms

type HCVCoalg f a = a :-> f (HContext f a)

This type represents cv-coalgebras over functor f and with domain a.

hfutu :: forall f a. HFunctor f => HCVCoalg f a -> a :-> HTerm f

This function constructs the unique futumorphism from the given cv-coalgebra to the term algebra.

type HCVCoalgM m f a = NatM m a (f (HContext f a))

This type represents monadic cv-coalgebras over monad m and functor f, and with domain a.

hfutuM :: forall f a m. (HTraversable f, Monad m) => HCVCoalgM m f a -> NatM m a (HTerm f)

This function constructs the unique monadic futumorphism from the given monadic cv-coalgebra to the term algebra.

Exponential Functors

appHTermHomE :: forall f g. (HExpFunctor f, HExpFunctor g) => HTermHom f g -> HTerm f :-> HTerm g

Variant of appHTermHom for term homomorphisms from and to HExpFunctor signatures.

hcataE :: forall f a. HExpFunctor f => HAlg f a -> HTerm f :-> a

Catamorphism for higher-order exponential functors.

appHCxtE :: HExpFunctor f => HContext f (HCxt h f a) :-> HCxt h f a

Variant of appHCxt for contexts over HExpFunctor signatures.