free-algebras 0.0.3.0 → 0.0.4.0

raw patch · 6 files changed

+171/−9 lines, 6 filesdep +mmorphPVP ok

version bump matches the API change (PVP)

Dependencies added: mmorph

API changes (from Hackage documentation)

Files

• ChangeLog.md +8/−0
• free-algebras.cabal +32/−2
• src/Control/Algebra/Free.hs +22/−4
• src/Data/Algebra/Free.hs +71/−1
• src/Data/Monoid/MSet.hs +21/−2
• src/Data/Semigroup/SSet.hs +17/−0

@@ -1,5 +1,13 @@ # Changelog for free-algebras +## Version 0.0.4.0++- `S` new type wrapper in `SSet`, and overlappable instance for+  `SSet s a => SSet (S s) (Endo a)`+- `foldrFree` and friends+- `foldrMSet`+- documented intersection with `monad-mmorph` package.+ ## Version 0.0.3.0  - Breaking change: changed proofs in FreeAlgebra and FreeAlgebra1 class; now

@@ -2,10 +2,10 @@ -- -- see: https://github.com/sol/hpack ----- hash: 9cf25d016d878667110e6394084d060d946ebb54650a1bb2b8786fd56371dc93+-- hash: d8b73793975417d05559e647f1e6239464f6261be7191fbb8ec438df38ca6548  name:           free-algebras-version:        0.0.3.0+version:        0.0.4.0 synopsis:       Free algebras in Haskell. description:    Universal algebra approach to free algebras including higher kinded algebraic structures like functors, applicative functors or monads. category:       Algebra, Control, Monads@@ -31,6 +31,11 @@   manual: True   default: False +flag documentation+  description: Add dependecies to link documentation+  manual: True+  default: False+ library   exposed-modules:       Control.Algebra.Free@@ -63,6 +68,31 @@     ghc-options: -Werror -Wall -Wincomplete-record-updates -Wincomplete-uni-patterns -Wredundant-constraints -Wno-deprecations   else     ghc-options: -Wall -Wincomplete-record-updates -Wincomplete-uni-patterns -Wredundant-constraints -Wno-deprecations+  if flag(documentation)+    build-depends:+        base >=4.11 && <5+      , constraints+      , containers+      , data-fix+      , free+      , groups+      , kan-extensions+      , mmorph+      , mtl+      , natural-numbers+      , transformers+  else+    build-depends:+        base >=4.11 && <5+      , constraints+      , containers+      , data-fix+      , free+      , groups+      , kan-extensions+      , mtl+      , natural-numbers+      , transformers   default-language: Haskell2010  test-suite free-algebras-test

@@ -75,9 +75,17 @@ -- constraint.  This functor is left adjoin to the forgetful functor (which is -- well defined if the laws on @'AlgebraType0'@ family are satisfied.  This in -- turn guarantees that @m@ composed with this forgetful functor is a monad.--- In result we get the monadic combinators: @'liftFree'@ (@'return'@ of--- this monad) and @'bindFree1'@ (its @'bind'@) and @'joinFree1'@ - its--- @'join'@ operator.+-- In result we get monadic operations:+-- +--   * @return = 'liftFree'@+--   * @(>>=)  = 'bindFree1'@+--   * @join   = 'joinFree1'@+--+-- For @m@ such that @'AlgebraType0'@ subsumes @'Monad'@ this class implies:+--+-- * @MFunctor@ via @hoist = hoistFree1@+-- * @MMonad@ via @embed = flip bindFree1@+-- * @MonadTrans@ via @lift = liftFree@ class FreeAlgebra1 (m :: (Type -> Type) -> Type -> Type) where     -- | Natural transformation that embeds generators into @m@.     liftFree :: AlgebraType0 m f => f a -> m f a@@ -95,7 +103,7 @@      -- |     -- A proof that @'AlgebraType' m (m f)@ holds for all @AlgebraType0 f => f@.-    -- Together with @hoistFree1@ this proves that @FreeAlgebra m => m@ is+    -- 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@.@@ -174,6 +182,10 @@ -- -- * @'Control.Applicative.Free.hoistAp' :: (forall a. f a -> g a) -> 'Ap' f b -> 'Ap' g b @ -- * @'Control.Monad.Free.hoistFree' :: 'Functor' g => (forall a. f a -> g a) -> 'Free' f b -> 'Free' g b@+-- * @Control.Monad.Morph.hoist@ for @'FreeAlgebra1' m => m@ such that+--   @'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@@ -223,6 +235,12 @@ -- | -- Bind operator for the @'joinFree1'@ monad, this is just @'foldNatFree'@ in -- disguise.+--+-- For @'Control.Monad.State.Lazy.StateT'@,+-- @'Control.Monad.Writer.Lazy.WriterT'@ or+-- @'Contorl.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

@@ -14,6 +14,10 @@     , joinFree     , bindFree     , cataFree+    , foldrFree+    , foldrFree'+    , foldlFree+    , foldlFree'     )     where @@ -23,7 +27,7 @@ import           Data.Fix (Fix, cata) import           Data.Kind (Constraint, Type) import           Data.List.NonEmpty (NonEmpty (..))-import           Data.Monoid (Monoid (..))+import           Data.Monoid (Endo (..), Monoid (..), Dual (..)) import           Data.Semigroup (Semigroup, (<>))  import           Data.Algebra.Pointed (Pointed (..))@@ -197,6 +201,72 @@          => Fix m          -> a cataFree = cata foldFree++-- |+-- 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+       , AlgebraType  m (Endo b)+       , AlgebraType0 m a+       )+    => (a -> b -> b)+    -> b+    -> m a+    -> b+foldrFree f z t = appEndo (foldMapFree (Endo . f) t) z++-- |+-- Like @'foldrFree'@ but strict.+foldrFree'+    :: forall m a b .+       ( FreeAlgebra  m+       , AlgebraType  m (Dual (Endo (b -> b)))+       , AlgebraType0 m a+       )+    => (a -> b -> b)+    -> m a+    -> b+    -> b+foldrFree' f xs z0 = foldlFree f' id xs z0+    where+    f' k x z = k $! f x z++-- |+-- Generalizes @'Data.Foldabale.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+       , AlgebraType  m (Dual (Endo b))+       , AlgebraType0 m a+       )+    => (b -> a -> b)+    -> b+    -> m a+    -> b+foldlFree f z t = appEndo (getDual (foldMapFree (Dual . Endo . flip f) t)) z++-- |+-- Like @'foldlFree'@ but strict.+foldlFree'+    :: forall m a b .+       ( FreeAlgebra  m+       , AlgebraType  m (Endo (b -> b))+       , AlgebraType0 m a+       )+    => (b -> a -> b)+    -> b+    -> m a+    -> b+foldlFree' f z0 xs = foldrFree f' id xs z0+    where+    f' x k z = k $! f z x  type instance AlgebraType0 NonEmpty a = () type instance AlgebraType  NonEmpty m = Semigroup m

@@ -5,11 +5,14 @@  -} module Data.Monoid.MSet     ( MSet+    , SSet (..)     , Endo (..)     , rep     , fact     , FreeMSet (..)     , hoistFreeMSet+    , foldrMSet+    , S (..)     ) where  import           Control.Monad (ap)@@ -24,8 +27,15 @@ import           Data.Ord (Down) import           Data.Set (Set) -import           Data.Semigroup.SSet (SSet (..), fact, rep)-import           Data.Algebra.Free (AlgebraType, AlgebraType0, FreeAlgebra (..), Proof (..), bindFree)+import           Data.Semigroup.SSet (SSet (..), S (..), fact, rep)+import           Data.Algebra.Free+    ( AlgebraType+    , AlgebraType0+    , FreeAlgebra (..)+    , Proof (..)+    , bindFree+    , foldrFree+    )  -- | -- Lawful instance should satisfy:@@ -84,6 +94,10 @@  instance MSet (Endo a) a +instance {-# OVERLAPPABLE #-} MSet m a => MSet (S m) a++instance {-# OVERLAPPING #-} MSet m b => MSet (S m) (Endo b)+ instance Monoid m => MSet (Sum Natural) m  instance MSet m a => MSet m (Const a b)@@ -113,6 +127,11 @@     act m (FreeMSet (h, a)) = FreeMSet $ (m <> h, a)  instance Monoid m => MSet m (FreeMSet m a)++-- |+-- @'foldrFree'@ for @'FreeMSet'@+foldrMSet :: forall m a b . MSet m b => (a -> b -> b) -> b -> (m, a) -> b+foldrMSet f b (m, a) = foldrFree f b (FreeMSet (S m, a))  type instance AlgebraType0 (FreeMSet m) a = () type instance AlgebraType  (FreeMSet m) a = MSet m a

@@ -5,6 +5,7 @@     ( SSet (..)     , rep     , fact+    , S (..)     ) where  import           Data.Semigroup (Endo (..), Sum (..))@@ -97,6 +98,22 @@  instance SSet (Endo a) a where     act (Endo f) a = f a++-- |+-- A newtype wrapper to avoid overlapping instances.+newtype S s = S { runS :: s }++instance Semigroup m => Semigroup (S m) where+    S s <> S s' = S $ s <> s'++instance Monoid m => Monoid (S m) where+    mempty = S mempty++instance {-# OVERLAPPABLE #-} SSet m a => SSet (S m) a where+    act (S m) a = act m a++instance {-# OVERLAPPABLE #-} SSet s a => SSet (S s) (Endo a) where+    act s (Endo f) = Endo $ act s . f  instance Monoid s => SSet (Sum Natural) s where     act (Sum 0) _ = mempty