free-algebras-0.0.8.1: Free algebras

Control.Algebra.Free

Synopsis

# Documentation

class FreeAlgebra1 (m :: (k -> Type) -> k -> Type) where Source #

Higher kinded version of FreeAlgebra. Instances includes free functors, free applicative functors, free monads, state monads etc.

A lawful instance should guarantee that foldNatFree is an isomorphism with inverses unFoldNatFree.

This guaranties that m is a left adjoint functor from the category of types of kind Type -> Type which satisfy AlgebraType0 m constraint, to the category of types of kind Type -> Type which satisfy the AlgebraType m constraint. This functor is left adjoin to the forgetful functor (which is well defined if the laws on AlgebraType0 family are satisfied. This in turn guarantees that m composed with this forgetful functor is a monad. In result we get monadic operations:

For m such that AlgebraType0 subsumes Monad this class implies:

• MFunctor via hoist = hoistFree1
• MMonad via embed = flip bindFree1
• MonadTrans via lift = liftFree

Minimal complete definition

Methods

liftFree :: AlgebraType0 m f => f a -> m f a Source #

Natural transformation that embeds generators into m.

Arguments

 :: (AlgebraType m d, AlgebraType0 m f) => (forall x. f x -> d x) a natural transformation which embeds generators of m into d -> m f a -> d a a morphism from m f to d

The freeness property.

foldNatFree nat (liftFree m) = nat m
foldNatFree nat . foldNatFree nat' = foldNatFree (foldNatFree nat . nat')

codom1 :: forall f. AlgebraType0 m f => Proof (AlgebraType m (m f)) (m f) Source #

A proof that AlgebraType m (m f) holds for all AlgebraType0 f => f. Together with hoistFree1 this proves that FreeAlgebra m => m is a functor from the full subcategory of types of kind Type -> Type which satisfy AlgebraType0 m f to ones that satisfy AlgebraType m f.

codom1 :: forall a. AlgebraType m (m a) => Proof (AlgebraType m (m a)) (m a) Source #

A proof that AlgebraType m (m f) holds for all AlgebraType0 f => f. Together with hoistFree1 this proves that FreeAlgebra m => m is a functor from the full subcategory of types of kind Type -> Type which satisfy AlgebraType0 m f to ones that satisfy AlgebraType m f.

forget1 :: forall f. AlgebraType m f => Proof (AlgebraType0 m f) (m f) Source #

A proof that the forgetful functor from the full subcategory of types of kind Type -> Type satisfying AlgebraType m f constraint to types satisfying AlgebraType0 m f is well defined.

forget1 :: forall a. AlgebraType0 m a => Proof (AlgebraType0 m a) (m a) Source #

A proof that the forgetful functor from the full subcategory of types of kind Type -> Type satisfying AlgebraType m f constraint to types satisfying AlgebraType0 m f is well defined.

Instances

## Type level witnesses

data Proof (c :: Constraint) (a :: l) where Source #

A proof that constraint c holds for type a.

Constructors

 Proof :: c => Proof c a

## Higher algebra type / constraints

type family AlgebraType0 (f :: k) (a :: l) :: Constraint Source #

Type family which limits Hask to its full subcategory which satisfies a given constraints. Some free algebras, like free groups, or free abelian semigroups have additional constraints on on generators, like Eq or Ord.

Instances

type family AlgebraType (f :: k) (a :: l) :: Constraint Source #

Type family which for each free algebra m returns a type level lambda from types to constraints. It is describe the class of algebras for which this free algebra is free.

A lawful instance for this type family must guarantee that the constraint AlgebraType0 m f is implied by the AlgebraType m f constraint. This guarantees that there exists a forgetful functor from the category of types of kind * -> * which satisfy AlgebraType m constrain to the category of types of kind * -> * which satisfy the 'AlgebraType0 m constraint.

Instances

# Combinators

wrapFree :: forall (m :: (Type -> Type) -> Type -> Type) (f :: Type -> Type) a. (FreeAlgebra1 m, AlgebraType0 m f, Monad (m f)) => f (m f a) -> m f a Source #

Anything that carries FreeAlgebra1 constraint is also an instance of MonadFree, but not vice versa. You can use wrap to define a MonadFree instance. ContT is an example of a monad which does have an FreeAlgebra1 instance, but has an MonadFree instance.

The Monad constrain will be satisfied for many monads through the 'AlgebraType m' constraint.

foldFree1 :: forall m f a. (FreeAlgebra1 m, AlgebraType m f) => m f a -> f a Source #

FreeAlgebra1 m implies that m f is a foldable.

foldFree1 . liftFree == id :: f a -> f a

foldFree1 is the unit of the adjunction imposed by FreeAlgebra1 constraint.

It can be specialized to:

unFoldNatFree :: (FreeAlgebra1 m, AlgebraType0 m f) => (forall x. m f x -> d x) -> f a -> d a Source #

unFoldNatFree is an inverse of foldNatFree

It is uniquelly determined by its universal property (by Yonneda lemma):

unFoldNatFree id = ruturnFree1

Note that unFoldNatFree id is the unit of the adjunction imposed by the FreeAlgebra1 constraint.

Arguments

 :: (FreeAlgebra1 m, AlgebraType0 m g, AlgebraType0 m f) => (forall x. f x -> g x) a natural transformation f ~> g -> m f a -> m g a

This is a functor instance for m when considered as an endofuctor of some subcategory of Type -> Type (e.g. endofunctors of Hask) and it satisfies the functor laws:

hoistFree1 id = id
hoistFree1 f . hoistFree1 g = hoistFree1 (f . g)

It can be specialized to:

hoistFreeH :: forall m n f a. (FreeAlgebra1 m, FreeAlgebra1 n, AlgebraType0 m f, AlgebraType0 n f, AlgebraType m (n f)) => m f a -> n f a Source #

joinFree1 :: forall m f a. (FreeAlgebra1 m, AlgebraType0 m f) => m (m f) a -> m f a Source #

joinFree1 makes m a monad in some subcatgory of types of kind Type -> Type (usually the endo-functor category of Hask). It is just a specialization of foldFree1.

Arguments

 :: (FreeAlgebra1 m, AlgebraType0 m g, AlgebraType0 m f) => m f a -> (forall x. f x -> m g x) natural transformation f ~> m g -> m g a

Bind operator for the joinFree1 monad, this is just foldNatFree in disguise.

For StateT, WriterT or ReaderT (or any FreeAlgebra1 m => m such that AlgebraType0 m subsumes Monad m), this is the >>= version of Control.Monad.Morph.embed.

assocFree1 :: forall m f a. (FreeAlgebra1 m, AlgebraType m f, Functor (m (m f))) => m f (m f a) -> m (m f) (f a) Source #

iterFree1 :: forall m f a. (FreeAlgebra1 m, AlgebraType0 m f, AlgebraType m Identity) => (forall x. f x -> x) -> m f a -> a Source #

Specialization of foldNatFree @_ @Identity; it will further specialize to:

cataFree1 :: forall m f a. (FreeAlgebra1 m, AlgebraType m f, Monad f, Traversable (m f)) => Fix (m f) -> f a Source #

Fix (m f) is the initial algebra of type AlgebraType m and AlgebraType0 f.

# Day convolution

newtype DayF f a Source #

Day f f newtype wrapper. It is isomorphic with Ap f for applicative functors f via dayToAp (and apToDay).

Constructors

 DayF FieldsrunDayF :: Day f f a
Instances

# Various classes (higher algebra types)

Algebra type for ListT monad transformer.

Methods

mempty1 :: m a Source #

mappend1 :: m a -> m a -> m a Source #

Instances
 Monad m => MonadList (ListT m) Source # Instance detailsDefined in Control.Algebra.Free Methodsmempty1 :: ListT m a Source #mappend1 :: ListT m a -> ListT m a -> ListT m a Source #

class MonadMaybe m where Source #

A higher version Pointed class.

With QuantifiedConstraints this class will be redundant.

Methods

point :: forall a. m a Source #

Instances
 Monad m => MonadMaybe (MaybeT m :: Type -> Type) Source # Instance detailsDefined in Control.Algebra.Free Methodspoint :: MaybeT m a Source #