free-algebras-0.0.4.0: Free algebras in Haskell.

Safe HaskellSafe
LanguageHaskell2010

Data.Algebra.Free

Contents

Synopsis

Algebra type

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
type AlgebraType [] (m :: *) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType [] (m :: *) = Monoid m
type AlgebraType Maybe (m :: *) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType Maybe (m :: *) = Pointed m
type AlgebraType NonEmpty (m :: *) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType FreeGroup (g :: *) Source # 
Instance details

Defined in Data.Group.Free

type AlgebraType FreeGroup (g :: *) = (Eq g, Group g)
type AlgebraType FreeAbelianSemigroup (a :: *) Source # 
Instance details

Defined in Data.Semigroup.Abelian

type AlgebraType FreeAbelianMonoid (m :: *) Source # 
Instance details

Defined in Data.Monoid.Abelian

type AlgebraType FreeSemiLattice (a :: *) Source # 
Instance details

Defined in Data.Semigroup.SemiLattice

type AlgebraType (FreeMSet m :: * -> *) (a :: *) Source # 
Instance details

Defined in Data.Monoid.MSet

type AlgebraType (FreeMSet m :: * -> *) (a :: *) = MSet m a
type AlgebraType F (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType F (m :: * -> *) = Monad m
type AlgebraType Free (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType Free (m :: * -> *) = Monad m
type AlgebraType Ap (g :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType Ap (g :: * -> *) = Applicative g
type AlgebraType Ap (g :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType Ap (g :: * -> *) = Applicative g
type AlgebraType Ap (g :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType Ap (g :: * -> *) = Applicative g
type AlgebraType Alt (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType Alt (m :: * -> *) = Alternative m
type AlgebraType Coyoneda (g :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType Coyoneda (g :: * -> *) = Functor g
type AlgebraType ListT (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType ListT (m :: * -> *) = MonadList m
type AlgebraType MaybeT (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType MaybeT (m :: * -> *) = (Monad m, MonadMaybe m)
type AlgebraType DayF (g :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType DayF (g :: * -> *) = Applicative g
type AlgebraType (ExceptT e :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType (ExceptT e :: (* -> *) -> * -> *) (m :: * -> *) = MonadError e m
type AlgebraType (StateT s :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType (StateT s :: (* -> *) -> * -> *) (m :: * -> *) = MonadState s m
type AlgebraType (StateT s :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType (StateT s :: (* -> *) -> * -> *) (m :: * -> *) = MonadState s m
type AlgebraType (WriterT w :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType (WriterT w :: (* -> *) -> * -> *) (m :: * -> *) = MonadWriter w m
type AlgebraType (WriterT w :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType (WriterT w :: (* -> *) -> * -> *) (m :: * -> *) = MonadWriter w m
type AlgebraType (ReaderT r :: (k -> *) -> k -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType (ReaderT r :: (k -> *) -> k -> *) (m :: * -> *) = MonadReader r m
type AlgebraType (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *) = MonadRWS r w s m
type AlgebraType (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *) = MonadRWS r w s m
type AlgebraType (FreeMAction m :: (k -> *) -> k -> *) (f :: * -> *) Source # 
Instance details

Defined in Control.Monad.Action

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

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 AlgebraType0 Coyoneda (g :: l) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 Coyoneda (g :: l) = ()
type AlgebraType0 Maybe (a :: l) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType0 Maybe (a :: l) = ()
type AlgebraType0 [] (a :: l) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType0 [] (a :: l) = ()
type AlgebraType0 NonEmpty (a :: l) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType0 NonEmpty (a :: l) = ()
type AlgebraType0 (FreeMSet m :: * -> *) (a :: l) Source # 
Instance details

Defined in Data.Monoid.MSet

type AlgebraType0 (FreeMSet m :: * -> *) (a :: l) = ()
type AlgebraType0 FreeGroup (a :: *) Source # 
Instance details

Defined in Data.Group.Free

type AlgebraType0 FreeGroup (a :: *) = Eq a
type AlgebraType0 FreeAbelianSemigroup (a :: *) Source # 
Instance details

Defined in Data.Semigroup.Abelian

type AlgebraType0 FreeAbelianMonoid (a :: *) Source # 
Instance details

Defined in Data.Monoid.Abelian

type AlgebraType0 FreeSemiLattice (a :: *) Source # 
Instance details

Defined in Data.Semigroup.SemiLattice

type AlgebraType0 F (f :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 F (f :: * -> *) = Functor f
type AlgebraType0 Free (f :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 Free (f :: * -> *) = Functor f
type AlgebraType0 Ap (g :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 Ap (g :: * -> *) = Functor g
type AlgebraType0 Ap (g :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 Ap (g :: * -> *) = Functor g
type AlgebraType0 Ap (g :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 Ap (g :: * -> *) = Functor g
type AlgebraType0 Alt (f :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 Alt (f :: * -> *) = Functor f
type AlgebraType0 ListT (f :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 ListT (f :: * -> *) = Monad f
type AlgebraType0 MaybeT (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 MaybeT (m :: * -> *) = Monad m
type AlgebraType0 DayF (g :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 DayF (g :: * -> *) = Applicative g
type AlgebraType0 (ExceptT e :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 (ExceptT e :: (* -> *) -> * -> *) (m :: * -> *) = Monad m
type AlgebraType0 (StateT s :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 (StateT s :: (* -> *) -> * -> *) (m :: * -> *) = Monad m
type AlgebraType0 (StateT s :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 (StateT s :: (* -> *) -> * -> *) (m :: * -> *) = Monad m
type AlgebraType0 (WriterT w :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 (WriterT w :: (* -> *) -> * -> *) (m :: * -> *) = (Monad m, Monoid w)
type AlgebraType0 (WriterT w :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 (WriterT w :: (* -> *) -> * -> *) (m :: * -> *) = (Monad m, Monoid w)
type AlgebraType0 (ReaderT r :: (k -> *) -> k -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 (ReaderT r :: (k -> *) -> k -> *) (m :: * -> *) = Monad m
type AlgebraType0 (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

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

Defined in Control.Algebra.Free

type AlgebraType0 (RWST r w s :: (* -> *) -> * -> *) (m :: * -> *) = (Monad m, Monoid w)
type AlgebraType0 (FreeMAction m :: (k2 -> k1) -> k2 -> *) (f :: * -> *) Source # 
Instance details

Defined in Control.Monad.Action

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

FreeAlgebra class

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

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

Injective map that embeds generators a into m.

foldMapFree Source #

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

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

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

Instances
FreeAlgebra [] Source # 
Instance details

Defined in Data.Algebra.Free

Methods

returnFree :: a -> [a] Source #

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

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

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

FreeAlgebra Maybe Source # 
Instance details

Defined in Data.Algebra.Free

FreeAlgebra NonEmpty Source # 
Instance details

Defined in Data.Algebra.Free

FreeAlgebra FreeGroup Source # 
Instance details

Defined in Data.Group.Free

FreeAlgebra FreeAbelianSemigroup Source # 
Instance details

Defined in Data.Semigroup.Abelian

FreeAlgebra FreeAbelianMonoid Source # 
Instance details

Defined in Data.Monoid.Abelian

FreeAlgebra FreeSemiLattice Source # 
Instance details

Defined in Data.Semigroup.SemiLattice

Monoid m => FreeAlgebra (FreeMSet m) Source # 
Instance details

Defined in Data.Monoid.MSet

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

A proof that constraint c holds for type a.

Constructors

Proof (Dict c) 

Combinators

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

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

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

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

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

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

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

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.

foldrFree :: forall m a b. (FreeAlgebra m, AlgebraType m (Endo b), AlgebraType0 m a) => (a -> b -> b) -> b -> m a -> b Source #

A version of foldr, e.g. it can specialize to

  • foldrFree @[] :: (a -> b -> b) -> [a] -> b -> b
  • foldrFree @NonEmpty :: (a -> b -> b) -> NonEmpty a -> b -> b

foldrFree' :: forall m a b. (FreeAlgebra m, AlgebraType m (Dual (Endo (b -> b))), AlgebraType0 m a) => (a -> b -> b) -> m a -> b -> b Source #

Like foldrFree but strict.

foldlFree :: forall m a b. (FreeAlgebra m, AlgebraType m (Dual (Endo b)), AlgebraType0 m a) => (b -> a -> b) -> b -> m a -> b Source #

Generalizes foldl, e.g. it can specialize to

  • foldlFree @[] :: (b -> a -> b) -> b -> [a] -> b
  • foldlFree @NonEmpty :: (b -> a -> b) -> b -> NonEmpty a -> b

foldlFree' :: forall m a b. (FreeAlgebra m, AlgebraType m (Endo (b -> b)), AlgebraType0 m a) => (b -> a -> b) -> b -> m a -> b Source #

Like foldlFree but strict.