compdata-0.3: Compositional Data Types

Portabilitynon-portable (GHC Extensions)
Stabilityexperimental
MaintainerPatrick Bahr <paba@diku.dk>

Data.Comp.Multi.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. All definitions are generalised versions of those in Data.Comp.Algebra.

Synopsis

Algebras & Catamorphisms

type Alg f e = f e :-> eSource

This type represents multisorted f-algebras with a family e of carriers.

free :: forall f h a b. HFunctor f => Alg f b -> (a :-> b) -> Cxt h f a :-> bSource

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

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

Construct a catamorphism from the given algebra.

cata' :: HFunctor f => Alg f e -> Cxt h f e :-> eSource

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

appCxt :: HFunctor f => Context f (Cxt h f a) :-> Cxt h f aSource

This function applies a whole context into another context.

Monadic Algebras & Catamorphisms

type AlgM m f e = NatM m (f e) eSource

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

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

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

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

This is a monadic version of cata.

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

liftMAlg :: forall m f. (Monad m, HTraversable f) => Alg f I -> Alg f mSource

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

Term Homomorphisms

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

This type represents context function.

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

This type represents uniform signature function specification.

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

This type represents term homomorphisms.

appTermHom :: forall f g. (HFunctor f, HFunctor g) => TermHom f g -> CxtFun f gSource

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

appTermHom' :: forall f g. HFunctor g => TermHom f g -> CxtFun f gSource

This function applies the given term homomorphism to a term/context. This is the top-down variant of appTermHom.

compTermHom :: (HFunctor g, HFunctor h) => TermHom g h -> TermHom f g -> TermHom f hSource

This function composes two term algebras.

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

This function applies a signature function to the given context.

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

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

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

This function composes two signature functions.

termHom :: HFunctor g => SigFun f g -> TermHom f gSource

Lifts the given signature function to the canonical term homomorphism.

compAlg :: HFunctor g => Alg g a -> TermHom f g -> Alg f aSource

This function composes a term algebra with an algebra.

Monadic Term Homomorphisms

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

This type represents monadic context function.

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

This type represents monadic signature functions.

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

This type represents monadic term algebras.

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

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.

termHom' :: (HFunctor f, HFunctor g, Monad m) => SigFunM m f g -> TermHomM m f gSource

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

appTermHomM :: forall f g m. (HTraversable f, HFunctor g, Monad m) => TermHomM m f g -> CxtFunM m f gSource

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

appTermHomM' :: forall f g m. (HTraversable g, Monad m) => TermHomM m f g -> CxtFunM m f gSource

This function applies the given monadic term homomorphism to the given term/context. This is a top-down variant of appTermHomM.

termHomM :: (HFunctor g, Monad m) => SigFun f g -> TermHomM m f gSource

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

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

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

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

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

compTermHomM :: (HTraversable g, HFunctor h, Monad m) => TermHomM m g h -> TermHomM m f g -> TermHomM m f hSource

This function composes two monadic term algebras.

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

This function composes two monadic signature functions.

compAlgM :: (HTraversable g, Monad m) => AlgM m g a -> TermHomM m f g -> AlgM m f aSource

This function composes a monadic term algebra with a monadic algebra

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

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

Coalgebras & Anamorphisms

type Coalg f a = a :-> f aSource

ana :: forall f a. HFunctor f => Coalg f a -> a :-> Term fSource

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

type CoalgM m f a = NatM m a (f a)Source

anaM :: forall a m f. (HTraversable f, Monad m) => CoalgM m f a -> NatM m a (Term f)Source

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

R-Algebras & Paramorphisms

type RAlg f a = f (Term f :*: a) :-> aSource

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

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

This function constructs a paramorphism from the given r-algebra

type RAlgM m f a = NatM m (f (Term f :*: a)) aSource

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

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

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

R-Coalgebras & Apomorphisms

type RCoalg f a = a :-> f (Term f :+: a)Source

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

apo :: forall f a. HFunctor f => RCoalg f a -> a :-> Term fSource

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

type RCoalgM m f a = NatM m a (f (Term f :+: a))Source

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

apoM :: forall f m a. (HTraversable f, Monad m) => RCoalgM m f a -> NatM m a (Term f)Source

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

CV-Coalgebras & Futumorphisms

type CVCoalg f a = a :-> f (Context f a)Source

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

futu :: forall f a. HFunctor f => CVCoalg f a -> a :-> Term fSource

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

type CVCoalgM m f a = NatM m a (f (Context f a))Source

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

futuM :: forall f a m. (HTraversable f, Monad m) => CVCoalgM m f a -> NatM m a (Term f)Source

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