compdata-0.12: Compositional Data Types

Copyright (c) 2010-2011 Patrick Bahr Tom Hvitved BSD3 Patrick Bahr experimental non-portable (GHC Extensions) None Haskell98

Data.Comp.Algebra

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.

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 #

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.

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 #

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 #

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 #

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 #

# 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 #

# 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 #

# 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 #

# 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 #