| Copyright | (c) 2010-2011 Patrick Bahr Tom Hvitved |
|---|---|
| License | BSD3 |
| Maintainer | Patrick Bahr <[email protected]> |
| Stability | experimental |
| Portability | non-portable (GHC Extensions) |
| Safe Haskell | None |
| Language | Haskell2010 |
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
- type Alg (f :: Type -> Type) a = f a -> a
- free :: forall f h a b. Functor f => Alg f b -> (a -> b) -> Cxt h f a -> b
- cata :: Functor f => Alg f a -> Term f -> a
- cata' :: Functor f => Alg f a -> Cxt h f a -> a
- appCxt :: forall (f :: Type -> Type) h a. Functor f => Context f (Cxt h f a) -> Cxt h f a
- type AlgM (m :: Type -> Type) (f :: Type -> Type) a = f a -> m a
- algM :: (Traversable f, Monad m) => AlgM m f a -> Alg f (m a)
- freeM :: forall h f a m b. (Traversable f, Monad m) => AlgM m f b -> (a -> m b) -> Cxt h f a -> m b
- cataM :: (Traversable f, Monad m) => AlgM m f a -> Term f -> m a
- cataM' :: forall h f a m. (Traversable f, Monad m) => AlgM m f a -> Cxt h f a -> m a
- type CxtFun (f :: Type -> Type) (g :: Type -> Type) = forall a h. Cxt h f a -> Cxt h g a
- type SigFun (f :: Type -> Type) (g :: Type -> Type) = forall a. f a -> g a
- type Hom (f :: Type -> Type) (g :: Type -> Type) = SigFun f (Context g)
- appHom :: forall (f :: Type -> Type) (g :: Type -> Type). (Functor f, Functor g) => Hom f g -> CxtFun f g
- appHom' :: forall (f :: Type -> Type) (g :: Type -> Type). Functor g => Hom f g -> CxtFun f g
- compHom :: forall (g :: Type -> Type) (h :: Type -> Type) (f :: Type -> Type). (Functor g, Functor h) => Hom g h -> Hom f g -> Hom f h
- appSigFun :: forall (f :: Type -> Type) (g :: Type -> Type). Functor f => SigFun f g -> CxtFun f g
- appSigFun' :: forall (g :: Type -> Type) (f :: Type -> Type). Functor g => SigFun f g -> CxtFun f g
- compSigFun :: forall (g :: Type -> Type) (h :: Type -> Type) (f :: Type -> Type). SigFun g h -> SigFun f g -> SigFun f h
- compSigFunHom :: forall (g :: Type -> Type) (h :: Type -> Type) (f :: Type -> Type). Functor g => SigFun g h -> Hom f g -> Hom f h
- compHomSigFun :: forall (g :: Type -> Type) (h :: Type -> Type) (f :: Type -> Type). Hom g h -> SigFun f g -> Hom f h
- compAlgSigFun :: Alg g a -> SigFun f g -> Alg f a
- hom :: forall (g :: Type -> Type) (f :: Type -> Type). Functor g => SigFun f g -> Hom f g
- compAlg :: Functor g => Alg g a -> Hom f g -> Alg f a
- compCoalg :: forall f (g :: Type -> Type) a. Hom f g -> Coalg f a -> CVCoalg' g a
- compCVCoalg :: forall (f :: Type -> Type) (g :: Type -> Type) a. (Functor f, Functor g) => Hom f g -> CVCoalg' f a -> CVCoalg' g a
- type CxtFunM (m :: Type -> Type) (f :: Type -> Type) (g :: Type -> Type) = forall a h. Cxt h f a -> m (Cxt h g a)
- type SigFunM (m :: Type -> Type) (f :: Type -> Type) (g :: Type -> Type) = forall a. f a -> m (g a)
- type HomM (m :: Type -> Type) (f :: Type -> Type) (g :: Type -> Type) = SigFunM m f (Context g)
- type SigFunMD (m :: Type -> Type) (f :: Type -> Type) (g :: Type -> Type) = forall a. f (m a) -> m (g a)
- type HomMD (m :: Type -> Type) (f :: Type -> Type) (g :: Type -> Type) = SigFunMD m f (Context g)
- sigFunM :: forall (m :: Type -> Type) (f :: Type -> Type) (g :: Type -> Type). Monad m => SigFun f g -> SigFunM m f g
- hom' :: forall (f :: Type -> Type) (g :: Type -> Type) (m :: Type -> Type). (Functor f, Functor g, Monad m) => SigFunM m f g -> HomM m f g
- appHomM :: forall (f :: Type -> Type) (g :: Type -> Type) (m :: Type -> Type). (Traversable f, Functor g, Monad m) => HomM m f g -> CxtFunM m f g
- appHomM' :: forall (f :: Type -> Type) (g :: Type -> Type) (m :: Type -> Type). (Traversable g, Monad m) => HomM m f g -> CxtFunM m f g
- homM :: forall (g :: Type -> Type) (m :: Type -> Type) (f :: Type -> Type). (Functor g, Monad m) => SigFunM m f g -> HomM m f g
- homMD :: forall (f :: Type -> Type) (g :: Type -> Type) (m :: Type -> Type). (Traversable f, Functor g, Monad m) => HomMD m f g -> CxtFunM m f g
- appSigFunM :: forall (f :: Type -> Type) (m :: Type -> Type) (g :: Type -> Type). (Traversable f, Monad m) => SigFunM m f g -> CxtFunM m f g
- appSigFunM' :: forall (g :: Type -> Type) (m :: Type -> Type) (f :: Type -> Type). (Traversable g, Monad m) => SigFunM m f g -> CxtFunM m f g
- appSigFunMD :: forall (f :: Type -> Type) (g :: Type -> Type) (m :: Type -> Type). (Traversable f, Functor g, Monad m) => SigFunMD m f g -> CxtFunM m f g
- compHomM :: forall (g :: Type -> Type) (h :: Type -> Type) (m :: Type -> Type) (f :: Type -> Type). (Traversable g, Functor h, Monad m) => HomM m g h -> HomM m f g -> HomM m f h
- compSigFunM :: forall (m :: Type -> Type) (g :: Type -> Type) (h :: Type -> Type) (f :: Type -> Type). Monad m => SigFunM m g h -> SigFunM m f g -> SigFunM m f h
- compSigFunHomM :: forall (g :: Type -> Type) (h :: Type -> Type) (m :: Type -> Type) (f :: Type -> Type). (Traversable g, Functor h, Monad m) => SigFunM m g h -> HomM m f g -> HomM m f h
- compHomSigFunM :: forall (m :: Type -> Type) (g :: Type -> Type) (h :: Type -> Type) (f :: Type -> Type). Monad m => HomM m g h -> SigFunM m f g -> HomM m f h
- compAlgSigFunM :: Monad m => AlgM m g a -> SigFunM m f g -> AlgM m f a
- compAlgM :: (Traversable g, Monad m) => AlgM m g a -> HomM m f g -> AlgM m f a
- compAlgM' :: (Traversable g, Monad m) => AlgM m g a -> Hom f g -> AlgM m f a
- type Coalg (f :: Type -> Type) a = a -> f a
- ana :: forall a f. Functor f => Coalg f a -> a -> Term f
- ana' :: forall a f. Functor f => Coalg f a -> a -> Term f
- type CoalgM (m :: Type -> Type) (f :: Type -> Type) a = a -> m (f a)
- anaM :: forall a m f. (Traversable f, Monad m) => CoalgM m f a -> a -> m (Term f)
- type RAlg (f :: Type -> Type) a = f (Term f, a) -> a
- para :: Functor f => RAlg f a -> Term f -> a
- type RAlgM (m :: Type -> Type) (f :: Type -> Type) a = f (Term f, a) -> m a
- paraM :: (Traversable f, Monad m) => RAlgM m f a -> Term f -> m a
- type RCoalg (f :: Type -> Type) a = a -> f (Either (Term f) a)
- apo :: Functor f => RCoalg f a -> a -> Term f
- type RCoalgM (m :: Type -> Type) (f :: Type -> Type) a = a -> m (f (Either (Term f) a))
- apoM :: (Traversable f, Monad m) => RCoalgM m f a -> a -> m (Term f)
- type CVAlg (f :: Type -> Type) a (f' :: Type -> Type) = f (Term f') -> a
- histo :: forall f a (f' :: Type -> Type). (Functor f, DistAnn f a f') => CVAlg f a f' -> Term f -> a
- type CVAlgM (m :: Type -> Type) (f :: Type -> Type) a (f' :: Type -> Type) = f (Term f') -> m a
- histoM :: forall f m a (f' :: Type -> Type). (Traversable f, Monad m, DistAnn f a f') => CVAlgM m f a f' -> Term f -> m a
- type CVCoalg (f :: Type -> Type) a = a -> f (Context f a)
- futu :: Functor f => CVCoalg f a -> a -> Term f
- type CVCoalg' (f :: Type -> Type) a = a -> Context f a
- futu' :: forall (f :: Type -> Type) a. Functor f => CVCoalg' f a -> a -> Term f
- type CVCoalgM (m :: Type -> Type) (f :: Type -> Type) a = a -> m (f (Context f a))
- futuM :: forall f a m. (Traversable f, Monad m) => CVCoalgM m f a -> a -> m (Term f)
Algebras & Catamorphisms
type Alg (f :: Type -> Type) 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 :: 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 :: forall (f :: Type -> Type) h a. 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 :: Type -> Type) (f :: Type -> Type) 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 :: (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 :: Type -> Type) (g :: Type -> Type) = forall a h. Cxt h f a -> Cxt h g a Source #
This type represents a context function.
type SigFun (f :: Type -> Type) (g :: Type -> Type) = forall a. f a -> g a Source #
This type represents a signature function.
type Hom (f :: Type -> Type) (g :: Type -> Type) = SigFun f (Context g) Source #
This type represents a term homomorphism.
appHom :: forall (f :: Type -> Type) (g :: Type -> Type). (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 :: Type -> Type) (g :: Type -> Type). 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 :: forall (g :: Type -> Type) (h :: Type -> Type) (f :: Type -> Type). (Functor g, Functor h) => Hom g h -> Hom f g -> Hom f h Source #
Compose two term homomorphisms.
appSigFun :: forall (f :: Type -> Type) (g :: Type -> Type). Functor f => SigFun f g -> CxtFun f g Source #
This function applies a signature function to the given context.
appSigFun' :: forall (g :: Type -> Type) (f :: Type -> Type). 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 :: forall (g :: Type -> Type) (h :: Type -> Type) (f :: Type -> Type). SigFun g h -> SigFun f g -> SigFun f h Source #
This function composes two signature functions.
compSigFunHom :: forall (g :: Type -> Type) (h :: Type -> Type) (f :: Type -> Type). Functor g => SigFun g h -> Hom f g -> Hom f h Source #
This function composes a signature function with a term homomorphism.
compHomSigFun :: forall (g :: Type -> Type) (h :: Type -> Type) (f :: Type -> Type). 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 :: forall (g :: Type -> Type) (f :: Type -> Type). 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 :: forall f (g :: Type -> Type) a. Hom f g -> Coalg f a -> CVCoalg' g a Source #
Compose a term homomorphism with a coalgebra to get a cv-coalgebra.
compCVCoalg :: forall (f :: Type -> Type) (g :: Type -> Type) a. (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 :: Type -> Type) (f :: Type -> Type) (g :: Type -> Type) = forall a h. Cxt h f a -> m (Cxt h g a) Source #
This type represents a monadic context function.
type SigFunM (m :: Type -> Type) (f :: Type -> Type) (g :: Type -> Type) = forall a. f a -> m (g a) Source #
This type represents a monadic signature function.
type HomM (m :: Type -> Type) (f :: Type -> Type) (g :: Type -> Type) = SigFunM m f (Context g) Source #
This type represents a monadic term homomorphism.
type SigFunMD (m :: Type -> Type) (f :: Type -> Type) (g :: Type -> Type) = 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 :: Type -> Type) (f :: Type -> Type) (g :: Type -> Type) = 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 :: forall (m :: Type -> Type) (f :: Type -> Type) (g :: Type -> Type). 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' :: forall (f :: Type -> Type) (g :: Type -> Type) (m :: Type -> Type). (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 :: Type -> Type) (g :: Type -> Type) (m :: Type -> Type). (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 :: Type -> Type) (g :: Type -> Type) (m :: Type -> Type). (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 :: forall (g :: Type -> Type) (m :: Type -> Type) (f :: Type -> Type). (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 :: Type -> Type) (g :: Type -> Type) (m :: Type -> Type). (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 :: forall (f :: Type -> Type) (m :: Type -> Type) (g :: Type -> Type). (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' :: forall (g :: Type -> Type) (m :: Type -> Type) (f :: Type -> Type). (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 :: Type -> Type) (g :: Type -> Type) (m :: Type -> Type). (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 :: forall (g :: Type -> Type) (h :: Type -> Type) (m :: Type -> Type) (f :: Type -> Type). (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 :: forall (m :: Type -> Type) (g :: Type -> Type) (h :: Type -> Type) (f :: Type -> Type). Monad m => SigFunM m g h -> SigFunM m f g -> SigFunM m f h Source #
This function composes two monadic signature functions.
compSigFunHomM :: forall (g :: Type -> Type) (h :: Type -> Type) (m :: Type -> Type) (f :: Type -> Type). (Traversable g, Functor h, Monad m) => SigFunM m g h -> HomM m f g -> HomM m f h Source #
compHomSigFunM :: forall (m :: Type -> Type) (g :: Type -> Type) (h :: Type -> Type) (f :: Type -> Type). 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 :: Type -> Type) 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.
type CoalgM (m :: Type -> Type) (f :: Type -> Type) 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 :: Type -> Type) 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 :: Type -> Type) (f :: Type -> Type) 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 :: Type -> Type) 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 :: Type -> Type) (f :: Type -> Type) 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 :: Type -> Type) a (f' :: Type -> Type) = f (Term f') -> a Source #
This type represents a cv-algebra over a functor f and carrier a.
histo :: forall f a (f' :: Type -> Type). (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 :: Type -> Type) (f :: Type -> Type) a (f' :: Type -> Type) = f (Term f') -> m a Source #
This type represents a monadic cv-algebra over a functor f and carrier
a.
histoM :: forall f m a (f' :: Type -> Type). (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 :: Type -> Type) a = a -> f (Context f a) Source #
This type represents a cv-coalgebra over a functor f and carrier a.
futu :: Functor f => CVCoalg f a -> a -> Term f Source #
Construct a futumorphism from the given cv-coalgebra.
type CVCoalg' (f :: Type -> Type) a = a -> Context f a Source #
This type represents a generalised cv-coalgebra over a functor f and
carrier a.
futu' :: forall (f :: Type -> Type) a. Functor f => CVCoalg' f a -> a -> Term f Source #
Construct a futumorphism from the given generalised cv-coalgebra.