Copyright	(c) 2011 Patrick Bahr Tom Hvitved
License	BSD3
Maintainer	Tom Hvitved <hvitved@diku.dk>
Stability	experimental
Portability	non-portable (GHC Extensions)
Safe Haskell	None
Language	Haskell98

Data.Comp.Param.Multi.Algebra

Contents

Algebras & Catamorphisms
Monadic Algebras & Catamorphisms
Term Homomorphisms
Monadic Term Homomorphisms

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 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 :: k -> *) (g :: k1 -> k) (a :: k1) :: forall k k1. (k -> *) -> (k1 -> k) -> k1 -> * = 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

type Alg f a = f a a :-> a Source #

This type represents an algebra over a difunctor f and carrier a.

free :: forall h f a b. HDifunctor f => Alg f a -> (b :-> a) -> Cxt h f a b :-> a Source #

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 :-> a Source #

Construct a catamorphism from the given algebra.

cata' :: HDifunctor f => Alg f a -> Cxt h f a 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 :: HDifunctor f => Cxt Hole f a (Cxt h f a b) :-> Cxt h f a b Source #

This function applies a whole context into another context.

Monadic Algebras & Catamorphisms

type AlgM m f a = NatM m (f a a) a Source #

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) a Source #

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) a Source #

Construct a monadic catamorphism from the given monadic algebra.

type AlgM' m f a = NatM m (f a (Compose m a)) a Source #

This type represents a monadic algebra, but where the covariant argument is also a monadic computation.

newtype Compose (f :: k -> *) (g :: k1 -> k) (a :: k1) :: forall k k1. (k -> *) -> (k1 -> k) -> k1 -> * infixr 9 #

Right-to-left composition of functors. The composition of applicative functors is always applicative, but the composition of monads is not always a monad.

Constructors

Compose infixr 9
Fields getCompose :: f (g a)

Instances

Functor f => Generic1 (Compose f g :: k -> *)
Instance details Defined in Data.Functor.Compose Associated Types type Rep1 (Compose f g) :: k -> * # Methods from1 :: Compose f g a -> Rep1 (Compose f g) a # to1 :: Rep1 (Compose f g) a -> Compose f g a #
Functor f => HFunctor (Compose f :: (* -> ) -> -> *)
Instance details Defined in Data.Comp.Multi.HFunctor Methods hfmap :: (f0 :-> g) -> Compose f f0 :-> Compose f g #
(Functor f, Functor g) => Functor (Compose f g)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods fmap :: (a -> b) -> Compose f g a -> Compose f g b # (<$) :: a -> Compose f g b -> Compose f g a #
(Applicative f, Applicative g) => Applicative (Compose f g)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods pure :: a -> Compose f g a # (<>) :: Compose f g (a -> b) -> Compose f g a -> Compose f g b # liftA2 :: (a -> b -> c) -> Compose f g a -> Compose f g b -> Compose f g c # (>) :: Compose f g a -> Compose f g b -> Compose f g b # (<*) :: Compose f g a -> Compose f g b -> Compose f g a #
(Foldable f, Foldable g) => Foldable (Compose f g)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods fold :: Monoid m => Compose f g m -> m # foldMap :: Monoid m => (a -> m) -> Compose f g a -> m # foldr :: (a -> b -> b) -> b -> Compose f g a -> b # foldr' :: (a -> b -> b) -> b -> Compose f g a -> b # foldl :: (b -> a -> b) -> b -> Compose f g a -> b # foldl' :: (b -> a -> b) -> b -> Compose f g a -> b # foldr1 :: (a -> a -> a) -> Compose f g a -> a # foldl1 :: (a -> a -> a) -> Compose f g a -> a # toList :: Compose f g a -> [a] # null :: Compose f g a -> Bool # length :: Compose f g a -> Int # elem :: Eq a => a -> Compose f g a -> Bool # maximum :: Ord a => Compose f g a -> a # minimum :: Ord a => Compose f g a -> a # sum :: Num a => Compose f g a -> a # product :: Num a => Compose f g a -> a #
(Traversable f, Traversable g) => Traversable (Compose f g)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods traverse :: Applicative f0 => (a -> f0 b) -> Compose f g a -> f0 (Compose f g b) # sequenceA :: Applicative f0 => Compose f g (f0 a) -> f0 (Compose f g a) # mapM :: Monad m => (a -> m b) -> Compose f g a -> m (Compose f g b) # sequence :: Monad m => Compose f g (m a) -> m (Compose f g a) #
(Eq1 f, Eq1 g) => Eq1 (Compose f g)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods liftEq :: (a -> b -> Bool) -> Compose f g a -> Compose f g b -> Bool #
(Ord1 f, Ord1 g) => Ord1 (Compose f g)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods liftCompare :: (a -> b -> Ordering) -> Compose f g a -> Compose f g b -> Ordering #
(Read1 f, Read1 g) => Read1 (Compose f g)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Compose f g a) # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Compose f g a] # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Compose f g a) # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Compose f g a] #
(Show1 f, Show1 g) => Show1 (Compose f g)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Compose f g a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Compose f g a] -> ShowS #
(Alternative f, Applicative g) => Alternative (Compose f g)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods empty :: Compose f g a # (<\|>) :: Compose f g a -> Compose f g a -> Compose f g a # some :: Compose f g a -> Compose f g [a] # many :: Compose f g a -> Compose f g [a] #
(Eq1 f, Eq1 g, Eq a) => Eq (Compose f g a)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods (==) :: Compose f g a -> Compose f g a -> Bool # (/=) :: Compose f g a -> Compose f g a -> Bool #
(Typeable a, Typeable f, Typeable g, Typeable k1, Typeable k2, Data (f (g a))) => Data (Compose f g a)
Instance details Defined in Data.Functor.Compose Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g0. g0 -> c g0) -> Compose f g a -> c (Compose f g a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Compose f g a) # toConstr :: Compose f g a -> Constr # dataTypeOf :: Compose f g a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Compose f g a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Compose f g a)) # gmapT :: (forall b. Data b => b -> b) -> Compose f g a -> Compose f g a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Compose f g a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Compose f g a -> r # gmapQ :: (forall d. Data d => d -> u) -> Compose f g a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Compose f g a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Compose f g a -> m (Compose f g a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Compose f g a -> m (Compose f g a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Compose f g a -> m (Compose f g a) #
(Ord1 f, Ord1 g, Ord a) => Ord (Compose f g a)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods compare :: Compose f g a -> Compose f g a -> Ordering # (<) :: Compose f g a -> Compose f g a -> Bool # (<=) :: Compose f g a -> Compose f g a -> Bool # (>) :: Compose f g a -> Compose f g a -> Bool # (>=) :: Compose f g a -> Compose f g a -> Bool # max :: Compose f g a -> Compose f g a -> Compose f g a # min :: Compose f g a -> Compose f g a -> Compose f g a #
(Read1 f, Read1 g, Read a) => Read (Compose f g a)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods readsPrec :: Int -> ReadS (Compose f g a) # readList :: ReadS [Compose f g a] # readPrec :: ReadPrec (Compose f g a) # readListPrec :: ReadPrec [Compose f g a] #
(Show1 f, Show1 g, Show a) => Show (Compose f g a)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods showsPrec :: Int -> Compose f g a -> ShowS # show :: Compose f g a -> String # showList :: [Compose f g a] -> ShowS #
Generic (Compose f g a)
Instance details Defined in Data.Functor.Compose Associated Types type Rep (Compose f g a) :: * -> * # Methods from :: Compose f g a -> Rep (Compose f g a) x # to :: Rep (Compose f g a) x -> Compose f g a #
type Rep1 (Compose f g :: k -> *)
Instance details Defined in Data.Functor.Compose type Rep1 (Compose f g :: k -> *) = D1 (MetaData "Compose" "Data.Functor.Compose" "base" True) (C1 (MetaCons "Compose" PrefixI True) (S1 (MetaSel (Just "getCompose") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (f :.: Rec1 g)))
type Rep (Compose f g a)
Instance details Defined in Data.Functor.Compose type Rep (Compose f g a) = D1 (MetaData "Compose" "Data.Functor.Compose" "base" True) (C1 (MetaCons "Compose" PrefixI True) (S1 (MetaSel (Just "getCompose") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (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 Source #

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) a Source #

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.

type SigFun f g = forall (a :: * -> *) (b :: * -> *). f a b :-> g a b 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. (HDifunctor f, HDifunctor g) => Hom f g -> CxtFun f g Source #

Apply a term homomorphism recursively to a term/context.

appHom' :: forall f g. HDifunctor 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 :: (HDifunctor g, HDifunctor h) => Hom g h -> Hom f g -> Hom f h Source #

Compose two term homomorphisms.

appSigFun :: forall f g. HDifunctor f => SigFun f g -> CxtFun f g Source #

This function applies a signature function to the given context.

appSigFun' :: forall f g. HDifunctor g => SigFun f g -> CxtFun f g Source #

This function applies a signature function to the given context.

compSigFun :: SigFun g h -> SigFun f g -> SigFun f h Source #

This function composes two signature functions.

hom :: HDifunctor g => SigFun f g -> Hom f g Source #

Lifts the given signature function to the canonical term homomorphism.

compAlg :: (HDifunctor f, HDifunctor g) => Alg g a -> Hom f g -> Alg f a Source #

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.

type HomM m f g = SigFunM m f (Cxt Hole g) Source #

This type represents a monadic term homomorphism.

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' :: (HDifunctor f, HDifunctor 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 g m. (HDitraversable f, Monad m, HDifunctor g) => HomM m f g -> CxtFunM m f g Source #

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

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

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

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

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

Compose two monadic term homomorphisms.

compSigFunM :: Monad m => SigFunM m g h -> SigFunM m f g -> SigFunM m f h Source #

This function composes two monadic signature functions.

compAlgM :: (HDitraversable 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' :: (HDitraversable 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.