Portability | non-portable (GHC Extensions) |
---|---|
Stability | experimental |
Maintainer | Tom Hvitved <hvitved@diku.dk> |
Safe Haskell | Safe-Infered |
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. HDifunctor f => Alg f a -> (b :-> a) -> Cxt h f a b :-> a
- cata :: forall f a. HDifunctor f => Alg f a -> Term f :-> a
- cata' :: HDifunctor f => Alg f a -> Cxt h f a a :-> a
- appCxt :: HDifunctor f => Cxt Hole f a (Cxt h f a b) :-> Cxt h f a b
- type AlgM m f a = NatM m (f a a) a
- 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
- cataM :: forall m f a. (HDitraversable f, Monad m) => AlgM m f a -> NatM m (Term f) a
- type AlgM' m f a = NatM m (f a (Compose m a)) a
- newtype Compose f g a = Compose {
- 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
- cataM' :: forall m f a. (HDifunctor f, Monad m) => AlgM' m f a -> NatM m (Term f) a
- type CxtFun f g = forall h. SigFun (Cxt h f) (Cxt h g)
- 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. (HDifunctor f, HDifunctor g) => Hom f g -> CxtFun f g
- appHom' :: forall f g. HDifunctor g => Hom f g -> CxtFun f g
- compHom :: (HDifunctor g, HDifunctor h) => Hom g h -> Hom f g -> Hom f h
- appSigFun :: forall f g. HDifunctor f => SigFun f g -> CxtFun f g
- appSigFun' :: forall f g. HDifunctor g => SigFun f g -> CxtFun f g
- compSigFun :: SigFun g h -> SigFun f g -> SigFun f h
- hom :: HDifunctor g => SigFun f g -> Hom f g
- compAlg :: (HDifunctor f, HDifunctor g) => Alg g a -> Hom 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. NatM m (f a b) (g a b)
- type HomM m f g = SigFunM m f (Cxt Hole g)
- sigFunM :: Monad m => SigFun f g -> SigFunM m f g
- hom' :: (HDifunctor f, HDifunctor g, Monad m) => SigFunM m f g -> HomM m f g
- appHomM :: forall f g m. (HDitraversable f, Monad m, HDifunctor g) => HomM m f g -> CxtFunM m f g
- appTHomM :: (HDitraversable f, Monad m, ParamFunctor m, HDifunctor g) => HomM m f g -> Term f i -> m (Term g i)
- appHomM' :: forall f g m. (HDitraversable g, Monad m) => HomM m f g -> CxtFunM m f g
- appTHomM' :: (HDitraversable g, Monad m, ParamFunctor m, HDifunctor g) => HomM m f g -> Term f i -> m (Term g i)
- homM :: (HDifunctor g, Monad m) => SigFun f g -> HomM m f g
- appSigFunM :: forall m f g. (HDitraversable f, Monad m) => SigFunM m f g -> CxtFunM m f g
- appTSigFunM :: (HDitraversable f, Monad m, ParamFunctor m, HDifunctor g) => SigFunM m f g -> Term f i -> m (Term g i)
- appSigFunM' :: forall m f g. (HDitraversable g, Monad m) => SigFunM m f g -> CxtFunM m f g
- appTSigFunM' :: (HDitraversable g, Monad m, ParamFunctor m, HDifunctor g) => SigFunM m f g -> Term f i -> m (Term g i)
- compHomM :: (HDitraversable g, HDifunctor 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
- compAlgM :: (HDitraversable g, Monad m) => AlgM m g a -> HomM m f g -> AlgM m f a
- compAlgM' :: (HDitraversable g, Monad m) => AlgM m g a -> Hom f g -> AlgM m f a
Algebras & Catamorphisms
free :: forall h f a b. HDifunctor 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. HDifunctor f => Alg f a -> Term f :-> aSource
Construct a catamorphism from the given algebra.
cata' :: HDifunctor 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 :: HDifunctor f => Cxt Hole 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 = NatM m (f a a) aSource
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) aSource
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) aSource
Construct a monadic catamorphism from the given monadic algebra.
type AlgM' m f a = NatM m (f a (Compose m a)) aSource
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.
Compose | |
|
(Functor f, Functor g) => Functor (Compose f g) | |
(Applicative f, Applicative g) => Applicative (Compose f g) | |
(Foldable f, Foldable g) => Foldable (Compose f g) | |
(Traversable f, Traversable g) => Traversable (Compose f g) | |
(Alternative f, Applicative g) => Alternative (Compose f g) |
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) aSource
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) aSource
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.
appHom :: forall f g. (HDifunctor f, HDifunctor g) => Hom f g -> CxtFun f gSource
Apply a term homomorphism recursively to a term/context.
appHom' :: forall f g. HDifunctor g => Hom f g -> CxtFun f gSource
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 hSource
Compose two term homomorphisms.
appSigFun :: forall f g. HDifunctor f => SigFun f g -> CxtFun f gSource
This function applies a signature function to the given context.
appSigFun' :: forall f g. HDifunctor g => SigFun f g -> CxtFun f gSource
This function applies a signature function to the given context.
compSigFun :: SigFun g h -> SigFun f g -> SigFun f hSource
This function composes two signature functions.
hom :: HDifunctor g => SigFun f g -> Hom f gSource
Lifts the given signature function to the canonical term homomorphism.
compAlg :: (HDifunctor f, HDifunctor g) => Alg g a -> Hom f g -> Alg f aSource
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.
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.
hom' :: (HDifunctor f, HDifunctor g, Monad m) => SigFunM m f g -> HomM m f gSource
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 gSource
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 gSource
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 gSource
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 gSource
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 gSource
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 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.