| Portability | non-portable (GHC Extensions) |
|---|---|
| Stability | experimental |
| Maintainer | Tom Hvitved <[email protected]> |
Data.Comp.Param.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.
- type Alg f a = f a a -> a
- free :: forall h f a b. Difunctor f => Alg f a -> (b -> a) -> Cxt h f a b -> a
- cata :: forall f a. Difunctor f => Alg f a -> Term f -> a
- cata' :: Difunctor f => Alg f a -> Cxt h f a a -> a
- appCxt :: Difunctor f => Context f a (Cxt h f a b) -> Cxt h f a b
- type AlgM m f a = f a a -> m a
- algM :: (Ditraversable f, Monad m) => AlgM m f a -> Alg f (m a)
- freeM :: forall m h f a b. (Ditraversable f, Monad m) => AlgM m f a -> (b -> m a) -> Cxt h f a b -> m a
- cataM :: forall m f a. (Ditraversable f, Monad m) => AlgM m f a -> Term f -> m a
- cataM' :: forall m h f a. (Ditraversable f, Monad m) => AlgM m f a -> Cxt h f a (m a) -> m a
- type CxtFun f g = forall h a b. Cxt h f a b -> Cxt h g a b
- type SigFun f g = forall a b. f a b -> g a b
- type Hom f g = SigFun f (Context g)
- appHom :: forall f g. (Difunctor f, Difunctor g) => Hom f g -> CxtFun f g
- appHom' :: forall f g. Difunctor g => Hom f g -> CxtFun f g
- compHom :: (Difunctor g, Difunctor h) => Hom g h -> Hom f g -> Hom f h
- appSigFun :: forall f g. Difunctor f => SigFun f g -> CxtFun f g
- appSigFun' :: forall f g. Difunctor g => SigFun f g -> CxtFun f g
- compSigFun :: SigFun g h -> SigFun f g -> SigFun f h
- compHomSigFun :: Hom g h -> SigFun f g -> Hom f h
- compSigFunHom :: Difunctor g => SigFun g h -> Hom f g -> Hom f h
- hom :: Difunctor g => SigFun f g -> Hom f g
- compAlg :: (Difunctor f, Difunctor g) => Alg g a -> Hom f g -> Alg f a
- compAlgSigFun :: Alg g a -> SigFun f g -> Alg f a
- type CxtFunM m f g = forall h. SigFunM m (Cxt h f) (Cxt h g)
- type SigFunM m f g = forall a b. f a b -> m (g a b)
- type HomM m f g = SigFunM m f (Context g)
- type SigFunMD m f g = forall a b. f a (m b) -> m (g a b)
- type HomMD m f g = SigFunMD m f (Context g)
- sigFunM :: Monad m => SigFun f g -> SigFunM m f g
- appHomM :: forall f g m. (Ditraversable f, Difunctor g, Monad m) => HomM m f g -> CxtFunM m f g
- appTHomM :: (Ditraversable f, ParamFunctor m, Monad m, Difunctor g) => HomM m f g -> Term f -> m (Term g)
- appHomM' :: forall f g m. (Ditraversable g, Monad m) => HomM m f g -> CxtFunM m f g
- appTHomM' :: (Ditraversable g, ParamFunctor m, Monad m, Difunctor g) => HomM m f g -> Term f -> m (Term g)
- homM :: (Difunctor g, Monad m) => SigFunM m f g -> HomM m f g
- homMD :: forall f g m. (Difunctor f, Difunctor g, Monad m) => HomMD m f g -> CxtFunM m f g
- appSigFunM :: forall m f g. (Ditraversable f, Monad m) => SigFunM m f g -> CxtFunM m f g
- appTSigFunM :: (Ditraversable f, ParamFunctor m, Monad m, Difunctor g) => SigFunM m f g -> Term f -> m (Term g)
- appSigFunM' :: forall m f g. (Ditraversable g, Monad m) => SigFunM m f g -> CxtFunM m f g
- appTSigFunM' :: (Ditraversable g, ParamFunctor m, Monad m, Difunctor g) => SigFunM m f g -> Term f -> m (Term g)
- appSigFunMD :: forall f g m. (Ditraversable f, Difunctor g, Monad m) => SigFunMD m f g -> CxtFunM m f g
- appTSigFunMD :: (Ditraversable f, ParamFunctor m, Monad m, Difunctor g) => SigFunMD m f g -> Term f -> m (Term g)
- compHomM :: (Ditraversable g, Difunctor h, Monad m) => HomM m g h -> HomM m f g -> HomM m f h
- compHomM' :: (Ditraversable h, Monad m) => HomM m g h -> HomM m f g -> HomM m f h
- compSigFunM :: Monad m => SigFunM m g h -> SigFunM m f g -> SigFunM m f h
- compSigFunHomM :: (Ditraversable g, Monad m) => SigFunM m g h -> HomM m f g -> HomM m f h
- compSigFunHomM' :: (Ditraversable h, Monad m) => SigFunM m g h -> HomM m f g -> HomM m f h
- compAlgSigFunM :: Monad m => AlgM m g a -> SigFunM m f g -> AlgM m f a
- compAlgSigFunM' :: AlgM m g a -> SigFun f g -> AlgM m f a
- compAlgM :: (Ditraversable g, Monad m) => AlgM m g a -> HomM m f g -> AlgM m f a
- compAlgM' :: (Ditraversable g, Monad m) => AlgM m g a -> Hom f g -> AlgM m f a
- type Coalg f a = forall b. a -> [(a, b)] -> Either b (f b (a, [(a, b)]))
- ana :: Difunctor f => Coalg f a -> a -> Term f
- type CoalgM m f a = forall b. a -> [(a, b)] -> m (Either b (f b (a, [(a, b)])))
- anaM :: forall a m f. (Ditraversable f, Monad m) => CoalgM m f a -> a -> forall a. m (Trm f a)
- type RAlg f a = f a (Trm f a, a) -> a
- para :: forall f a. Difunctor f => RAlg f a -> Term f -> a
- type RAlgM m f a = f a (Trm f a, a) -> m a
- paraM :: forall m f a. (Ditraversable f, Monad m) => RAlgM m f a -> Term f -> m a
- type RCoalg f a = forall b. a -> [(a, b)] -> Either b (f b (Either (Trm f b) (a, [(a, b)])))
- apo :: Difunctor f => RCoalg f a -> a -> Term f
- type RCoalgM m f a = forall b. a -> [(a, b)] -> m (Either b (f b (Either (Trm f b) (a, [(a, b)]))))
- apoM :: forall f m a. (Ditraversable f, Monad m) => RCoalgM m f a -> a -> forall a. m (Trm f a)
- type CVAlg f a f' = f a (Trm f' a) -> a
- histo :: forall f f' a. (Difunctor f, DistAnn f a f') => CVAlg f a f' -> Term f -> a
- type CVAlgM m f a f' = f a (Trm f' a) -> m a
- histoM :: forall f f' m a. (Ditraversable f, Monad m, DistAnn f a f') => CVAlgM m f a f' -> Term f -> m a
- type CVCoalg f a = forall b. a -> [(a, b)] -> Either b (f b (Context f b (a, [(a, b)])))
- futu :: Difunctor f => CVCoalg f a -> a -> Term f
- type CVCoalg' f a = forall b. a -> [(a, b)] -> Context f b (a, [(a, b)])
- futu' :: Difunctor f => CVCoalg' f a -> a -> Term f
- type CVCoalgM m f a = forall b. a -> [(a, b)] -> m (Either b (f b (Context f b (a, [(a, b)]))))
- futuM :: forall f a m. (Ditraversable f, Monad m) => CVCoalgM m f a -> a -> forall a. m (Trm f a)
Algebras & Catamorphisms
free :: forall h f a b. Difunctor f => Alg f a -> (b -> a) -> Cxt h f a b -> aSource
Construct a catamorphism for contexts over f with holes of type b, from
the given algebra.
cata :: forall f a. Difunctor f => Alg f a -> Term f -> aSource
Construct a catamorphism from the given algebra.
cata' :: Difunctor f => Alg f a -> Cxt h f a a -> aSource
A generalisation of cata from terms over f to contexts over f, where
the holes have the type of the algebra carrier.
appCxt :: Difunctor f => Context f a (Cxt h f a b) -> Cxt h f a bSource
This function applies a whole context into another context.
Monadic Algebras & Catamorphisms
type AlgM m f a = f a a -> m aSource
This type represents a monadic algebra. It is similar to Alg but
the return type is monadic.
algM :: (Ditraversable 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 m h f a b. (Ditraversable f, Monad m) => AlgM m f a -> (b -> m a) -> Cxt h f a b -> m aSource
Construct a monadic catamorphism for contexts over f with holes of type
b, from the given monadic algebra.
cataM :: forall m f a. (Ditraversable f, Monad m) => AlgM m f a -> Term f -> m aSource
Construct a monadic catamorphism from the given monadic algebra.
cataM' :: forall m h f a. (Ditraversable f, Monad m) => AlgM m f a -> Cxt h f a (m a) -> m aSource
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 h a b. Cxt h f a b -> Cxt h g a bSource
This type represents a context function.
appHom :: forall f g. (Difunctor f, Difunctor g) => Hom f g -> CxtFun f gSource
Apply a term homomorphism recursively to a term/context.
appHom' :: forall f g. Difunctor g => Hom f g -> CxtFun f gSource
Apply a term homomorphism recursively to a term/context.
compHom :: (Difunctor g, Difunctor h) => Hom g h -> Hom f g -> Hom f hSource
Compose two term homomorphisms.
appSigFun :: forall f g. Difunctor f => SigFun f g -> CxtFun f gSource
This function applies a signature function to the given context.
appSigFun' :: forall f g. Difunctor g => SigFun f g -> CxtFun f gSource
This function applies a signature function to the given
context. This is a top-bottom variant of appSigFun.
compSigFun :: SigFun g h -> SigFun f g -> SigFun f hSource
This function composes two signature functions.
compHomSigFun :: Hom g h -> SigFun f g -> Hom f hSource
This function composes a term homomorphism and a signature function.
compSigFunHom :: Difunctor g => SigFun g h -> Hom f g -> Hom f hSource
This function composes a term homomorphism and a signature function.
hom :: Difunctor g => SigFun f g -> Hom f gSource
Lifts the given signature function to the canonical term homomorphism.
compAlg :: (Difunctor f, Difunctor g) => Alg g a -> Hom f g -> Alg f aSource
Compose an algebra with a term homomorphism to get a new algebra.
compAlgSigFun :: Alg g a -> SigFun f g -> Alg f aSource
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. f a b -> m (g a b)Source
This type represents a monadic signature function.
type SigFunMD m f g = forall a b. f a (m b) -> m (g a b)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 gSource
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.
appHomM :: forall f g m. (Ditraversable f, Difunctor g, Monad m) => HomM m f g -> CxtFunM m f gSource
Apply a monadic term homomorphism recursively to a term/context. The monad is sequenced bottom-up.
appTHomM :: (Ditraversable f, ParamFunctor m, Monad m, Difunctor g) => HomM m f g -> Term f -> m (Term g)Source
A restricted form of |appHomM| which only works for terms.
appHomM' :: forall f g m. (Ditraversable g, Monad m) => HomM m f g -> CxtFunM m f gSource
Apply a monadic term homomorphism recursively to a term/context. The monad is sequence top-down.
appTHomM' :: (Ditraversable g, ParamFunctor m, Monad m, Difunctor g) => HomM m f g -> Term f -> m (Term g)Source
A restricted form of |appHomM'| which only works for terms.
homM :: (Difunctor g, Monad m) => SigFunM m f g -> HomM m f gSource
Lift the given signature function to a monadic term homomorphism.
homMD :: forall f g m. (Difunctor f, Difunctor g, Monad m) => HomMD m f g -> CxtFunM m f gSource
This function constructs the unique monadic homomorphism from the initial term algebra to the given term algebra.
appSigFunM :: forall m f g. (Ditraversable f, Monad m) => SigFunM m f g -> CxtFunM m f gSource
This function applies a monadic signature function to the given context.
appTSigFunM :: (Ditraversable f, ParamFunctor m, Monad m, Difunctor g) => SigFunM m f g -> Term f -> m (Term g)Source
A restricted form of |appSigFunM| which only works for terms.
appSigFunM' :: forall m f g. (Ditraversable g, Monad m) => SigFunM m f g -> CxtFunM m f gSource
This function applies a monadic signature function to the given
context. This is a 'top-down variant of appSigFunM.
appTSigFunM' :: (Ditraversable g, ParamFunctor m, Monad m, Difunctor g) => SigFunM m f g -> Term f -> m (Term g)Source
A restricted form of |appSigFunM'| which only works for terms.
appSigFunMD :: forall f g m. (Ditraversable f, Difunctor g, Monad m) => SigFunMD m f g -> CxtFunM m f gSource
This function applies a signature function to the given context.
appTSigFunMD :: (Ditraversable f, ParamFunctor m, Monad m, Difunctor g) => SigFunMD m f g -> Term f -> m (Term g)Source
A restricted form of |appSigFunMD| which only works for terms.
compHomM :: (Ditraversable g, Difunctor h, Monad m) => HomM m g h -> HomM m f g -> HomM m f hSource
Compose two monadic term homomorphisms.
compHomM' :: (Ditraversable h, Monad m) => HomM m g h -> HomM m f g -> HomM m f hSource
Compose two monadic term homomorphisms.
compSigFunM :: Monad m => SigFunM m g h -> SigFunM m f g -> SigFunM m f hSource
This function composes two monadic signature functions.
compSigFunHomM :: (Ditraversable g, Monad m) => SigFunM m g h -> HomM m f g -> HomM m f hSource
Compose two monadic term homomorphisms.
compSigFunHomM' :: (Ditraversable h, Monad m) => SigFunM m g h -> HomM m f g -> HomM m f hSource
Compose two monadic term homomorphisms.
compAlgSigFunM :: Monad m => AlgM m g a -> SigFunM m f g -> AlgM m f aSource
Compose a monadic algebra with a monadic signature function to get a new monadic algebra.
compAlgSigFunM' :: AlgM m g a -> SigFun f g -> AlgM m f aSource
Compose a monadic algebra with a signature function to get a new monadic algebra.
compAlgM :: (Ditraversable g, Monad m) => AlgM m g a -> HomM m f g -> AlgM m f aSource
Compose a monadic algebra with a monadic term homomorphism to get a new monadic algebra.
compAlgM' :: (Ditraversable g, Monad m) => AlgM m g a -> Hom f g -> AlgM m f aSource
Compose a monadic algebra with a term homomorphism to get a new monadic algebra.
Coalgebras & Anamorphisms
type Coalg f a = forall b. a -> [(a, b)] -> Either b (f b (a, [(a, b)]))Source
This type represents a coalgebra over a difunctor f and carrier a. The
list of (a,b)s represent the parameters that may occur in the constructed
value. The first component represents the seed of the parameter,
and the second component is the (polymorphic) parameter itself. If f is
itself a binder, then the parameters bound by f can be passed to the
covariant argument, thereby making them available to sub terms.
ana :: Difunctor f => Coalg f a -> a -> Term fSource
Construct an anamorphism from the given coalgebra.
type CoalgM m f a = forall b. a -> [(a, b)] -> m (Either b (f b (a, [(a, b)])))Source
This type represents a monadic coalgebra over a difunctor f and carrier
a.
anaM :: forall a m f. (Ditraversable f, Monad m) => CoalgM m f a -> a -> forall a. m (Trm f a)Source
Construct a monadic anamorphism from the given monadic coalgebra.
R-Algebras & Paramorphisms
type RAlg f a = f a (Trm f a, a) -> aSource
This type represents an r-algebra over a difunctor f and carrier a.
para :: forall f a. Difunctor f => RAlg f a -> Term f -> aSource
Construct a paramorphism from the given r-algebra.
type RAlgM m f a = f a (Trm f a, a) -> m aSource
This type represents a monadic r-algebra over a difunctor f and carrier
a.
paraM :: forall m f a. (Ditraversable f, Monad m) => RAlgM m f a -> Term f -> m aSource
Construct a monadic paramorphism from the given monadic r-algebra.
R-Coalgebras & Apomorphisms
type RCoalg f a = forall b. a -> [(a, b)] -> Either b (f b (Either (Trm f b) (a, [(a, b)])))Source
This type represents an r-coalgebra over a difunctor f and carrier a.
apo :: Difunctor f => RCoalg f a -> a -> Term fSource
Construct an apomorphism from the given r-coalgebra.
type RCoalgM m f a = forall b. a -> [(a, b)] -> m (Either b (f b (Either (Trm f b) (a, [(a, b)]))))Source
This type represents a monadic r-coalgebra over a functor f and carrier
a.
apoM :: forall f m a. (Ditraversable f, Monad m) => RCoalgM m f a -> a -> forall a. m (Trm f a)Source
Construct a monadic apomorphism from the given monadic r-coalgebra.
CV-Algebras & Histomorphisms
type CVAlg f a f' = f a (Trm f' a) -> aSource
This type represents a cv-algebra over a difunctor f and carrier a.
histo :: forall f f' a. (Difunctor f, DistAnn f a f') => CVAlg f a f' -> Term f -> aSource
Construct a histomorphism from the given cv-algebra.
type CVAlgM m f a f' = f a (Trm f' a) -> m aSource
This type represents a monadic cv-algebra over a functor f and carrier
a.
histoM :: forall f f' m a. (Ditraversable f, Monad m, DistAnn f a f') => CVAlgM m f a f' -> Term f -> m aSource
Construct a monadic histomorphism from the given monadic cv-algebra.
CV-Coalgebras & Futumorphisms
type CVCoalg f a = forall b. a -> [(a, b)] -> Either b (f b (Context f b (a, [(a, b)])))Source
This type represents a cv-coalgebra over a difunctor f and carrier a.
The list of (a,b)s represent the parameters that may occur in the
constructed value. The first component represents the seed of the parameter,
and the second component is the (polymorphic) parameter itself. If f is
itself a binder, then the parameters bound by f can be passed to the
covariant argument, thereby making them available to sub terms.
futu :: Difunctor f => CVCoalg f a -> a -> Term fSource
Construct a futumorphism from the given cv-coalgebra.
type CVCoalg' f a = forall b. a -> [(a, b)] -> Context f b (a, [(a, b)])Source
This type represents a generalised cv-coalgebra over a difunctor f and
carrier a.
futu' :: Difunctor f => CVCoalg' f a -> a -> Term fSource
Construct a futumorphism from the given generalised cv-coalgebra.