free-algebras-0.0.4.0: Free algebras in Haskell.

Data.Algebra.Free

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

# 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

Methods

returnFree :: a -> m a Source #

Injective map that embeds generators a into m.

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
 Source # Instance detailsDefined in Data.Algebra.Free MethodsreturnFree :: 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 # Source # Instance detailsDefined in Data.Algebra.Free MethodsreturnFree :: a -> Maybe a Source #foldMapFree :: (AlgebraType Maybe d, AlgebraType0 Maybe a) => (a -> d) -> Maybe a -> d Source #proof :: AlgebraType0 Maybe a => Proof (AlgebraType Maybe (Maybe a)) (Maybe a) Source # Source # Instance detailsDefined in Data.Algebra.Free MethodsreturnFree :: a -> NonEmpty a Source #foldMapFree :: (AlgebraType NonEmpty d, AlgebraType0 NonEmpty a) => (a -> d) -> NonEmpty a -> d Source # Source # Instance detailsDefined in Data.Group.Free MethodsreturnFree :: a -> FreeGroup a Source #foldMapFree :: (AlgebraType FreeGroup d, AlgebraType0 FreeGroup a) => (a -> d) -> FreeGroup a -> d Source # Source # Instance detailsDefined in Data.Semigroup.Abelian MethodsfoldMapFree :: (AlgebraType FreeAbelianSemigroup d, AlgebraType0 FreeAbelianSemigroup a) => (a -> d) -> FreeAbelianSemigroup a -> d Source # Source # Instance detailsDefined in Data.Monoid.Abelian MethodsfoldMapFree :: (AlgebraType FreeAbelianMonoid d, AlgebraType0 FreeAbelianMonoid a) => (a -> d) -> FreeAbelianMonoid a -> d Source # Source # Instance detailsDefined in Data.Semigroup.SemiLattice MethodsreturnFree :: a -> FreeSemiLattice a Source #foldMapFree :: (AlgebraType FreeSemiLattice d, AlgebraType0 FreeSemiLattice a) => (a -> d) -> FreeSemiLattice a -> d Source # Monoid m => FreeAlgebra (FreeMSet m) Source # Instance detailsDefined in Data.Monoid.MSet MethodsreturnFree :: a -> FreeMSet m a Source #foldMapFree :: (AlgebraType (FreeMSet m) d, AlgebraType0 (FreeMSet m) a) => (a -> d) -> FreeMSet m a -> d Source #proof :: AlgebraType0 (FreeMSet m) a => Proof (AlgebraType (FreeMSet m) (FreeMSet m a)) (FreeMSet m a) Source #forget :: AlgebraType (FreeMSet m) a => Proof (AlgebraType0 (FreeMSet m) a) (FreeMSet m a) Source #

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.