compdata-0.7.0.2: Compositional Data Types

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

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

This type represents an algebra over a functor f and carrier a.

free :: forall f h a b. Functor f => Alg f b -> (a -> b) -> Cxt h f a -> b Source

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

cata :: forall f a. Functor f => Alg f a -> Term f -> a Source

Construct a catamorphism from the given algebra.

cata' :: Functor f => Alg f a -> Cxt h f 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 :: Functor f => Context f (Cxt h f a) -> Cxt h f a Source

This function applies a whole context into another context.

Monadic Algebras & Catamorphisms

type AlgM m f a = f a -> m a Source

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

algM :: (Traversable f, Monad m) => AlgM m f a -> Alg f (m a) Source

Convert a monadic algebra into an ordinary algebra with a monadic carrier.

freeM :: forall h f a m b. (Traversable f, Monad m) => AlgM m f b -> (a -> m b) -> Cxt h f a -> m b Source

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

cataM :: forall f m a. (Traversable f, Monad m) => AlgM m f a -> Term f -> m a Source

Construct a monadic catamorphism from the given monadic algebra.

cataM' :: forall h f a m. (Traversable f, Monad m) => AlgM m f a -> Cxt h f a -> m a Source

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

Term Homomorphisms

type CxtFun f g = forall a h. Cxt h f a -> Cxt h g a Source

This type represents a context function.

type SigFun f g = forall a. f a -> g a 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. (Functor f, Functor g) => Hom f g -> CxtFun f g Source

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

appHom' :: forall f g. Functor 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 :: (Functor g, Functor h) => Hom g h -> Hom f g -> Hom f h Source

Compose two term homomorphisms.

appSigFun :: Functor f => SigFun f g -> CxtFun f g Source

This function applies a signature function to the given context.

appSigFun' :: Functor g => SigFun f g -> CxtFun f g Source

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

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

This function composes two signature functions.

compSigFunHom :: Functor g => SigFun g h -> Hom f g -> Hom f h Source

This function composes a signature function with a term homomorphism.

compHomSigFun :: Hom g h -> SigFun f g -> Hom f h Source

This function composes a term homomorphism with a signature function.

compAlgSigFun :: Alg g a -> SigFun f g -> Alg f a Source

This function composes an algebra with a signature function.

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

Lifts the given signature function to the canonical term homomorphism.

compAlg :: Functor g => Alg g a -> Hom f g -> Alg f a Source

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

compCoalg :: Hom f g -> Coalg f a -> CVCoalg' g a Source

Compose a term homomorphism with a coalgebra to get a cv-coalgebra.

compCVCoalg :: (Functor f, Functor g) => Hom f g -> CVCoalg' f a -> CVCoalg' g a Source

Compose a term homomorphism with a cv-coalgebra to get a new cv-coalgebra.

Monadic Term Homomorphisms

type CxtFunM m f g = forall a h. Cxt h f a -> m (Cxt h g a) Source

This type represents a monadic context function.

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

This type represents a monadic signature function.

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

This type represents a monadic term homomorphism.

type SigFunMD m f g = forall a. f (m a) -> m (g a) Source

This type represents a monadic signature function. It is similar to SigFunM but has monadic values also in the domain.

type HomMD m f g = SigFunMD m f (Context g) Source

This type represents a monadic term homomorphism. It is similar to HomM but has monadic values also in the domain.

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' :: (Functor f, Functor 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. (Traversable f, Functor g, Monad m) => HomM m f g -> CxtFunM m f g Source

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

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

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

homM :: (Functor g, Monad m) => SigFunM m f g -> HomM m f g Source

Lift the given signature function to a monadic term homomorphism.

homMD :: forall f g m. (Traversable f, Functor g, Monad m) => HomMD m f g -> CxtFunM m f g Source

This function constructs the unique monadic homomorphism from the initial term algebra to the given term algebra.

appSigFunM :: (Traversable f, Monad m) => SigFunM m f g -> CxtFunM m f g Source

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

appSigFunM' :: (Traversable 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.

appSigFunMD :: forall f g m. (Traversable f, Functor g, Monad m) => SigFunMD m f g -> CxtFunM m f g Source

This function applies a signature function to the given context.

compHomM :: (Traversable g, Functor 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.

compSigFunHomM :: (Traversable g, Functor h, Monad m) => SigFunM m g h -> HomM m f g -> HomM m f h Source

compHomSigFunM :: Monad m => HomM m g h -> SigFunM m f g -> HomM m f h Source

This function composes two monadic signature functions.

compAlgSigFunM :: Monad m => AlgM m g a -> SigFunM m f g -> AlgM m f a Source

This function composes two monadic signature functions.

compAlgM :: (Traversable 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' :: (Traversable 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.

Coalgebras & Anamorphisms

type Coalg f a = a -> f a Source

This type represents a coalgebra over a functor f and carrier a.

ana :: forall a f. Functor f => Coalg f a -> a -> Term f Source

Construct an anamorphism from the given coalgebra.

ana' :: forall a f. Functor f => Coalg f a -> a -> Term f Source

Shortcut fusion variant of ana.

type CoalgM m f a = a -> m (f a) Source

This type represents a monadic coalgebra over a functor f and carrier a.

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

Construct a monadic anamorphism from the given monadic coalgebra.

R-Algebras & Paramorphisms

type RAlg f a = f (Term f, a) -> a Source

This type represents an r-algebra over a functor f and carrier a.

para :: Functor f => RAlg f a -> Term f -> a Source

Construct a paramorphism from the given r-algebra.

type RAlgM m f a = f (Term f, a) -> m a Source

This type represents a monadic r-algebra over a functor f and carrier a.

paraM :: (Traversable f, Monad m) => RAlgM m f a -> Term f -> m a Source

Construct a monadic paramorphism from the given monadic r-algebra.

R-Coalgebras & Apomorphisms

type RCoalg f a = a -> f (Either (Term f) a) Source

This type represents an r-coalgebra over a functor f and carrier a.

apo :: Functor f => RCoalg f a -> a -> Term f Source

Construct an apomorphism from the given r-coalgebra.

type RCoalgM m f a = a -> m (f (Either (Term f) a)) Source

This type represents a monadic r-coalgebra over a functor f and carrier a.

apoM :: (Traversable f, Monad m) => RCoalgM m f a -> a -> m (Term f) Source

Construct a monadic apomorphism from the given monadic r-coalgebra.

CV-Algebras & Histomorphisms

type CVAlg f a f' = f (Term f') -> a Source

This type represents a cv-algebra over a functor f and carrier a.

histo :: (Functor f, DistAnn f a f') => CVAlg f a f' -> Term f -> a Source

Construct a histomorphism from the given cv-algebra.

type CVAlgM m f a f' = f (Term f') -> m a Source

This type represents a monadic cv-algebra over a functor f and carrier a.

histoM :: (Traversable f, Monad m, DistAnn f a f') => CVAlgM m f a f' -> Term f -> m a Source

Construct a monadic histomorphism from the given monadic cv-algebra.

CV-Coalgebras & Futumorphisms

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

This type represents a cv-coalgebra over a functor f and carrier a.

futu :: forall f a. Functor f => CVCoalg f a -> a -> Term f Source

Construct a futumorphism from the given cv-coalgebra.

type CVCoalg' f a = a -> Context f a Source

This type represents a generalised cv-coalgebra over a functor f and carrier a.

futu' :: forall f a. Functor f => CVCoalg' f a -> a -> Term f Source

Construct a futumorphism from the given generalised cv-coalgebra.

type CVCoalgM m f a = a -> m (f (Context f a)) Source

This type represents a monadic cv-coalgebra over a functor f and carrier a.

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

Construct a monadic futumorphism from the given monadic cv-coalgebra.