free-algebras 0.0.8.2 → 0.1.0.0
raw patch · 11 files changed
+205/−208 lines, 11 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
+ Data.Algebra.Free: DNonEmpty :: ([a] -> NonEmpty a) -> DNonEmpty a
+ Data.Algebra.Free: instance Data.Algebra.Free.FreeAlgebra Data.Algebra.Free.DNonEmpty
+ Data.Algebra.Free: instance GHC.Base.Semigroup (Data.Algebra.Free.DNonEmpty a)
+ Data.Algebra.Free: newtype DNonEmpty a
Files
- README.md +1/−1
- free-algebras.cabal +1/−1
- src/Control/Algebra/Free.hs +77/−82
- src/Control/Algebra/Free2.hs +23/−34
- src/Control/Monad/Action.hs +8/−8
- src/Data/Algebra/Free.hs +64/−50
- src/Data/Algebra/Pointed.hs +4/−4
- src/Data/Group/Free.hs +16/−15
- src/Data/Monoid/Abelian.hs +1/−2
- src/Data/Semigroup/Abelian.hs +6/−7
- src/Data/Semigroup/Semilattice.hs +4/−4
README.md view
@@ -5,7 +5,7 @@ Universal algebra approach (which is compatible with categorical approach) to free algebras (including higher order structures like functors, applicative functors or monads). Mathematical introduction alongside with some of the-Haskell ideas is exposed in this [blog](https://coot.me/posts/free-monads.html)+Haskell ideas is desribed in a [blog](https://coot.me/posts/free-monads.html) post. Examples:
free-algebras.cabal view
@@ -1,6 +1,6 @@ cabal-version: 2.0 name: free-algebras-version: 0.0.8.2+version: 0.1.0.0 synopsis: Free algebras description: Algebraic approach to free algebras, inspired by Univeral Algebra and
src/Control/Algebra/Free.hs view
@@ -98,8 +98,7 @@ import Data.Algebra.Free (AlgebraType, AlgebraType0, Proof (..)) --- |--- Higher kinded version of @'FreeAlgebra'@. Instances includes free functors,+-- | Higher kinded version of @'FreeAlgebra'@. Instances includes free functors, -- free applicative functors, free monads, state monads etc. -- -- A lawful instance should guarantee that @'foldNatFree'@ is an isomorphism@@ -122,6 +121,7 @@ -- * @MFunctor@ via @hoist = hoistFree1@ -- * @MMonad@ via @embed = flip bindFree1@ -- * @MonadTrans@ via @lift = liftFree@+-- class FreeAlgebra1 (m :: (k -> Type) -> k -> Type) where {-# MINIMAL liftFree, foldNatFree #-}@@ -144,30 +144,29 @@ -> (m f a -> d a) -- ^ a morphism from @m f@ to @d@ - -- |- -- A proof that @'AlgebraType' m (m f)@ holds for all @AlgebraType0 f => f@.+ -- | A proof that @'AlgebraType' m (m f)@ holds for all @AlgebraType0 f => f@. -- Together with @'hoistFree1'@ this proves that @FreeAlgebra m => m@ is -- a functor from the full subcategory of types of kind @Type -> Type@ -- which satisfy @'AlgebraType0' m f@ to ones that satisfy @'AlgebraType' -- m f@.+ -- codom1 :: forall f. AlgebraType0 m f => Proof (AlgebraType m (m f)) (m f) default codom1 :: forall a. AlgebraType m (m a) => Proof (AlgebraType m (m a)) (m a) codom1 = Proof - -- |- -- A proof that the forgetful functor from the full subcategory of types of+ -- | A proof that the forgetful functor from the full subcategory of types of -- kind @Type -> Type@ satisfying @'AlgebraType' m f@ constraint to types -- satisfying @'AlgebraType0' m f@ is well defined.+ -- forget1 :: forall f. AlgebraType m f => Proof (AlgebraType0 m f) (m f) default forget1 :: forall a. AlgebraType0 m a => Proof (AlgebraType0 m a) (m a) forget1 = Proof --- |--- Anything that carries @'FreeAlgebra1'@ constraint is also an instance of+-- | Anything that carries @'FreeAlgebra1'@ constraint is also an instance of -- @'Control.Monad.Free.Class.MonadFree'@, but not vice versa. You can use -- @'wrap'@ to define a @'Control.Monad.Free.Class.MonadFree'@ instance. -- @'ContT'@ is an example of a monad which does have an @'FreeAlgebra1'@@@ -175,6 +174,7 @@ -- -- The @'Monad'@ constrain will be satisfied for many monads through the -- @'AlgebraType m'@ constraint.+-- wrapFree :: forall (m :: (Type -> Type) -> Type -> Type) (f :: Type -> Type) @@ -188,8 +188,7 @@ wrapFree = join . liftFree {-# INLINABLE wrapFree #-} --- |--- @'FreeAlgebra1' m@ implies that @m f@ is a foldable.+-- | @'FreeAlgebra1' m@ implies that @m f@ is a foldable. -- -- @ -- 'foldFree1' . 'liftFree' == 'id' :: f a -> f a@@ -204,6 +203,7 @@ -- * @'Data.Functor.Coyoneda.lowerCoyoneda' :: 'Functor' f => 'Coyoneda' f a -> f a@ -- * @'Control.Applicative.Free.retractAp' :: 'Applicative' f => 'Ap' f a -> f a@ -- * @'Control.Monad.Free.retract' :: 'Monad' f => 'Free' f a -> f a@+-- foldFree1 :: forall m f a . ( FreeAlgebra1 m , AlgebraType m f@@ -214,8 +214,7 @@ Proof -> foldNatFree id {-# INLINABLE foldFree1 #-} --- |--- @'unFoldNatFree'@ is an inverse of @'foldNatFree'@+-- | @'unFoldNatFree'@ is an inverse of @'foldNatFree'@ -- -- It is uniquelly determined by its universal property (by Yonneda lemma): --@@ -224,6 +223,7 @@ -- Note that @'unFoldNatFree' id@ is the -- [unit](https://ncatlab.org/nlab/show/unit+of+an+adjunction) of the -- adjunction imposed by the @'FreeAlgebra1'@ constraint.+-- unFoldNatFree :: ( FreeAlgebra1 m , AlgebraType0 m f@@ -232,8 +232,7 @@ -> f a -> d a unFoldNatFree nat = nat . liftFree --- |--- This is a functor instance for @m@ when considered as an endofuctor of some+-- | This is a functor instance for @m@ when considered as an endofuctor of some -- subcategory of @Type -> Type@ (e.g. endofunctors of /Hask/) and it satisfies -- the functor laws: --@@ -248,6 +247,7 @@ -- @'AlgebraType0' m@ subsumes @Monad m@, e.g. -- @'Control.Monad.State.Lazy.StateT'@, @'Control.Monad.Writer.Lazy.WriterT'@ -- or @'Control.Monad.Reader.ReaderT'@.+-- hoistFree1 :: forall m f g a . ( FreeAlgebra1 m , AlgebraType0 m g@@ -299,10 +299,10 @@ foldNatFree nat (hoistFreeH f) = foldNatFree nat f #-} --- |--- @'joinFree1'@ makes @m@ a monad in some subcatgory of types of kind @Type -> Type@+-- | @'joinFree1'@ makes @m@ a monad in some subcatgory of types of kind @Type -> Type@ -- (usually the endo-functor category of @Hask@). It is just a specialization -- of @'foldFree1'@.+-- joinFree1 :: forall m f a . ( FreeAlgebra1 m , AlgebraType0 m f@@ -314,8 +314,7 @@ Proof -> foldFree1 {-# INLINABLE joinFree1 #-} --- |--- Bind operator for the @'joinFree1'@ monad, this is just @'foldNatFree'@ in+-- | Bind operator for the @'joinFree1'@ monad, this is just @'foldNatFree'@ in -- disguise. -- -- For @'Control.Monad.State.Lazy.StateT'@,@@ -323,6 +322,7 @@ -- @'Control.Monad.Reader.Lazy.ReaderT'@ (or any @'FreeAlgebra1' m => m@ such -- that @'AlgebraType0' m@ subsumes @'Monad' m@), this is the @>>=@ version of -- @Control.Monad.Morph.embed@.+-- bindFree1 :: forall m f g a . ( FreeAlgebra1 m , AlgebraType0 m g@@ -349,8 +349,7 @@ Proof -> fmap foldFree1 . foldNatFree (hoistFree1 liftFree . liftFree) {-# INLINABLE assocFree1 #-} --- |--- @'Fix' (m f)@ is the initial /algebra/ of type @'AlgebraType' m@ and+-- | @'Fix' (m f)@ is the initial /algebra/ of type @'AlgebraType' m@ and -- @'AlgebraType0' f@. -- cataFree1 :: forall m f a .@@ -363,12 +362,12 @@ -> f a cataFree1 = cataM foldFree1 --- |--- Specialization of @'foldNatFree' \@_ \@'Identity'@; it will further specialize to:+-- | Specialization of @'foldNatFree' \@_ \@'Identity'@; it will further specialize to: -- -- * @\\_ -> 'runIdentity' . 'Data.Functor.Coyoneda.lowerCoyoneda'@ -- * @'Control.Applicative.Free.iterAp' :: 'Functor' g => (g a -> a) -> 'Ap' g a -> a@ -- * @'Control.Monad.Free.iter' :: 'Functor' f => (f a -> a) -> 'Free' f a -> a@+-- iterFree1 :: forall m f a . ( FreeAlgebra1 m , AlgebraType0 m f@@ -382,21 +381,21 @@ -- Instances --- |--- Algebras of the same type as @'Coyoneda'@ are all functors.+-- | Algebras of the same type as @'Coyoneda'@ are all functors.+-- type instance AlgebraType0 Coyoneda g = () type instance AlgebraType Coyoneda g = Functor g instance FreeAlgebra1 Coyoneda where liftFree = liftCoyoneda foldNatFree nat (Coyoneda ba fx) = ba <$> nat fx --- |--- Algebras of the same type as @'Ap'@ are the applicative functors.+-- | Algebras of the same type as @'Ap'@ are the applicative functors.+-- type instance AlgebraType0 Ap g = Functor g type instance AlgebraType Ap g = Applicative g--- |--- @'Ap'@ is a free in the class of applicative functors, over any functor+-- | @'Ap'@ is a free in the class of applicative functors, over any functor -- (@'Ap' f@ is applicative whenever @f@ is a functor)+-- instance FreeAlgebra1 Ap where liftFree = Ap.liftAp foldNatFree = Ap.runAp@@ -413,9 +412,9 @@ liftFree = Final.liftAp foldNatFree = Final.runAp --- |--- @'Day' f f@ newtype wrapper. It is isomorphic with @'Ap' f@ for applicative--- functors @f@ via @'dayToAp'@ (and @'apToDay'@).+-- | @'Day' f f@ newtype wrapper. It is isomorphic with @'Ap' f@ for+-- applicative functors @f@ via @'dayToAp'@ (and @'apToDay'@).+-- newtype DayF f a = DayF { runDayF :: Day f f a} deriving (Functor, Applicative) @@ -425,24 +424,24 @@ apToDay :: Applicative f => Ap f a -> Day f f a apToDay = runDayF . hoistFreeH --- |--- Algebras of the same type as @'DayF'@ are all the applicative functors.+-- | Algebras of the same type as @'DayF'@ are all the applicative functors.+-- type instance AlgebraType0 DayF g = Applicative g type instance AlgebraType DayF g = Applicative g--- |--- @'DayF'@, as @'Ap'@ is a free applicative functor, but over applicative functors+-- | @'DayF'@, as @'Ap'@ is a free applicative functor, but over applicative functors -- (@'DayF' f@ is applicative if @f@ is an applicative functor).+-- instance FreeAlgebra1 DayF where liftFree fa = DayF $ Day fa fa const foldNatFree nat (DayF day) = Day.dap . Day.trans2 nat . Day.trans1 nat $ day --- |--- Algebras of the same type as @'Free'@ monad is the class of all monads.+-- | Algebras of the same type as @'Free'@ monad is the class of all monads.+-- type instance AlgebraType0 Free f = Functor f type instance AlgebraType Free m = Monad m--- |--- @'Free'@ monad is free in the class of monad over the class of functors.+-- | @'Free'@ monad is free in the class of monad over the class of functors.+-- instance FreeAlgebra1 Free where liftFree = Free.liftF foldNatFree = Free.foldFree@@ -459,13 +458,12 @@ liftFree = Alt.liftAlt foldNatFree = Alt.runAlt --- |--- Algebras of the same type as @'L.StateT'@ monad is the class of all state+-- | Algebras of the same type as @'L.StateT'@ monad is the class of all state -- monads.+-- type instance AlgebraType0 (L.StateT s) m = Monad m type instance AlgebraType (L.StateT s) m = ( MonadState s m )--- |--- Lazy @'L.StateT'@ monad transformer is a free algebra in the class of monads+-- | Lazy @'L.StateT'@ monad transformer is a free algebra in the class of monads -- which satisfy the @'MonadState'@ constraint. Note that this instance -- captures that @'L.StateT' s@ is a monad transformer: --@@ -474,6 +472,7 @@ -- @ -- -- This is also true for all the other monad transformers.+-- instance FreeAlgebra1 (L.StateT s) where liftFree = lift foldNatFree nat ma = do@@ -481,14 +480,14 @@ put s return a --- |--- Algebras of the same type as @'S.StateT'@ monad is the class of all state+-- | Algebras of the same type as @'S.StateT'@ monad is the class of all state -- monads.+-- type instance AlgebraType0 (S.StateT s) m = Monad m type instance AlgebraType (S.StateT s) m = ( MonadState s m )--- |--- Strict @'S.StateT'@ monad transformer is also a free algebra, thus @'hoistFreeH'@--- is an isomorphism between the strict and lazy versions.+-- | Strict @'S.StateT'@ monad transformer is also a free algebra, thus+-- @'hoistFreeH'@ is an isomorphism between the strict and lazy versions.+-- instance FreeAlgebra1 (S.StateT s) where liftFree :: Monad m => m a -> S.StateT s m a liftFree = lift@@ -497,50 +496,50 @@ put s return a --- |--- Algebras of the same type as @'L.WriterT'@ monad is the class of all writer--- monads.+-- | Algebras of the same type as @'L.WriterT'@ monad is the class of all+-- writer monads.+-- type instance AlgebraType0 (L.WriterT w) m = ( Monad m, Monoid w ) type instance AlgebraType (L.WriterT w) m = ( MonadWriter w m )--- |--- Lazy @'L.WriterT'@ is free for algebras of type @'MonadWriter'@.+-- | Lazy @'L.WriterT'@ is free for algebras of type @'MonadWriter'@.+-- instance FreeAlgebra1 (L.WriterT w) where liftFree = lift foldNatFree nat (L.WriterT m) = fst <$> nat m --- |--- Algebras of the same type as @'S.WriterT'@ monad is the class of all writer--- monads.+-- | Algebras of the same type as @'S.WriterT'@ monad is the class of all+-- writer monads.+-- type instance AlgebraType0 (S.WriterT w) m = ( Monad m, Monoid w ) type instance AlgebraType (S.WriterT w) m = ( MonadWriter w m )--- |--- Strict @'S.WriterT'@ monad transformer is a free algebra among all+-- | Strict @'S.WriterT'@ monad transformer is a free algebra among all -- @'MonadWriter'@s.+-- instance FreeAlgebra1 (S.WriterT w) where liftFree = lift foldNatFree nat (S.WriterT m) = fst <$> nat m --- |--- Algebras of the same type as @'L.ReaderT'@ monad is the class of all reader--- monads.+-- | Algebras of the same type as @'L.ReaderT'@ monad is the class of all+-- reader monads. -- -- TODO: take advantage of poly-kinded `ReaderT`+-- type instance AlgebraType0 (ReaderT r) m = ( Monad m ) type instance AlgebraType (ReaderT r) m = ( MonadReader r m )--- |--- @'ReaderT'@ is a free monad in the class of all @'MonadReader'@ monads.+-- | @'ReaderT'@ is a free monad in the class of all @'MonadReader'@ monads.+-- instance FreeAlgebra1 (ReaderT r :: (Type -> Type) -> Type -> Type) where liftFree = lift foldNatFree nat (ReaderT g) = ask >>= nat . g --- |--- Algebras of the same type as @'S.ReaderT'@ monad is the class of all reader--- monads.+-- | Algebras of the same type as @'S.ReaderT'@ monad is the class of all+-- reader monads.+-- type instance AlgebraType0 (ExceptT e) m = ( Monad m ) type instance AlgebraType (ExceptT e) m = ( MonadError e m )--- |--- @'ExceptT' e@ is a free algebra among all @'MonadError' e@ monads.+-- | @'ExceptT' e@ is a free algebra among all @'MonadError' e@ monads.+-- instance FreeAlgebra1 (ExceptT e) where liftFree = lift foldNatFree nat (ExceptT m) = do@@ -573,8 +572,8 @@ tell w return a --- |--- Algebra type for @'ListT'@ monad transformer.+-- | Algebra type for @'ListT'@ monad transformer.+-- class Monad m => MonadList m where mempty1 :: m a mappend1 :: m a -> m a -> m a@@ -596,13 +595,13 @@ empty1 <- mempty1 foldM (\x y -> x `mappend1_` y) empty1 as --- |--- Free construction for kinds @'Type' -> 'Type'@. @'Free1' 'Functor'@ is+-- | Free construction for kinds @'Type' -> 'Type'@. @'Free1' 'Functor'@ is -- isomorhpic to @'Coyoneda'@ via @'hoistFreeH'@, and @'Free1' 'Applicative'@ -- is isomorphic to @'Ap'@ (also via @'hoistFreeH'@). -- -- Note: useful instance are only provided for ghc-8.6 using quantified -- constraints.+-- newtype Free1 (c :: (Type -> Type) -> Constraint) (f :: Type -> Type) a@@ -615,8 +614,7 @@ -- instances for @'Free1'@ using quantified constraints -- --- |--- @'Free1'@ is a functor whenever @c f@ implies @'Functor' f@ .+-- | @'Free1'@ is a functor whenever @c f@ implies @'Functor' f@ . -- instance (forall h. c h => Functor h) => Functor (Free1 c f) where@@ -626,9 +624,8 @@ a <$ Free1 g = Free1 $ \h -> a <$ g h --- |--- @'Free1'@ is an applicative functor whenever @c f@ implies --- @'Applicative' f@.+-- | @'Free1'@ is an applicative functor whenever @c f@ implies @'Applicative'+-- f@. -- instance (forall h. c h => Applicative h) => Applicative (Free1 c f) where@@ -644,9 +641,8 @@ Free1 f <* Free1 g = Free1 $ \h -> f h <* g h --- |--- @'Free1'@ is a monad whenever @c f@ implies --- @'Monad' f@.+-- | @'Free1'@ is a monad whenever @c f@ implies @'Monad' f@.+-- instance (forall h. c h => Monad h) => Monad (Free1 c f) where @@ -706,8 +702,7 @@ -- @'ContT' r m@ is not functorial in @m@, so there is no chance it can admit -- an instance of @'FreeAlgebra1'@ --- |--- A higher version @'Data.Algebra.Pointed'@ class.+-- | A higher version @'Data.Algebra.Pointed'@ class. -- -- With @'QuantifiedConstraints'@ this class will be redundant. class MonadMaybe m where
src/Control/Algebra/Free2.hs view
@@ -3,8 +3,7 @@ {-# LANGUAGE PolyKinds #-} {-# LANGUAGE RankNTypes #-} --- |--- A type class for free objects of kind @k -> k -> Type@, i.e. /graphs/ (we+-- | A type class for free objects of kind @k -> k -> Type@, i.e. /graphs/ (we -- will use this name for types of this kind in this documentation). Examples -- include various flavors of /free categories/ and /arrows/ which -- are not included in this package, see@@ -35,24 +34,21 @@ import Data.Algebra.Free (AlgebraType, AlgebraType0, Proof (..)) --- |--- Free algebra class similar to @'FreeAlgebra1'@ and @'FreeAlgebra'@, but for--- types of kind @k -> k -> Type@.+-- | Free algebra class similar to @'FreeAlgebra1'@ and @'FreeAlgebra'@, but+-- for types of kind @k -> k -> Type@. -- class FreeAlgebra2 (m :: (k -> k -> Type) -> k -> k -> Type) where {-# MINIMAL liftFree2, foldNatFree2 #-} - -- |- -- Lift a graph @f@ satsifying the constraint @'AlgebraType0'@ to- -- a free its object @m f@.+ -- | Lift a graph @f@ satsifying the constraint @'AlgebraType0'@ to a free+ -- its object @m f@. -- liftFree2 :: AlgebraType0 m f => f a b -> m f a b - -- |- -- This represents the theorem that @m f@ is indeed free object (as+ -- | This represents the theorem that @m f@ is indeed free object (as -- in propositions as types). The types of kind @k -> k -> Type@ form -- a category, where an arrow from @f :: k -> k -> Type@ to @d :: k -> -- k -> Type@ is represented by type @forall x y. f x y -> d x y@.@@ -71,13 +67,12 @@ => (forall x y. f x y -> d x y) -> (m f a b -> d a b) - -- |- -- A proof that for each @f@ satisfying @AlgebraType0 m f@, @m f@+ -- | A proof that for each @f@ satisfying @AlgebraType0 m f@, @m f@ -- satisfies @AlgebraType m (m f)@ constrant. This means that @m@ is- -- a well defined /functor/ from the full sub-category of types of- -- kind @k -> k -> Type@ which satisfy the @AlgebraType0 m@ constraint- -- to the full subcategory of types of the same kind which satifsfy- -- the constraint @AlgebraType m@.+ -- a well defined /functor/ from the full sub-category of types of kind @k+ -- -> k -> Type@ which satisfy the @AlgebraType0 m@ constraint to the full+ -- subcategory of types of the same kind which satifsfy the constraint+ -- @AlgebraType m@. -- codom2 :: forall (f :: k -> k -> Type). AlgebraType0 m f@@ -87,13 +82,12 @@ => Proof (AlgebraType m (m a)) (m a) codom2 = Proof - -- | - -- A proof that each type @f :: k -> k -> Type@ satisfying the- -- @Algebra m f@ constraint also satisfies @AlgebraType0 m f@. This- -- states that there is a well defined /forgetful functor/ from the- -- category of types of kind @k -> k -> Type@ which satisfy the- -- @AlgebraType m@ to the category of types of the same kind which- -- satisfy the @AlgebraType0 m@ constraint.+ -- | A proof that each type @f :: k -> k -> Type@ satisfying the @Algebra+ -- m f@ constraint also satisfies @AlgebraType0 m f@. This states that+ -- there is a well defined /forgetful functor/ from the category of types+ -- of kind @k -> k -> Type@ which satisfy the @AlgebraType m@ to the+ -- category of types of the same kind which satisfy the @AlgebraType0 m@+ -- constraint. -- forget2 :: forall (f :: k -> k -> Type). AlgebraType m f@@ -144,8 +138,7 @@ Proof -> foldNatFree2 id {-# INLINABLE foldFree2 #-} --- | --- Inverse of @'foldNatFree2'@.+-- | Inverse of @'foldNatFree2'@. -- -- It is uniquelly determined by its universal property (by Yonneda lemma): --@@ -164,11 +157,9 @@ unFoldNatFree2 nat = nat . liftFree2 {-# INLINABLE unFoldNatFree2 #-} --- |--- Hoist the underlying graph in the free structure.--- This is a higher version of a functor (analogous to @'fmapFree'@, which--- defined functor instance for @'FreeAlgebra'@ instances) and it satisfies the--- functor laws:+-- | Hoist the underlying graph in the free structure. This is a higher+-- version of a functor (analogous to @'fmapFree'@, which defined functor+-- instance for @'FreeAlgebra'@ instances) and it satisfies the functor laws: -- -- prop> hoistFree2 id = id -- prop> hoistFree2 f . hoistFree2 g = hoistFree2 (f . g)@@ -198,8 +189,7 @@ #-} --- |--- Hoist the top level free structure.+-- | Hoist the top level free structure. -- hoistFreeH2 :: forall m n f a b . ( FreeAlgebra2 m@@ -241,8 +231,7 @@ Proof -> foldFree2 {-# INLINABLE joinFree2 #-} --- |--- @bind@ of the monad defined by @m@ on the subcategory of graphs (types of+-- | @bind@ of the monad defined by @m@ on the subcategory of graphs (types of -- kind @k -> k -> Type@). -- -- prop> foldNatFree2 nat (bindFree mf nat') = foldNatFree2 (foldNatFree2 nat . nat') mf
src/Control/Monad/Action.hs view
@@ -20,8 +20,7 @@ import Data.Algebra.Pointed (Pointed (point)) import Data.Algebra.Free (FreeAlgebra, foldFree) --- |--- A /monad action/ is an `m`-algebra parametrized over a functor `f`.+-- | A /monad action/ is an `m`-algebra parametrized over a functor `f`. -- This is direct translation of a /monoid action/ in the monoidal category of -- endofunctors with monoidal product: functor composition. --@@ -31,22 +30,23 @@ -- prop> mact . return = id -- -- There are monads which do not have any (safe) instances, like @'IO'@.+-- class (Monad m, Functor f) => MAction m f where mact :: m (f a) -> f a instance Monad m => MAction m m where mact = join --- |--- You can use @'PointedMonoid'@ newtype wrapper if you want to laverage+-- | You can use @'PointedMonoid'@ newtype wrapper if you want to laverage -- @'Pointed'@ instance for a @'Monoid'@.+-- instance (Pointed r, Functor f) => MAction ((->) r) f where mact f = f point --- |--- Every algebra @d@ which satisfies the constraint @'AlgebraType' m d@ lifts+-- | Every algebra @d@ which satisfies the constraint @'AlgebraType' m d@ lifts -- to an action on the constant functor @'Const' d@. This is the same as to -- say that @d@ is an @m@-algebra (as of /f-algebras/ in category theory).+-- instance ( Monad m , FreeAlgebra m , AlgebraType m d@@ -54,8 +54,8 @@ => MAction m (Const d) where mact mca = Const $ foldFree $ getConst <$> mca --- |--- Free algebra associated with the @'MAction' constraint.+-- | Free algebra associated with the @'MAction' constraint.+-- newtype FreeMAction (m :: Type -> Type) (f :: Type -> Type) a = FreeMAction { runFreeMAction :: m (f a)
src/Data/Algebra/Free.hs view
@@ -32,6 +32,7 @@ , foldlFree' -- * General free type , Free (..)+ , DNonEmpty (..) ) where @@ -46,6 +47,7 @@ import Data.Group (Group (..)) import Data.Kind (Constraint, Type) import Data.List.NonEmpty (NonEmpty (..))+import qualified Data.List.NonEmpty as NonEmpty import Data.Monoid ( Endo (..) #if __GLASGOW_HASKELL__ < 808 , Monoid (..)@@ -62,10 +64,9 @@ -- Prerequisites for @'FreeAlgebra'@ -- --- |--- 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.+-- | 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'@@ -73,21 +74,21 @@ -- the category of types of kind @* -> *@ which satisfy @'AlgebraType' m@ -- constrain to the category of types of kind @* -> *@ which satisfy the -- @'AlgebraType0 m@ constraint.+-- type family AlgebraType (f :: k) (a :: l) :: Constraint --- |--- Type family which limits Hask to its full subcategory which satisfies+-- | 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@.+-- type family AlgebraType0 (f :: k) (a :: l) :: Constraint --- |--- A proof that constraint @c@ holds for type @a@.+-- | A proof that constraint @c@ holds for type @a@.+-- data Proof (c :: Constraint) (a :: l) where Proof :: c => Proof c a --- |--- A lawful instance has to guarantee that @'unFoldFree'@ is an inverse of+-- | 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@@ -95,6 +96,7 @@ -- 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@.+-- class FreeAlgebra (m :: Type -> Type) where {-# MINIMAL returnFree, foldMapFree #-}@@ -111,21 +113,21 @@ => (a -> d) -- ^ a mapping of generators of @m@ into @d@ -> (m a -> d) -- ^ a homomorphism from @m a@ to @d@ - -- |- -- 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)+ -- | 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)+ -- codom :: forall a. AlgebraType0 m a => Proof (AlgebraType m (m a)) (m a) default codom :: forall a. AlgebraType m (m a) => Proof (AlgebraType m (m a)) (m a) codom = Proof - -- |- -- Proof that the forgetful functor from types @a@ satisfying @AgelbraType- -- m a@ to @AlgebraType0 m a@ is well defined.+ -- | Proof that the forgetful functor from types @a@ satisfying+ -- @AgelbraType m a@ to @AlgebraType0 m a@ is well defined.+ -- forget :: forall a. AlgebraType m a => Proof (AlgebraType0 m a) (m a) default forget :: forall a. AlgebraType0 m a@@ -136,8 +138,7 @@ -- Free combinators -- --- |--- Inverse of @'foldMapFree'@+-- | Inverse of @'foldMapFree'@ -- -- It is uniquelly determined by its universal property (by Yonneda lemma): --@@ -146,6 +147,7 @@ -- Note that @'unFoldMapFree' id@ is the unit of the -- [unit](https://ncatlab.org/nlab/show/unit+of+an+adjunction) of the -- adjunction imposed by the @'FreeAlgebra'@ constraint.+-- unFoldMapFree :: FreeAlgebra m => (m a -> d)@@ -153,8 +155,7 @@ unFoldMapFree f = f . returnFree {-# INLINABLE unFoldMapFree #-} --- |--- All types which satisfy @'FreeAlgebra'@ constraint are foldable.+-- | All types which satisfy @'FreeAlgebra'@ constraint are foldable. -- -- prop> foldFree . returnFree == id --@@ -171,6 +172,7 @@ -- -- Note that @foldFree@ replaces the abstract \/ free algebraic operation in -- @m a@ to concrete one in @a@.+-- foldFree :: forall m a . ( FreeAlgebra m@@ -182,8 +184,7 @@ Proof -> foldMapFree id ma {-# INLINABLE foldFree #-} --- |--- The canonical quotient map from a free algebra of a wider class to a free+-- | 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.@@ -196,6 +197,7 @@ -- always true, just GHC cannot prove it here) -- * @m@ is a free algebra generated by @a@ -- * @n@ is a free algebra generated by @a@+-- natFree :: forall m n a . ( FreeAlgebra m , FreeAlgebra n@@ -207,9 +209,9 @@ natFree = foldMapFree returnFree {-# INLINABLE natFree #-} --- |--- All types which satisfy @'FreeAlgebra'@ constraint are functors.--- The constraint @'AlgebraType' m (m b)@ is always satisfied.+-- | All types which satisfy @'FreeAlgebra'@ constraint are functors. The+-- constraint @'AlgebraType' m (m b)@ is always satisfied.+-- fmapFree :: forall m a b . ( FreeAlgebra m , AlgebraType0 m a@@ -222,8 +224,8 @@ Proof -> foldMapFree (returnFree . f) ma {-# INLINABLE fmapFree #-} --- |--- @'FreeAlgebra'@ constraint implies @Monad@ constrain.+-- | @'FreeAlgebra'@ constraint implies @Monad@ constrain.+-- joinFree :: forall m a . ( FreeAlgebra m , AlgebraType0 m a@@ -234,9 +236,9 @@ Proof -> foldFree mma {-# INLINABLE joinFree #-} --- |--- The monadic @'bind'@ operator. @'returnFree'@ is the corresponding+-- | The monadic @'bind'@ operator. @'returnFree'@ is the corresponding -- @'return'@ for this monad. This just @'foldMapFree'@ in disguise.+-- bindFree :: forall m a b . ( FreeAlgebra m , AlgebraType0 m a@@ -249,8 +251,7 @@ Proof -> foldMapFree f ma {-# INLINABLE bindFree #-} --- |--- @'Fix' m@ is the initial algebra in the category of algebras of type+-- | @'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). --@@ -261,6 +262,7 @@ -- fixToFree = cataFree -- @ -- For monoids the inverse is given by @'Data.Fix.ana' (\_ -> [])@.+-- cataFree :: ( FreeAlgebra m , AlgebraType m a , Functor m@@ -269,11 +271,11 @@ -> a cataFree = cata foldFree --- |--- A version of @'Data.Foldable.foldr'@, e.g. it can specialize to+-- | A version of @'Data.Foldable.foldr'@, e.g. it can specialize to -- -- * @foldrFree \@[] :: (a -> b -> b) -> [a] -> b -> b@ -- * @foldrFree \@'Data.List.NonEmpty.NonEmpty' :: (a -> b -> b) -> 'Data.List.NonEmpty.NonEmpty' a -> b -> b@+-- foldrFree :: forall m a b . ( FreeAlgebra m@@ -286,8 +288,8 @@ -> b foldrFree f z t = appEndo (foldMapFree (Endo . f) t) z --- |--- Like @'foldrFree'@ but strict.+-- | Like @'foldrFree'@ but strict.+-- foldrFree' :: forall m a b . ( FreeAlgebra m@@ -302,11 +304,11 @@ where f' k x z = k $! f x z --- |--- Generalizes @'Data.Foldable.foldl'@, e.g. it can specialize to+-- | Generalizes @'Data.Foldable.foldl'@, e.g. it can specialize to -- -- * @foldlFree \@[] :: (b -> a -> b) -> b -> [a] -> b@ -- * @foldlFree \@'Data.List.NonEmpty.NonEmpty' :: (b -> a -> b) -> b -> 'Data.List.NonEmpty.NonEmpty' a -> b@+-- foldlFree :: forall m a b . ( FreeAlgebra m@@ -319,8 +321,8 @@ -> b foldlFree f z t = appEndo (getDual (foldMapFree (Dual . Endo . flip f) t)) z --- |--- Like @'foldlFree'@ but strict.+-- | Like @'foldlFree'@ but strict.+-- foldlFree' :: forall m a b . ( FreeAlgebra m@@ -349,9 +351,9 @@ type instance AlgebraType0 NonEmpty a = () type instance AlgebraType NonEmpty m = Semigroup m--- |--- @'NonEmpty'@ is the free semigroup in the class of semigroup which are+-- | @'NonEmpty'@ is the free semigroup in the class of semigroup which are -- strict in the left argument.+-- instance FreeAlgebra NonEmpty where returnFree a = a :| [] -- @'foldMap'@ requires @'Monoid' d@ constraint which we don't need to@@ -359,10 +361,21 @@ foldMapFree f (a :| []) = f a foldMapFree f (a :| (b : bs)) = f a <> foldMapFree f (b :| bs) +-- | 'DNonEmpty' is the free semigroup ihn the class of all semigroups.+--+newtype DNonEmpty a = DNonEmpty ([a] -> NonEmpty a)+instance Semigroup (DNonEmpty a) where+ DNonEmpty f <> DNonEmpty g = DNonEmpty (f . NonEmpty.toList . g)++type instance AlgebraType0 DNonEmpty a = ()+type instance AlgebraType DNonEmpty m = Semigroup m+instance FreeAlgebra DNonEmpty where+ returnFree a = DNonEmpty (a :|)+ foldMapFree f (DNonEmpty g) = foldMapFree f (g [])+ type instance AlgebraType0 [] a = () type instance AlgebraType [] m = Monoid m--- | --- Note that @'[]'@ is a free monoid only for monoids which multiplication is+-- | Note that @'[]'@ is a free monoid only for monoids which multiplication is -- strict in the left argument -- [ref](http://comonad.com/reader/2015/free-monoids-in-haskell/). Note that -- being strict adds additional equation to the monoid laws:@@ -375,6 +388,7 @@ -- 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 FreeAlgebra [] where returnFree a = [a] foldMapFree = foldMap@@ -386,9 +400,9 @@ foldMapFree _ Nothing = point foldMapFree f (Just a) = f a --- |--- @'Free' c a@ represents free algebra for a constraint @c@ generated by+-- | @'Free' c a@ represents free algebra for a constraint @c@ generated by -- type @a@.+-- newtype Free (c :: Type -> Constraint) a = Free { runFree :: forall r. c r => (a -> r) -> r }@@ -420,9 +434,9 @@ type instance AlgebraType0 DList a = () type instance AlgebraType DList a = Monoid a--- |--- @'DList'@ is isomorphic to @'Free' Monoid@; it is free in the class of all+-- | @'DList'@ is isomorphic to @'Free' Monoid@; it is free in the class of all -- monoids.+-- instance FreeAlgebra DList where returnFree = DList.singleton foldMapFree = foldMap
src/Data/Algebra/Pointed.hs view
@@ -11,16 +11,16 @@ import Data.Semigroup (Semigroup (..)) #endif --- |--- Class of pointed sets+-- | Class of pointed sets+-- class Pointed p where point :: p instance Pointed (Maybe a) where point = Nothing --- |--- @Monoid@ should be a subclass of @Pointed@.+-- | @Monoid@ should be a subclass of @Pointed@.+-- newtype PointedMonoid m = PointedMonoid { runPointedMonoid :: m } deriving (Show, Eq, Ord, Functor)
src/Data/Group/Free.hs view
@@ -22,10 +22,11 @@ ) where import Control.Monad (ap)+import Data.Bifunctor (bimap) import Data.DList (DList) import qualified Data.DList as DList-import Data.Bifunctor (bimap) import Data.Group (Group (..))+import Data.List (foldl') #if __GLASGOW_HASKELL__ < 808 import Data.Semigroup (Semigroup (..)) #endif@@ -36,8 +37,7 @@ , FreeAlgebra (..) ) --- |--- Free group generated by a type @a@. Internally it's represented by a list+-- | Free group generated by a type @a@. Internally it's represented by a list -- @[Either a a]@ where inverse is given by: -- -- @@@ -49,6 +49,7 @@ -- -- @'FreeGroup' a@ is isomorphic with @'Free' Group a@ (but the latter does not -- require @Eq@ constraint, hence is more general).+-- newtype FreeGroup a = FreeGroup { runFreeGroup :: DList (Either a a) }@@ -65,8 +66,7 @@ return a = FreeGroup $ DList.singleton (Right a) FreeGroup as >>= f = FreeGroup $ as >>= runFreeGroup . either f f --- |--- Normalize a @Dlist@, i.e. remove adjacent inverses from a word, i.e.+-- | Normalize a @Dlist@, i.e. remove adjacent inverses from a word, i.e. -- @ab⁻¹ba⁻¹c = c@. Note that this function is implemented using -- @'normalizeL'@, implemnting it directly on @DList@s would be @O(n^2)@ -- instead of @O(n)@.@@ -78,17 +78,17 @@ -> DList (Either a a) normalize = DList.fromList . normalizeL . DList.toList --- |--- Smart constructor which normalizes a dlist.+-- | Smart constructor which normalizes a dlist. -- -- /Complexity:/ @O(n)@+-- fromDList :: Eq a => DList (Either a a) -> FreeGroup a fromDList = freeGroupFromList . DList.toList --- |--- Construct a FreeGroup from a list.+-- | Construct a FreeGroup from a list. -- -- /Complextiy:/ @O(n)@+-- freeGroupFromList :: Eq a => [Either a a] -> FreeGroup a freeGroupFromList = FreeGroup . DList.fromList . normalizeL @@ -105,7 +105,7 @@ #endif instance Eq a => Group (FreeGroup a) where- invert (FreeGroup as) = FreeGroup $ foldl (\acu a -> either Right Left a `DList.cons` acu) DList.empty as+ invert (FreeGroup as) = FreeGroup $ foldl' (\acu a -> either Right Left a `DList.cons` acu) DList.empty as type instance AlgebraType0 FreeGroup a = Eq a type instance AlgebraType FreeGroup g = (Eq g, Group g)@@ -117,17 +117,18 @@ as' = DList.tail as in either (invert . f) f a' `mappend` foldMapFree f (FreeGroup as') --- |--- Free group in the class of groups which multiplication is strict on the+-- | Free group in the class of groups which multiplication is strict on the -- left, i.e. -- -- prop> undefined <> a = undefined+-- newtype FreeGroupL a = FreeGroupL { runFreeGroupL :: [Either a a] } deriving (Show, Eq, Ord) -- | Like @'normalize'@ but for lists. -- -- /Complexity:/ @O(n)@+-- normalizeL :: Eq a => [Either a a]@@ -138,6 +139,7 @@ -- hand side of a 'FreeGroupL'. -- -- /Complexity:/ @O(1)@+-- consL :: Eq a => Either a a -> FreeGroupL a -> FreeGroupL a consL a (FreeGroupL as) = FreeGroupL (consL_ a as) @@ -148,8 +150,7 @@ (Right x, Left y) | x == y -> bs _ -> a : as --- |--- Smart constructor which normalizes a list.+-- | Smart constructor which normalizes a list. -- -- /Complexity:/ @O(n)@ fromList :: Eq a => [Either a a] -> FreeGroupL a@@ -168,7 +169,7 @@ #endif instance Eq a => Group (FreeGroupL a) where- invert (FreeGroupL as) = FreeGroupL $ foldl (\acu a -> either Right Left a : acu) [] as+ invert (FreeGroupL as) = FreeGroupL $ foldl' (\acu a -> either Right Left a : acu) [] as type instance AlgebraType0 FreeGroupL a = Eq a type instance AlgebraType FreeGroupL g = (Eq g, Group g)
src/Data/Monoid/Abelian.hs view
@@ -13,8 +13,7 @@ import Data.Algebra.Free (AlgebraType, AlgebraType0, FreeAlgebra (..)) import Data.Semigroup.Abelian (AbelianSemigroup) --- |--- Free abelian monoid. Note that `FreeAbelianMonoid () ≅ Natural` as+-- | Free abelian monoid. Note that `FreeAbelianMonoid () ≅ Natural` as -- expected. -- -- It is a monad on the full subcategory which satisfies the `Ord` constraint,
src/Data/Semigroup/Abelian.hs view
@@ -39,11 +39,11 @@ , FreeAlgebra (..) ) --- |--- Class of commutative monoids, e.g. with additional law:+-- | Class of commutative monoids, e.g. with additional law: -- @ -- a <> b = b <> a -- @+-- class Semigroup m => AbelianSemigroup m instance AbelianSemigroup Void@@ -70,8 +70,7 @@ instance AbelianSemigroup IntSet --- |--- Free abelian semigroup is isomorphic to a non empty map with keys @a@ and+-- | Free abelian semigroup is isomorphic to a non empty map with keys @a@ and -- values positive natural numbers. -- -- It is a monad on the full subcategory which satisfies the `Ord` constraint,@@ -84,9 +83,9 @@ toNonEmpty :: FreeAbelianSemigroup a -> NonEmpty (a, Natural) toNonEmpty (FreeAbelianSemigroup as) = NE.fromList . Map.toList $ as --- |--- Smart constructor which creates `FreeAbelianSemigroup` from a non empty list--- of pairs @(a, n) :: (a, Natural)@ where @n > 0@.+-- | Smart constructor which creates `FreeAbelianSemigroup` from a non empty+-- list of pairs @(a, n) :: (a, Natural)@ where @n > 0@.+-- fromNonEmpty :: Ord a => NonEmpty (a, Natural) -> Maybe (FreeAbelianSemigroup a) fromNonEmpty = fmap (FreeAbelianSemigroup . Map.fromList) . go . NE.toList where
src/Data/Semigroup/Semilattice.hs view
@@ -27,9 +27,9 @@ ) import Data.Semigroup.Abelian (AbelianSemigroup) --- |--- Class of abelian semigroups in which every element is idempontent, i.e.+-- | Class of abelian semigroups in which every element is idempontent, i.e. -- @a <> a = a@.+-- class AbelianSemigroup m => Semilattice m instance Semilattice Void@@ -39,8 +39,8 @@ instance Ord a => Semilattice (Set a) instance Semilattice IntSet --- |--- @'FreeSemilattice'@ is a non empty set.+-- | @'FreeSemilattice'@ is a non empty set.+-- newtype FreeSemilattice a = FreeSemilattice (Set a) deriving (Ord, Eq, Show, Semigroup)