Copyright | (c) 2011 Patrick Bahr |
---|---|
License | BSD3 |
Maintainer | Patrick Bahr <paba@diku.dk> |
Stability | experimental |
Portability | non-portable (GHC Extensions) |
Safe Haskell | None |
Language | Haskell98 |
Data.Comp.Multi.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. All definitions are generalised versions of those in Data.Comp.Algebra.
- type Alg f e = f e :-> e
- free :: forall f h a b. HFunctor f => Alg f b -> (a :-> b) -> Cxt h f a :-> b
- cata :: forall f a. HFunctor f => Alg f a -> Term f :-> a
- cata' :: HFunctor f => Alg f e -> Cxt h f e :-> e
- appCxt :: HFunctor f => Context f (Cxt h f a) :-> Cxt h f a
- type AlgM m f e = NatM m (f e) e
- freeM :: forall f m h a b. (HTraversable f, Monad m) => AlgM m f b -> NatM m a b -> NatM m (Cxt h f a) b
- cataM :: forall f m a. (HTraversable f, Monad m) => AlgM m f a -> NatM m (Term f) a
- cataM' :: forall m h a f. (Monad m, HTraversable f) => AlgM m f a -> NatM m (Cxt h f a) a
- liftMAlg :: forall m f. (Monad m, HTraversable f) => Alg f I -> Alg f m
- type CxtFun f g = forall h. SigFun (Cxt h f) (Cxt h g)
- type SigFun f g = forall a. f a :-> g a
- type Hom f g = SigFun f (Context g)
- appHom :: forall f g. (HFunctor f, HFunctor g) => Hom f g -> CxtFun f g
- appHom' :: forall f g. HFunctor g => Hom f g -> CxtFun f g
- compHom :: (HFunctor g, HFunctor h) => Hom g h -> Hom f g -> Hom f h
- appSigFun :: forall f g. HFunctor f => SigFun f g -> CxtFun f g
- appSigFun' :: forall f g. HFunctor g => SigFun f g -> CxtFun f g
- compSigFun :: SigFun g h -> SigFun f g -> SigFun f h
- hom :: HFunctor g => SigFun f g -> Hom f g
- compAlg :: HFunctor 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. NatM m (f a) (g a)
- type HomM m f g = SigFunM m f (Context g)
- sigFunM :: Monad m => SigFun f g -> SigFunM m f g
- hom' :: (HFunctor f, HFunctor g, Monad m) => SigFunM m f g -> HomM m f g
- appHomM :: forall f g m. (HTraversable f, HFunctor g, Monad m) => HomM m f g -> CxtFunM m f g
- appHomM' :: forall f g m. (HTraversable g, Monad m) => HomM m f g -> CxtFunM m f g
- homM :: (HFunctor g, Monad m) => SigFun f g -> HomM m f g
- appSigFunM :: forall f g m. (HTraversable f, Monad m) => SigFunM m f g -> CxtFunM m f g
- appSigFunM' :: forall f g m. (HTraversable g, Monad m) => SigFunM m f g -> CxtFunM m f g
- compHomM :: (HTraversable g, HFunctor 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 :: (HTraversable g, Monad m) => AlgM m g a -> HomM m f g -> AlgM m f a
- compAlgM' :: (HTraversable g, Monad m) => AlgM m g a -> Hom f g -> AlgM m f a
- type Coalg f a = a :-> f a
- ana :: forall f a. HFunctor f => Coalg f a -> a :-> Term f
- type CoalgM m f a = NatM m a (f a)
- anaM :: forall a m f. (HTraversable f, Monad m) => CoalgM m f a -> NatM m a (Term f)
- type RAlg f a = f (Term f :*: a) :-> a
- para :: forall f a. HFunctor f => RAlg f a -> Term f :-> a
- type RAlgM m f a = NatM m (f (Term f :*: a)) a
- paraM :: forall f m a. (HTraversable f, Monad m) => RAlgM m f a -> NatM m (Term f) a
- type RCoalg f a = a :-> f (Term f :+: a)
- apo :: forall f a. HFunctor f => RCoalg f a -> a :-> Term f
- type RCoalgM m f a = NatM m a (f (Term f :+: a))
- apoM :: forall f m a. (HTraversable f, Monad m) => RCoalgM m f a -> NatM m a (Term f)
- type CVCoalg f a = a :-> f (Context f a)
- futu :: forall f a. HFunctor f => CVCoalg f a -> a :-> Term f
- type CVCoalgM m f a = NatM m a (f (Context f a))
- futuM :: forall f a m. (HTraversable f, Monad m) => CVCoalgM m f a -> NatM m a (Term f)
Algebras & Catamorphisms
type Alg f e = f e :-> e Source
This type represents multisorted f
-algebras with a family e
of carriers.
free :: forall f h a b. HFunctor f => Alg f b -> (a :-> b) -> Cxt h f a :-> b Source
Construct a catamorphism for contexts over f
with holes of type
b
, from the given algebra.
cata :: forall f a. HFunctor f => Alg f a -> Term f :-> a Source
Construct a catamorphism from the given algebra.
cata' :: HFunctor f => Alg f e -> Cxt h f e :-> e Source
A generalisation of cata
from terms over f
to contexts over
f
, where the holes have the type of the algebra carrier.
appCxt :: HFunctor 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 e = NatM m (f e) e Source
This type represents a monadic algebra. It is similar to Alg
but the return type is monadic.
freeM :: forall f m h a b. (HTraversable f, Monad m) => AlgM m f b -> NatM m a b -> NatM m (Cxt h f a) b Source
Construct a monadic catamorphism for contexts over f
with holes
of type b
, from the given monadic algebra.
cataM :: forall f m a. (HTraversable f, Monad m) => AlgM m f a -> NatM m (Term f) a Source
This is a monadic version of cata
.
liftMAlg :: forall m f. (Monad m, HTraversable f) => Alg f I -> Alg f m Source
This function lifts a many-sorted algebra to a monadic domain.
Term Homomorphisms
type SigFun f g = forall a. f a :-> g a Source
This type represents uniform signature function specification.
appHom :: forall f g. (HFunctor f, HFunctor g) => Hom f g -> CxtFun f g Source
This function applies the given term homomorphism to a term/context.
appHom' :: forall f g. HFunctor g => Hom f g -> CxtFun f g Source
This function applies the given term homomorphism to a
term/context. This is the top-down variant of appHom
.
compHom :: (HFunctor g, HFunctor h) => Hom g h -> Hom f g -> Hom f h Source
This function composes two term algebras.
appSigFun :: forall f g. HFunctor f => SigFun f g -> CxtFun f g Source
This function applies a signature function to the given context.
appSigFun' :: forall f g. HFunctor g => SigFun f g -> CxtFun f g Source
This function applies a signature function to the given
context. This is the top-down variant of appSigFun
.
compSigFun :: SigFun g h -> SigFun f g -> SigFun f h Source
This function composes two signature functions.
hom :: HFunctor g => SigFun f g -> Hom f g Source
Lifts the given signature function to the canonical term homomorphism.
compAlg :: HFunctor g => Alg g a -> Hom f g -> Alg f a Source
This function composes a term algebra with an algebra.
Monadic Term Homomorphisms
type CxtFunM m f g = forall h. SigFunM m (Cxt h f) (Cxt h g) Source
This type represents monadic context function.
type SigFunM m f g = forall a. NatM m (f a) (g a) Source
This type represents monadic signature functions.
sigFunM :: Monad m => SigFun f g -> SigFunM m f g Source
This function lifts the given signature function to a monadic signature function. Note that term algebras are instances of signature functions. Hence this function also applies to term algebras.
hom' :: (HFunctor f, HFunctor g, Monad m) => SigFunM m f g -> HomM m f g Source
This function lifts the give monadic signature function to a monadic term algebra.
appHomM :: forall f g m. (HTraversable f, HFunctor g, Monad m) => HomM m f g -> CxtFunM m f g Source
This function applies the given monadic term homomorphism to the given term/context.
appHomM' :: forall f g m. (HTraversable g, Monad m) => HomM m f g -> CxtFunM m f g Source
This function applies the given monadic term homomorphism to the
given term/context. This is a top-down variant of appHomM
.
homM :: (HFunctor g, Monad m) => SigFun f g -> HomM m f g Source
This function lifts the given signature function to a monadic term algebra.
appSigFunM :: forall f g m. (HTraversable f, Monad m) => SigFunM m f g -> CxtFunM m f g Source
This function applies the given monadic signature function to the given context.
appSigFunM' :: forall f g m. (HTraversable g, Monad m) => SigFunM m f g -> CxtFunM m f g Source
This function applies the given monadic signature function to the
given context. This is a top-down variant of appSigFunM
.
compHomM :: (HTraversable g, HFunctor h, Monad m) => HomM m g h -> HomM m f g -> HomM m f h Source
This function composes two monadic term algebras.
compSigFunM :: Monad m => SigFunM m g h -> SigFunM m f g -> SigFunM m f h Source
This function composes two monadic signature functions.
compAlgM :: (HTraversable g, Monad m) => AlgM m g a -> HomM m f g -> AlgM m f a Source
This function composes a monadic term algebra with a monadic algebra
compAlgM' :: (HTraversable g, Monad m) => AlgM m g a -> Hom f g -> AlgM m f a Source
This function composes a monadic term algebra with a monadic algebra.
Coalgebras & Anamorphisms
ana :: forall f a. HFunctor f => Coalg f a -> a :-> Term f Source
This function unfolds the given value to a term using the given
unravelling function. This is the unique homomorphism a -> Term f
from the given coalgebra of type a -> f a
to the final coalgebra
Term f
.
anaM :: forall a m f. (HTraversable f, Monad m) => CoalgM m f a -> NatM m a (Term f) Source
This function unfolds the given value to a term using the given
monadic unravelling function. This is the unique homomorphism a ->
Term f
from the given coalgebra of type a -> f a
to the final
coalgebra Term f
.
R-Algebras & Paramorphisms
type RAlg f a = f (Term f :*: a) :-> a Source
This type represents r-algebras over functor f
and with domain
a
.
para :: forall f a. HFunctor f => RAlg f a -> Term f :-> a Source
This function constructs a paramorphism from the given r-algebra
type RAlgM m f a = NatM m (f (Term f :*: a)) a Source
This type represents monadic r-algebras over monad m
and
functor f
and with domain a
.
paraM :: forall f m a. (HTraversable f, Monad m) => RAlgM m f a -> NatM m (Term f) a Source
This function constructs a monadic paramorphism from the given monadic r-algebra
R-Coalgebras & Apomorphisms
type RCoalg f a = a :-> f (Term f :+: a) Source
This type represents r-coalgebras over functor f
and with
domain a
.
apo :: forall f a. HFunctor f => RCoalg f a -> a :-> Term f Source
This function constructs an apomorphism from the given r-coalgebra.
type RCoalgM m f a = NatM m a (f (Term f :+: a)) Source
This type represents monadic r-coalgebras over monad m
and
functor f
with domain a
.
apoM :: forall f m a. (HTraversable f, Monad m) => RCoalgM m f a -> NatM m a (Term f) Source
This function constructs a monadic apomorphism from the given monadic r-coalgebra.
CV-Coalgebras & Futumorphisms
type CVCoalg f a = a :-> f (Context f a) Source
This type represents cv-coalgebras over functor f
and with domain
a
.
futu :: forall f a. HFunctor f => CVCoalg f a -> a :-> Term f Source
This function constructs the unique futumorphism from the given cv-coalgebra to the term algebra.