Data.Algebra.Free

Free algebra class

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

A lawful instance has to guarantee that unFoldFree is an inverse of foldMapFree (in the category of algebras of type AlgebraType m).

This in turn guaranties that m is a left adjoint functor from full subcategory of Hask (of types constrained by AlgebraType0 m) 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

Methods

returnFree :: a -> m a

Injective map that embeds generators a into m.

foldMapFree

Arguments

:: forall d a. (AlgebraType m d, AlgebraType0 m a)

=> (a -> d)

a mapping of generators of m into d

-> m a -> d

a homomorphism from m a to d

The freeness property.

codom :: 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. (codom from codomain)

default codom :: forall a. AlgebraType m (m a) => Proof (AlgebraType m (m a)) (m a)

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.

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

Instances

FreeAlgebra []

Note that '[]' is a free monoid only for monoids which multiplication is strict in the left argument ref. Note that being strict adds additional equation to the monoid laws:

undefined <> a = undefined

Thus, expectedly we get an equational theory for left right two-sided strict monoids.

Snoc lists are free monoids in the class of monoids which are strict in the right argument, Free Monoid and @DList are free in the class of all Haskell monoids.

Defined in Data.Algebra.Free

Methods

returnFree :: a -> [a]

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

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

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

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

FreeAlgebra Identity

Defined in Data.Algebra.Free

Methods

returnFree :: a -> Identity a

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

codom :: AlgebraType0 Identity a => Proof (AlgebraType Identity (Identity a)) (Identity a)

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

FreeAlgebra NonEmpty

NonEmpty is the free semigroup in the class of semigroup which are strict in the left argument.

Defined in Data.Algebra.Free

Methods

returnFree :: a -> NonEmpty a

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

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

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

FreeAlgebra DList

DList is isomorphic to Free Monoid; it is free in the class of all monoids.

Defined in Data.Algebra.Free

Methods

returnFree :: a -> DList a

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

codom :: AlgebraType0 DList a => Proof (AlgebraType DList (DList a)) (DList a)

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

FreeAlgebra DNonEmpty

Defined in Data.Algebra.Free

Methods

returnFree :: a -> DNonEmpty a

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

codom :: AlgebraType0 DNonEmpty a => Proof (AlgebraType DNonEmpty (DNonEmpty a)) (DNonEmpty a)

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

FreeAlgebra FreeGroupL

Defined in Data.Group.Free

Methods

returnFree :: a -> FreeGroupL a

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

codom :: AlgebraType0 FreeGroupL a => Proof (AlgebraType FreeGroupL (FreeGroupL a)) (FreeGroupL a)

forget :: AlgebraType FreeGroupL a => Proof (AlgebraType0 FreeGroupL a) (FreeGroupL 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

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

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

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

codom :: AlgebraType0 FreeSemilattice a => Proof (AlgebraType FreeSemilattice (FreeSemilattice a)) (FreeSemilattice a)

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

FreeAlgebra (Free Semigroup)

Defined in Data.Algebra.Free

Methods

returnFree :: a -> Free Semigroup a

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

codom :: AlgebraType0 (Free Semigroup) a => Proof (AlgebraType (Free Semigroup) (Free Semigroup a)) (Free Semigroup a)

forget :: AlgebraType (Free Semigroup) a => Proof (AlgebraType0 (Free Semigroup) a) (Free Semigroup a)

FreeAlgebra (Free Monoid)

Defined in Data.Algebra.Free

Methods

returnFree :: a -> Free Monoid a

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

codom :: AlgebraType0 (Free Monoid) a => Proof (AlgebraType (Free Monoid) (Free Monoid a)) (Free Monoid a)

forget :: AlgebraType (Free Monoid) a => Proof (AlgebraType0 (Free Monoid) a) (Free Monoid a)

FreeAlgebra (Free Group)

Defined in Data.Algebra.Free

Methods

returnFree :: a -> Free Group a

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

codom :: AlgebraType0 (Free Group) a => Proof (AlgebraType (Free Group) (Free Group a)) (Free Group a)

forget :: AlgebraType (Free Group) a => Proof (AlgebraType0 (Free Group) a) (Free Group a)

Type level witnesses

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

A proof that constraint c holds for type a.

Constructors

Proof :: c => Proof c a

Algebra types / constraints

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 Identity (a :: l)

Defined in Data.Algebra.Free

type AlgebraType Identity (a :: l) = ()

type AlgebraType [] (m :: Type)

Defined in Data.Algebra.Free

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

type AlgebraType Maybe (m :: Type)

Defined in Data.Algebra.Free

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

type AlgebraType NonEmpty (m :: Type)

Defined in Data.Algebra.Free

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

type AlgebraType DList (a :: Type)

Defined in Data.Algebra.Free

type AlgebraType DList (a :: Type) = Monoid a

type AlgebraType DNonEmpty (m :: Type)

Defined in Data.Algebra.Free

type AlgebraType DNonEmpty (m :: Type) = Semigroup m

type AlgebraType FreeGroupL (g :: Type)

Defined in Data.Group.Free

type AlgebraType FreeGroupL (g :: Type) = (Eq g, Group g)

type AlgebraType FreeGroup (g :: Type)

Defined in Data.Group.Free

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

type AlgebraType FreeAbelianSemigroup (a :: Type)

Defined in Data.Semigroup.Abelian

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

type AlgebraType FreeAbelianMonoid (m :: Type)

Defined in Data.Monoid.Abelian

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

type AlgebraType FreeSemilattice (a :: Type)

Defined in Data.Semigroup.Semilattice

type AlgebraType FreeSemilattice (a :: Type)

type AlgebraType (Free Semigroup) (a :: Type)

Defined in Data.Algebra.Free

type AlgebraType (Free Semigroup) (a :: Type) = Semigroup a

type AlgebraType (Free Monoid) (a :: Type)

Defined in Data.Algebra.Free

type AlgebraType (Free Monoid) (a :: Type) = Monoid a

type AlgebraType (Free Group) (a :: Type)

Defined in Data.Algebra.Free

type AlgebraType (Free Group) (a :: Type) = Group a

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

type AlgebraType (Free1 c :: (Type -> Type) -> Type -> Type) (f :: Type -> Type)

Defined in Control.Algebra.Free

type AlgebraType (Free1 c :: (Type -> Type) -> Type -> Type) (f :: Type -> Type) = c f

type AlgebraType (FreeMAction m :: (Type -> Type) -> Type -> Type) (f :: Type -> Type)

Defined in Control.Monad.Action

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

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

Defined in Control.Algebra.Free

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

type AlgebraType (ReaderT r :: (Type -> Type) -> Type -> Type) (m :: Type -> Type)

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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)

Algebras of the same type as Coyoneda are all functors.

Defined in Control.Algebra.Free

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

type AlgebraType0 DList (a :: l)

Defined in Data.Algebra.Free

type AlgebraType0 DList (a :: 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 Identity (a :: l)

Defined in Data.Algebra.Free

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

type AlgebraType0 DNonEmpty (a :: l)

Defined in Data.Algebra.Free

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

type AlgebraType0 (Free1 c :: (Type -> Type) -> Type -> Type) (f :: l)

Defined in Control.Algebra.Free

type AlgebraType0 (Free1 c :: (Type -> Type) -> Type -> Type) (f :: l) = ()

type AlgebraType0 (Free Group) (a :: l)

Defined in Data.Algebra.Free

type AlgebraType0 (Free Group) (a :: l) = ()

type AlgebraType0 (Free Monoid) (a :: l)

Defined in Data.Algebra.Free

type AlgebraType0 (Free Monoid) (a :: l) = ()

type AlgebraType0 (Free Semigroup) (a :: l)

Defined in Data.Algebra.Free

type AlgebraType0 (Free Semigroup) (a :: l) = ()

type AlgebraType0 FreeGroupL (a :: Type)

Defined in Data.Group.Free

type AlgebraType0 FreeGroupL (a :: Type) = Eq a

type AlgebraType0 FreeGroup (a :: Type)

Defined in Data.Group.Free

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

type AlgebraType0 FreeAbelianSemigroup (a :: Type)

Defined in Data.Semigroup.Abelian

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

type AlgebraType0 FreeAbelianMonoid (a :: Type)

Defined in Data.Monoid.Abelian

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

type AlgebraType0 FreeSemilattice (a :: Type)

Defined in Data.Semigroup.Semilattice

type AlgebraType0 FreeSemilattice (a :: Type) = Ord a

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Algebras of the same type as Free monad is the class of all monads.

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Algebras of the same type as Ap are the applicative functors.

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Algebras of the same type as DayF are all the applicative functors.

Defined in Control.Algebra.Free

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

type AlgebraType0 (FreeMAction m :: (Type -> Type) -> Type -> Type) (f :: Type -> Type)

Defined in Control.Monad.Action

type AlgebraType0 (FreeMAction m :: (Type -> Type) -> Type -> Type) (f :: Type -> Type) = Functor f

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

Algebras of the same type as ReaderT monad is the class of all reader monads.

Defined in Control.Algebra.Free

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

type AlgebraType0 (ReaderT r :: (Type -> Type) -> Type -> Type) (m :: Type -> Type)

Algebras of the same type as ReaderT monad is the class of all reader monads.

TODO: take advantage of poly-kinded ReaderT

Defined in Control.Algebra.Free

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

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

Algebras of the same type as StateT monad is the class of all state monads.

Defined in Control.Algebra.Free

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

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

Algebras of the same type as StateT monad is the class of all state monads.

Defined in Control.Algebra.Free

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

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

Algebras of the same type as WriterT monad is the class of all writer monads.

Defined in Control.Algebra.Free

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

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

Algebras of the same type as WriterT monad is the class of all writer monads.

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

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

Defined in Control.Algebra.Free

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

Combinators

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

Inverse of foldMapFree

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

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.

Examples:

foldFree @[] = foldMap id
             = foldr (<>) mempty
foldFree @NonEmpty
             = foldr1 (<>)

Note that foldFree replaces the abstract / free algebraic operation in m a to concrete one in a.

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 (the initial algebra is a free algebra generated by empty set of generators, e.g. the Viod type).

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 (_ -> []).

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

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

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

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

Like foldlFree but strict.

General free type

newtype Free (c :: Type -> Constraint) a

Free c a represents free algebra for a constraint c generated by type a.

Constructors

Free

Fields

• runFree :: forall r. c r => (a -> r) -> r

Instances

FreeAlgebra (Free Semigroup)

Defined in Data.Algebra.Free

Methods

returnFree :: a -> Free Semigroup a

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

codom :: AlgebraType0 (Free Semigroup) a => Proof (AlgebraType (Free Semigroup) (Free Semigroup a)) (Free Semigroup a)

forget :: AlgebraType (Free Semigroup) a => Proof (AlgebraType0 (Free Semigroup) a) (Free Semigroup a)

FreeAlgebra (Free Monoid)

Defined in Data.Algebra.Free

Methods

returnFree :: a -> Free Monoid a

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

codom :: AlgebraType0 (Free Monoid) a => Proof (AlgebraType (Free Monoid) (Free Monoid a)) (Free Monoid a)

forget :: AlgebraType (Free Monoid) a => Proof (AlgebraType0 (Free Monoid) a) (Free Monoid a)

FreeAlgebra (Free Group)

Defined in Data.Algebra.Free

Methods

returnFree :: a -> Free Group a

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

codom :: AlgebraType0 (Free Group) a => Proof (AlgebraType (Free Group) (Free Group a)) (Free Group a)

forget :: AlgebraType (Free Group) a => Proof (AlgebraType0 (Free Group) a) (Free Group a)

Semigroup (Free Semigroup a)

Defined in Data.Algebra.Free

Methods

(<>) :: Free Semigroup a -> Free Semigroup a -> Free Semigroup a

sconcat :: NonEmpty (Free Semigroup a) -> Free Semigroup a

stimes :: Integral b => b -> Free Semigroup a -> Free Semigroup a

Semigroup (Free Monoid a)

Defined in Data.Algebra.Free

Methods

(<>) :: Free Monoid a -> Free Monoid a -> Free Monoid a

sconcat :: NonEmpty (Free Monoid a) -> Free Monoid a

stimes :: Integral b => b -> Free Monoid a -> Free Monoid a

Semigroup (Free Group a)

Defined in Data.Algebra.Free

Methods

(<>) :: Free Group a -> Free Group a -> Free Group a

sconcat :: NonEmpty (Free Group a) -> Free Group a

stimes :: Integral b => b -> Free Group a -> Free Group a

Monoid (Free Monoid a)

Defined in Data.Algebra.Free

Methods

mempty :: Free Monoid a

mappend :: Free Monoid a -> Free Monoid a -> Free Monoid a

mconcat :: [Free Monoid a] -> Free Monoid a

Monoid (Free Group a)

Defined in Data.Algebra.Free

Methods

mempty :: Free Group a

mappend :: Free Group a -> Free Group a -> Free Group a

mconcat :: [Free Group a] -> Free Group a

Group (Free Group a)

Defined in Data.Algebra.Free

Methods

invert :: Free Group a -> Free Group a

(~~) :: Free Group a -> Free Group a -> Free Group a

pow :: Integral x => Free Group a -> x -> Free Group a

type AlgebraType0 (Free Group) (a :: l)

Defined in Data.Algebra.Free

type AlgebraType0 (Free Group) (a :: l) = ()

type AlgebraType0 (Free Monoid) (a :: l)

Defined in Data.Algebra.Free

type AlgebraType0 (Free Monoid) (a :: l) = ()

type AlgebraType0 (Free Semigroup) (a :: l)

Defined in Data.Algebra.Free

type AlgebraType0 (Free Semigroup) (a :: l) = ()

type AlgebraType (Free Semigroup) (a :: Type)

Defined in Data.Algebra.Free

type AlgebraType (Free Semigroup) (a :: Type) = Semigroup a

type AlgebraType (Free Monoid) (a :: Type)

Defined in Data.Algebra.Free

type AlgebraType (Free Monoid) (a :: Type) = Monoid a

type AlgebraType (Free Group) (a :: Type)

Defined in Data.Algebra.Free

type AlgebraType (Free Group) (a :: Type) = Group a

newtype DNonEmpty a

DNonEmpty is the free semigroup ihn the class of all semigroups.

Constructors

DNonEmpty ([a] -> NonEmpty a)

Instances

FreeAlgebra DNonEmpty

Defined in Data.Algebra.Free

Methods

returnFree :: a -> DNonEmpty a

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

codom :: AlgebraType0 DNonEmpty a => Proof (AlgebraType DNonEmpty (DNonEmpty a)) (DNonEmpty a)

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

Semigroup (DNonEmpty a)

Defined in Data.Algebra.Free

Methods

(<>) :: DNonEmpty a -> DNonEmpty a -> DNonEmpty a

sconcat :: NonEmpty (DNonEmpty a) -> DNonEmpty a

stimes :: Integral b => b -> DNonEmpty a -> DNonEmpty a

type AlgebraType0 DNonEmpty (a :: l)

Defined in Data.Algebra.Free

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

type AlgebraType DNonEmpty (m :: Type)

Defined in Data.Algebra.Free

type AlgebraType DNonEmpty (m :: Type) = Semigroup m