Data.Algebra.Free

Algebra type

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

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

type AlgebraType [] (m :: *)

Defined in Data.Algebra.Free

type AlgebraType [] (m :: *) = Monoid m

type AlgebraType Maybe (m :: *)

Defined in Data.Algebra.Free

type AlgebraType Maybe (m :: *) = Pointed m

type AlgebraType NonEmpty (m :: *)

Defined in Data.Algebra.Free

type AlgebraType NonEmpty (m :: *) = Semigroup m

type AlgebraType FreeGroup (g :: *)

Defined in Data.Group.Free

type AlgebraType FreeGroup (g :: *) = (Eq g, Group g)

type AlgebraType FreeAbelianSemigroup (a :: *)

Defined in Data.Semigroup.Abelian

type AlgebraType FreeAbelianSemigroup (a :: *) = (Ord a, AbelianSemigroup a)

type AlgebraType FreeAbelianMonoid (m :: *)

Defined in Data.Monoid.Abelian

type AlgebraType FreeAbelianMonoid (m :: *) = (Ord m, Monoid m, AbelianSemigroup m)

type AlgebraType FreeSemiLattice (a :: *)

Defined in Data.Semigroup.SemiLattice

type AlgebraType FreeSemiLattice (a :: *)

type AlgebraType (FreeMSet m :: * -> *) (a :: *)

Defined in Data.Monoid.MSet

type AlgebraType (FreeMSet m :: * -> *) (a :: *) = MSet m a

type AlgebraType MaybeT (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType MaybeT (m :: * -> *) = (Monad m, MonadMaybe m)

type AlgebraType F (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType F (m :: * -> *) = Monad m

type AlgebraType Free (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType Free (m :: * -> *) = Monad m

type AlgebraType Ap (g :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType Ap (g :: * -> *) = Applicative g

type AlgebraType Ap (g :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType Ap (g :: * -> *) = Applicative g

type AlgebraType Ap (g :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType Ap (g :: * -> *) = Applicative g

type AlgebraType Alt (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType Alt (m :: * -> *) = Alternative m

type AlgebraType Coyoneda (g :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType Coyoneda (g :: * -> *) = Functor g

type AlgebraType ListT (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType ListT (m :: * -> *) = MonadList m

type AlgebraType DayF (g :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType DayF (g :: * -> *) = Applicative g

type AlgebraType (ExceptT e :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType (ExceptT e :: (* -> *) -> * -> *) (m :: * -> *) = MonadError e m

type AlgebraType (StateT s :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType (StateT s :: (* -> *) -> * -> *) (m :: * -> *) = MonadState s m

type AlgebraType (StateT s :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType (StateT s :: (* -> *) -> * -> *) (m :: * -> *) = MonadState s m

type AlgebraType (WriterT w :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType (WriterT w :: (* -> *) -> * -> *) (m :: * -> *) = MonadWriter w m

type AlgebraType (WriterT w :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType (WriterT w :: (* -> *) -> * -> *) (m :: * -> *) = MonadWriter w m

type AlgebraType (ReaderT r :: (k -> *) -> k -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType (ReaderT r :: (k -> *) -> k -> *) (m :: * -> *) = MonadReader r m

type AlgebraType (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *) = MonadRWS r w s m

type AlgebraType (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *) = MonadRWS r w s m

type AlgebraType (FreeMAction m :: (k -> *) -> k -> *) (f :: * -> *)

Defined in Control.Monad.Action

type AlgebraType (FreeMAction m :: (k -> *) -> k -> *) (f :: * -> *) = MAction m f

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

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 AlgebraType0 Coyoneda (g :: l)

Defined in Control.Algebra.Free

type AlgebraType0 Coyoneda (g :: l) = ()

type AlgebraType0 Maybe (a :: l)

Defined in Data.Algebra.Free

type AlgebraType0 Maybe (a :: l) = ()

type AlgebraType0 [] (a :: l)

Defined in Data.Algebra.Free

type AlgebraType0 [] (a :: l) = ()

type AlgebraType0 NonEmpty (a :: l)

Defined in Data.Algebra.Free

type AlgebraType0 NonEmpty (a :: l) = ()

type AlgebraType0 (FreeMSet m :: * -> *) (a :: l)

Defined in Data.Monoid.MSet

type AlgebraType0 (FreeMSet m :: * -> *) (a :: l) = ()

type AlgebraType0 FreeGroup (a :: *)

Defined in Data.Group.Free

type AlgebraType0 FreeGroup (a :: *) = Eq a

type AlgebraType0 FreeAbelianSemigroup (a :: *)

Defined in Data.Semigroup.Abelian

type AlgebraType0 FreeAbelianSemigroup (a :: *) = Ord a

type AlgebraType0 FreeAbelianMonoid (a :: *)

Defined in Data.Monoid.Abelian

type AlgebraType0 FreeAbelianMonoid (a :: *) = Ord a

type AlgebraType0 FreeSemiLattice (a :: *)

Defined in Data.Semigroup.SemiLattice

type AlgebraType0 FreeSemiLattice (a :: *) = Ord a

type AlgebraType0 MaybeT (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 MaybeT (m :: * -> *) = Monad m

type AlgebraType0 F (f :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 F (f :: * -> *) = Functor f

type AlgebraType0 Free (f :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 Free (f :: * -> *) = Functor f

type AlgebraType0 Ap (g :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 Ap (g :: * -> *) = Functor g

type AlgebraType0 Ap (g :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 Ap (g :: * -> *) = Functor g

type AlgebraType0 Ap (g :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 Ap (g :: * -> *) = Functor g

type AlgebraType0 Alt (f :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 Alt (f :: * -> *) = Functor f

type AlgebraType0 ListT (f :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 ListT (f :: * -> *) = Monad f

type AlgebraType0 DayF (g :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 DayF (g :: * -> *) = Applicative g

type AlgebraType0 (ExceptT e :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 (ExceptT e :: (* -> *) -> * -> *) (m :: * -> *) = Monad m

type AlgebraType0 (StateT s :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 (StateT s :: (* -> *) -> * -> *) (m :: * -> *) = Monad m

type AlgebraType0 (StateT s :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 (StateT s :: (* -> *) -> * -> *) (m :: * -> *) = Monad m

type AlgebraType0 (WriterT w :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 (WriterT w :: (* -> *) -> * -> *) (m :: * -> *) = (Monad m, Monoid w)

type AlgebraType0 (WriterT w :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 (WriterT w :: (* -> *) -> * -> *) (m :: * -> *) = (Monad m, Monoid w)

type AlgebraType0 (ReaderT r :: (k -> *) -> k -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 (ReaderT r :: (k -> *) -> k -> *) (m :: * -> *) = Monad m

type AlgebraType0 (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *) = (Monad m, Monoid w)

type AlgebraType0 (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *)

Defined in Control.Algebra.Free

type AlgebraType0 (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *) = (Monad m, Monoid w)

type AlgebraType0 (FreeMAction m :: (k2 -> k1) -> k2 -> *) (f :: * -> *)

Defined in Control.Monad.Action

type AlgebraType0 (FreeMAction m :: (k2 -> k1) -> k2 -> *) (f :: * -> *) = Functor f

FreeAlgebra class

class FreeAlgebra (m :: Type -> Type) where

A lawful instance has to guarantee that unFoldFree is an inverse of foldMapFree.

This in turn guaranties that m is a left adjoint functor from Hask to algebras of type 'AlgebraType m'. The right adjoint is the forgetful functor. The composition of left adjoin and the right one is always a monad, this is why we will be able to build monad instance for m.

Minimal complete definition

returnFree, foldMapFree, proof, forget

Methods

returnFree :: a -> m a

Injective map that embeds generators a into m.

foldMapFree

Arguments

:: (AlgebraType m d, AlgebraType0 m a)

=> (a -> d)

map generators of m into d

-> m a -> d

returns a homomorphism from m a to d

The freeness property.

proof :: forall a. AlgebraType0 m a => Proof (AlgebraType m (m a)) (m a)

Proof that AlgebraType0 m a => m a is an algebra of type AlgebraType m. This proves that m is a mapping from the full subcategory of Hask of types satisfying AlgebraType0 m a constraint to the full subcategory satisfying AlgebraType m a, fmapFree below proves that it's a functor.

forget :: forall a. AlgebraType m a => Proof (AlgebraType0 m a) (m a)

Proof that the forgetful functor from types a satisfying AgelbraType m a to AlgebraType0 m a is well defined.

Instances

FreeAlgebra []

Defined in Data.Algebra.Free

Methods

returnFree :: a -> [a]

foldMapFree :: (AlgebraType [] d, AlgebraType0 [] a) => (a -> d) -> [a] -> d

proof :: AlgebraType0 [] a => Proof (AlgebraType [] [a]) [a]

forget :: AlgebraType [] a => Proof (AlgebraType0 [] a) [a]

FreeAlgebra Maybe

Defined in Data.Algebra.Free

Methods

returnFree :: a -> Maybe a

foldMapFree :: (AlgebraType Maybe d, AlgebraType0 Maybe a) => (a -> d) -> Maybe a -> d

proof :: AlgebraType0 Maybe a => Proof (AlgebraType Maybe (Maybe a)) (Maybe a)

forget :: AlgebraType Maybe a => Proof (AlgebraType0 Maybe a) (Maybe a)

FreeAlgebra NonEmpty

Defined in Data.Algebra.Free

Methods

returnFree :: a -> NonEmpty a

foldMapFree :: (AlgebraType NonEmpty d, AlgebraType0 NonEmpty a) => (a -> d) -> NonEmpty a -> d

proof :: AlgebraType0 NonEmpty a => Proof (AlgebraType NonEmpty (NonEmpty a)) (NonEmpty a)

forget :: AlgebraType NonEmpty a => Proof (AlgebraType0 NonEmpty a) (NonEmpty a)

FreeAlgebra FreeGroup

Defined in Data.Group.Free

Methods

returnFree :: a -> FreeGroup a

foldMapFree :: (AlgebraType FreeGroup d, AlgebraType0 FreeGroup a) => (a -> d) -> FreeGroup a -> d

proof :: AlgebraType0 FreeGroup a => Proof (AlgebraType FreeGroup (FreeGroup a)) (FreeGroup a)

forget :: AlgebraType FreeGroup a => Proof (AlgebraType0 FreeGroup a) (FreeGroup a)

FreeAlgebra FreeAbelianSemigroup

Defined in Data.Semigroup.Abelian

Methods

returnFree :: a -> FreeAbelianSemigroup a

foldMapFree :: (AlgebraType FreeAbelianSemigroup d, AlgebraType0 FreeAbelianSemigroup a) => (a -> d) -> FreeAbelianSemigroup a -> d

proof :: AlgebraType0 FreeAbelianSemigroup a => Proof (AlgebraType FreeAbelianSemigroup (FreeAbelianSemigroup a)) (FreeAbelianSemigroup a)

forget :: AlgebraType FreeAbelianSemigroup a => Proof (AlgebraType0 FreeAbelianSemigroup a) (FreeAbelianSemigroup a)

FreeAlgebra FreeAbelianMonoid

Defined in Data.Monoid.Abelian

Methods

returnFree :: a -> FreeAbelianMonoid a

foldMapFree :: (AlgebraType FreeAbelianMonoid d, AlgebraType0 FreeAbelianMonoid a) => (a -> d) -> FreeAbelianMonoid a -> d

proof :: AlgebraType0 FreeAbelianMonoid a => Proof (AlgebraType FreeAbelianMonoid (FreeAbelianMonoid a)) (FreeAbelianMonoid a)

forget :: AlgebraType FreeAbelianMonoid a => Proof (AlgebraType0 FreeAbelianMonoid a) (FreeAbelianMonoid a)

FreeAlgebra FreeSemiLattice

Defined in Data.Semigroup.SemiLattice

Methods

returnFree :: a -> FreeSemiLattice a

foldMapFree :: (AlgebraType FreeSemiLattice d, AlgebraType0 FreeSemiLattice a) => (a -> d) -> FreeSemiLattice a -> d

proof :: AlgebraType0 FreeSemiLattice a => Proof (AlgebraType FreeSemiLattice (FreeSemiLattice a)) (FreeSemiLattice a)

forget :: AlgebraType FreeSemiLattice a => Proof (AlgebraType0 FreeSemiLattice a) (FreeSemiLattice a)

Monoid m => FreeAlgebra (FreeMSet m)

Defined in Data.Monoid.MSet

Methods

returnFree :: a -> FreeMSet m a

foldMapFree :: (AlgebraType (FreeMSet m) d, AlgebraType0 (FreeMSet m) a) => (a -> d) -> FreeMSet m a -> d

proof :: AlgebraType0 (FreeMSet m) a => Proof (AlgebraType (FreeMSet m) (FreeMSet m a)) (FreeMSet m a)

forget :: AlgebraType (FreeMSet m) a => Proof (AlgebraType0 (FreeMSet m) a) (FreeMSet m a)

newtype Proof (c :: Constraint) (a :: l)

A proof that constraint c holds for type a.

Constructors

Proof (Dict c)

Combinators

unFoldMapFree :: FreeAlgebra m => (m a -> d) -> a -> d

Inverse of foldMapFree

unFoldMapFree id = returnFree

Note that unFoldMapFree id is the unit of the unit of the adjunction imposed by the FreeAlgebra constraint.

foldFree :: forall m a. (FreeAlgebra m, AlgebraType m a) => m a -> a

All types which satisfy FreeAlgebra constraint are foldable.

foldFree . returnFree == id

foldFree is the unit of the adjunction imposed by FreeAlgebra constraint.

natFree :: forall m n a. (FreeAlgebra m, FreeAlgebra n, AlgebraType0 m a, AlgebraType m (n a)) => m a -> n a

The canonical quotient map from a free algebra of a wider class to a free algebra of a narrower class, e.g. from a free semigroup to free monoid, or from a free monoid to free commutative monoid, etc.

natFree . natFree == natFree

fmapFree f . natFree == hoistFree . fmapFree f

the constraints: * the algebra n a is of the same type as algebra m (this is always true, just ghc cannot prove it here) * m is a free algebra generated by a * n is a free algebra generated by a

fmapFree :: forall m a b. (FreeAlgebra m, AlgebraType0 m a, AlgebraType0 m b) => (a -> b) -> m a -> m b

All types which satisfy FreeAlgebra constraint are functors. The constraint AlgebraType m (m b) is always satisfied.

joinFree :: forall m a. (FreeAlgebra m, AlgebraType0 m a) => m (m a) -> m a

FreeAlgebra constraint implies Monad constrain.

bindFree :: forall m a b. (FreeAlgebra m, AlgebraType0 m a, AlgebraType0 m b) => m a -> (a -> m b) -> m b

The monadic bind operator. returnFree is the corresponding return for this monad. This just foldMapFree in disguise.

cataFree :: (FreeAlgebra m, AlgebraType m a, Functor m) => Fix m -> a

Fix m is the initial algebra in the category of algebras of type AlgebraType m, whenever it exists.

Another way of putting this is observing that Fix m is isomorphic to m Void where m is the free algebra. This isomorphisms is given by fixToFree :: (FreeAlgebra m, AlgebraType m (m Void), Functor m) => Fix m -> m Void fixToFree = cataFree For monoids the inverse is given by ana (_ -> []). The category of semigroups, however, does not have the initial object.