free-algebras-0.0.5.1: Free algebras in Haskell.

Safe HaskellSafe
LanguageHaskell2010

Data.Algebra.Free

Contents

Synopsis

Free algebra class

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

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, codom, 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)

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

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 #

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.

Instance details

Defined in Data.Algebra.Free

Methods

returnFree :: a -> [a] Source #

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

codom :: 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 Identity Source # 
Instance details

Defined in Data.Algebra.Free

FreeAlgebra NonEmpty Source #

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

Instance details

Defined in Data.Algebra.Free

FreeAlgebra DList Source #

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

Instance details

Defined in Data.Algebra.Free

FreeAlgebra FreeGroupL Source # 
Instance details

Defined in Data.Group.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

FreeAlgebra (Free Semigroup) Source # 
Instance details

Defined in Data.Algebra.Free

FreeAlgebra (Free Monoid) Source # 
Instance details

Defined in Data.Algebra.Free

FreeAlgebra (Free Group) Source # 
Instance details

Defined in Data.Algebra.Free

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

Defined in Data.Monoid.MSet

Type level witnesses

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

A proof that constraint c holds for type a.

Constructors

Proof (Dict c) 

proof :: c => Proof (c :: Constraint) (a :: l) Source #

Proof smart constructor.

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 Identity (a :: l) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType Identity (a :: l) = ()
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 DList (a :: *) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType DList (a :: *) = Monoid a
type AlgebraType FreeGroupL (g :: *) Source # 
Instance details

Defined in Data.Group.Free

type AlgebraType FreeGroupL (g :: *) = (Eq g, Group g)
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 (Free Semigroup) (a :: *) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType (Free Monoid) (a :: *) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType (Free Monoid) (a :: *) = Monoid a
type AlgebraType (Free Group) (a :: *) Source # 
Instance details

Defined in Data.Algebra.Free

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

Defined in Data.Monoid.MSet

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

Defined in Control.Algebra.Free

type AlgebraType MaybeT (m :: * -> *) = (Monad m, MonadMaybe m)
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 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 DList (a :: l) Source # 
Instance details

Defined in Data.Algebra.Free

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

Defined in Data.Algebra.Free

type AlgebraType0 Identity (a :: l) = ()
type AlgebraType0 (Free Group) (a :: l) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType0 (Free Group) (a :: l) = ()
type AlgebraType0 (Free Monoid) (a :: l) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType0 (Free Monoid) (a :: l) = ()
type AlgebraType0 (Free Semigroup) (a :: l) Source # 
Instance details

Defined in Data.Algebra.Free

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

Defined in Data.Monoid.MSet

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

Defined in Data.Group.Free

type AlgebraType0 FreeGroupL (a :: *) = Eq a
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 MaybeT (m :: * -> *) Source # 
Instance details

Defined in Control.Algebra.Free

type AlgebraType0 MaybeT (m :: * -> *) = Monad m
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 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

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

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.

General free type

newtype Free c a Source #

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

Defined in Data.Algebra.Free

FreeAlgebra (Free Monoid) Source # 
Instance details

Defined in Data.Algebra.Free

FreeAlgebra (Free Group) Source # 
Instance details

Defined in Data.Algebra.Free

Semigroup (Free Semigroup a) Source # 
Instance details

Defined in Data.Algebra.Free

Semigroup (Free Monoid a) Source # 
Instance details

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

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

Defined in Data.Algebra.Free

Monoid (Free Group a) Source # 
Instance details

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

Defined in Data.Algebra.Free

Methods

invert :: Free Group a -> Free Group a #

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

type AlgebraType0 (Free Group) (a :: l) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType0 (Free Group) (a :: l) = ()
type AlgebraType0 (Free Monoid) (a :: l) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType0 (Free Monoid) (a :: l) = ()
type AlgebraType0 (Free Semigroup) (a :: l) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType0 (Free Semigroup) (a :: l) = ()
type AlgebraType (Free Semigroup) (a :: *) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType (Free Monoid) (a :: *) Source # 
Instance details

Defined in Data.Algebra.Free

type AlgebraType (Free Monoid) (a :: *) = Monoid a
type AlgebraType (Free Group) (a :: *) Source # 
Instance details

Defined in Data.Algebra.Free

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