compdata-0.7.0.2: Compositional Data Types

Copyright(c) 2011 Patrick Bahr, Tom Hvitved
LicenseBSD3
MaintainerTom Hvitved <hvitved@diku.dk>
Stabilityexperimental
Portabilitynon-portable (GHC Extensions)
Safe HaskellNone
LanguageHaskell98

Data.Comp.MultiParam.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.

Synopsis

Algebras & Catamorphisms

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

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 Source

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 Source

Construct a catamorphism from the given algebra.

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

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 Source

This function applies a whole context into another context.

Monadic Algebras & Catamorphisms

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

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

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

Construct a monadic catamorphism from the given monadic algebra.

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

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)
 

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 Source

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 Source

Construct a monadic catamorphism from the given monadic algebra.

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 b Source

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 g Source

Apply a term homomorphism recursively to a term/context.

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

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 Source

Compose two term homomorphisms.

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

This function applies a signature function to the given context.

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

This function applies a signature function to the given context.

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

This function composes two signature functions.

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

Lifts the given signature function to the canonical term homomorphism.

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

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) 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 g Source

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 Source

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

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

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 g Source

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 g Source

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 g Source

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 g Source

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 h Source

Compose two monadic term homomorphisms.

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

This function composes two monadic signature functions.

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

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

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

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