yaya 0.2.1.0 → 0.2.1.2

raw patch · 15 files changed

+79/−218 lines, 15 filesdep −deriving-compatdep −hedgehogdep −yayadep ~base

Dependencies removed: deriving-compat, hedgehog, yaya, yaya-hedgehog

Dependency ranges changed: base

Files

• CHANGELOG.md +9/−0
• src/Yaya/Applied.hs +4/−4
• src/Yaya/Experimental/Foldable.hs +11/−9
• src/Yaya/Fold.hs +15/−11
• src/Yaya/Fold/Common.hs +9/−15
• src/Yaya/Fold/Native.hs +2/−0
• src/Yaya/Functor.hs +3/−3
• src/Yaya/Pattern.hs +6/−2
• src/Yaya/Zoo.hs +19/−19
• test/Test/Fold.hs +0/−29
• test/Test/Fold/Common.hs +0/−19
• test/Test/Fold/Retrofit.hs +0/−28
• test/Test/Retrofit.hs +0/−41
• test/test.hs +0/−19
• yaya.cabal +1/−19

@@ -4,6 +4,15 @@ The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/), and this project adheres to the [Haskell Package Versioning Policy](https://pvp.haskell.org/). +## 0.2.1.2 – 2019–11–08+### Changed+- improved documentation++## 0.2.1.1 – 2019–11–08+### Added+- documentation explaining limitations of `Mu`+- tests for `law_cataCompose` (which bumps the yaya-hedgehog dependency for tests)+ ## 0.2.1.0 – 2019–01–08 ### Added - exports of type class methods via `Yaya.Retrofit`

@@ -39,14 +39,14 @@ naturals :: (Steppable n Maybe, Corecursive t ((,) n)) => t naturals = ana (unarySequence succN) zeroN --- | Extracts _no more than_ `n` elements from the possibly-infinite sequence---  `s`.+-- | Extracts _no more than_ @n@ elements from the possibly-infinite sequence+--  @s@. takeUpTo   :: (Recursive n Maybe, Projectable s (XNor a), Steppable l (XNor a))   => n -> s -> l takeUpTo = cata (lowerDay (embed . takeAvailable)) --- | Extracts _exactly_ `n` elements from the infinite stream `s`.+-- | Extracts _exactly_ @n@ elements from the infinite stream @s@. take   :: (Recursive n Maybe, Projectable s ((,) a), Steppable l (XNor a))   => n -> s -> l@@ -95,7 +95,7 @@  -- | Lops off the branches of the tree below a certain depth, turning a --   potentially-infinite structure into a finite one. Like a generalized---  'take'.+--  `Yaya.Applied.take`. truncate   :: (Recursive n Maybe, Projectable t f, Steppable u (FreeF f ()), Functor f)   => n -> t -> u

@@ -1,8 +1,9 @@--- | This shows how 'Data.Foldable' is basically 'Recursive' specialized to---   lists. The true operation of 'Data.Foldable' is 'toList'.+-- | This shows how `Data.Foldable.Foldable` is basically `Recursive`+--   specialized to lists. The true operation of `Data.Foldable.Foldable` is+--  `Data.Foldable.toList`. -- --   As these few operations have the usual signatures, the rest of the type---   class can be implemented in the as in 'base'.+--   class can be implemented in the as in @base@. module Yaya.Experimental.Foldable where  import Control.Monad.Trans.Free@@ -15,8 +16,9 @@ foldMap = cata . lowerMonoid  -- | This class represents the ability of a structure to be converted to a---   list. It is equivalent to `Foldable`, but designed to illustrate the---   representation of `Foldable` as `Recursive` specialized to lists.+--   list. It is equivalent to `Data.Foldable.Foldable`, but designed to+--   illustrate the representation of `Data.Foldable.Foldable` as `Recursive`+--   specialized to lists. class Listable f where   naturalList :: f a b -> Free (XNor a) b   -- toColist :: (Projectable t (f a), Corecursive u (XNor a)) => t -> u@@ -24,10 +26,10 @@   -- toList :: (Recursive t (f a), Steppable u (XNor a)) => t -> u   -- toList = cata (embed . unFree . naturalList) --- FIXME: Use `cata . liftCoEnv`  instead of `iter`.+-- FIXME: Use @cata . liftCoEnv@  instead of `iter`. --- | This is simply `cata` applied to a list – the function is the `Cons`---   case, while the initial value is the `Nil` case.+-- | This is simply `cata` applied to a list – the function is the @Cons@+--   case, while the initial value is the @Nil@ case. foldr :: (Listable f, Recursive t (f a)) => (a -> b -> b) -> b -> t -> b foldr f b =   cata (iter (\case@@ -35,7 +37,7 @@                  Both a r -> f a r)         . naturalList) --- | Simply 'cata' with a carrier of 'b -> b'.+-- | Simply `cata` with a carrier of @b -> b@. foldl :: (Listable f, Recursive t (f a)) => (b -> a -> b) -> b -> t -> b foldl f =   flip

@@ -37,9 +37,9 @@ type Coalgebra f a = a -> f a type GCoalgebra m f a = a -> f (m a) type ElgotCoalgebra m f a = a -> m (f a)--- | Note that using a `CoalgebraM` “directly” is partial (e.g., with `anaM`).---   However, `ana . Compose` can accept a `CoalgebraM` and produce something---   like an effectful stream.+-- | Note that using a `CoalgebraM` “directly” is partial (e.g., with+--  `Yaya.Unsafe.Fold.anaM`). However, @ana . Compose@ can accept a `CoalgebraM`+--   and produce something like an effectful stream. type CoalgebraM m f a = a -> m (f a) type GCoalgebraM m n f a = a -> m (f (n a)) @@ -78,6 +78,10 @@   cata (showParen True . liftShowsPrec (const id) (foldMap id) prec)  -- | A fixed-point operator for inductive / finite data structures.+--+--  *NB*: This is only guaranteed to be finite when @f a@ is strict in @a@+--       (having strict functors won't prevent `Nu` from being lazy). Using+--       @-XStrictData@ can help with this a lot. data Mu f = Mu (forall a. Algebra f a -> a)  instance Functor f => Projectable (Mu f) f where@@ -173,7 +177,7 @@ cata2 :: (Recursive t f, Projectable u g) => Algebra (Day f g) a -> t -> u -> a cata2 = cata . lowerDay --- | Makes it possible to provide a 'GAlgebra' to 'cata'.+-- | Makes it possible to provide a `GAlgebra` to `cata`. lowerAlgebra   :: (Functor f, Comonad w)   => DistributiveLaw f w@@ -181,7 +185,7 @@   -> Algebra f (w a) lowerAlgebra k φ = fmap φ . k . fmap duplicate --- | Makes it possible to provide a 'GAlgebraM' to 'cataM'.+-- | Makes it possible to provide a `GAlgebraM` to `Yaya.Zoo.cataM`. lowerAlgebraM   :: (Applicative m, Traversable f, Comonad w, Traversable w)   => DistributiveLaw f w@@ -189,7 +193,7 @@   -> AlgebraM m f (w a) lowerAlgebraM k φ = traverse φ . k . fmap duplicate --- | Makes it possible to provide a 'GCoalgebra' to 'ana'.+-- | Makes it possible to provide a `GCoalgebra` to `ana`. lowerCoalgebra   :: (Functor f, Monad m)   => DistributiveLaw m f@@ -197,7 +201,7 @@   -> Coalgebra f (m a) lowerCoalgebra k ψ = fmap join . k . fmap ψ --- | Makes it possible to provide a 'GCoalgebraM' to 'anaM'.+-- | Makes it possible to provide a `GCoalgebraM` to `Yaya.Unsafe.Fold.anaM`. lowerCoalgebraM   :: (Applicative m, Traversable f, Monad n, Traversable n)   => DistributiveLaw n f@@ -316,10 +320,10 @@ ignoringAttribute φ = φ . lowerEnvT  -- | It is somewhat common to have a natural transformation that looks like---  `η :: forall a. f a -> Free g a`. This maps naturally to a `GCoalgebra` (to---   pass to `apo`) with `η . project`, but the desired `Algebra` is more likely---   to be `cata unFree . η` than `embed . η`. See yaya-streams for some---   examples of this.+--  @η :: forall a. f a -> Free g a@. This maps naturally to a `GCoalgebra` (to+--   pass to `Yaya.Zoo.apo`) with @η . project@, but the desired `Algebra` is+--   more likely to be @cata unFree . η@ than @embed . η@. See yaya-streams for+--   some examples of this. unFree :: Steppable t f => Algebra (FreeF f t) t unFree = \case   Pure t  -> t

@@ -14,41 +14,30 @@  import Yaya.Pattern --- | Converts the free monoid (a list) into some other monoid.+-- | Converts the free monoid (a list) into some other `Monoid`. lowerMonoid :: Monoid m => (a -> m) -> XNor a m -> m lowerMonoid f = \case   Neither  -> mempty   Both a b -> mappend (f a) b --- | Converts the free semigroup (a non-empty list) into some other semigroup.+-- | Converts the free semigroup (a non-empty list) into some other `Semigroup`. lowerSemigroup :: Semigroup m => (a -> m) -> AndMaybe a m -> m lowerSemigroup f = \case   Only a     -> f a   Indeed a b -> f a <> b +-- | Converts the free monad into some other `Monad`. lowerMonad :: Monad m => (forall a. f a -> m a) -> FreeF f a (m a) -> m a lowerMonad f = \case   Pure a  -> pure a   Free fm -> join (f fm) +-- | Provides equality over arbitrary pattern functors. equal :: (Functor f, Foldable f, Eq1 f) => Day f f Bool -> Bool equal (Day f1 f2 fn) =   liftEq (==) (void f1) (void f2)   && and (zipWith fn (toList f1) (toList f2)) --- -- | What we want here is a way we can get a--- --  `corecursiveEq :: t -> t -> Partial Bool`, so we can define (unsafe) `Eq`--- --   instances with `eq = runToEnd corecursiveEq`.--- coequal :: (Functor f, Foldable f, Eq1 f) => t -> t -> Either Bool [(t, t)]--- coequal a b =---   let fa = project a---       fb = project b---   in if liftEq (==) (void fa) (void fb)---      then case zip (toList fa) (toList fb) of---             [] -> Left True---             ps -> Right ps---      else Left False- -- TODO: Redefine this using `Natural` -- | When folded, returns the height of the data structure. height :: Foldable f => f Integer -> Integer@@ -61,6 +50,8 @@ size :: Foldable f => f Natural -> Natural size = foldr (+) 1 +-- | Converts a provably infinite structure into a `Yaya.Zoo.Partial` one (that+--   will never terminate). toRight :: Identity b -> Either a b toRight = Right . runIdentity @@ -68,11 +59,14 @@ while :: (a -> Maybe a) -> a -> Either a a while f a = maybe (Left a) Right $ f a +-- | Collapses a `Yaya.Zoo.Partial` structure to a value (probably requiring+--   unsafe instances). fromEither :: Either a a -> a fromEither = \case   Left a  -> a   Right a -> a +-- | Generates an infinite structure from an arbitrary seed. never :: a -> Identity a never = Identity 

@@ -13,6 +13,8 @@ import Yaya.Fold import Yaya.Pattern +-- | A fixed-point constructor that uses Haskell's built-in recursion. This is+--   lazy/corecursive. newtype Fix f = Fix { unFix :: f (Fix f) }  instance Projectable (Fix f) f where

@@ -4,16 +4,16 @@  import Data.Bifunctor --- | A functor from the category of endofunctors to *Hask*. The `D` is meant to+-- | A functor from the category of endofunctors to *Hask*. The @D@ is meant to --   be a mnemonic for “down”, as we’re “lowering” from endofunctors to types. class DFunctor (d :: (* -> *) -> *) where   dmap :: (forall a. f a -> g a) -> d f -> d g --- | This isn’t a Functor instance because of the position of the `a`, but you+-- | This isn’t a Functor instance because of the position of the @a@, but you --   can use it like: --   > newtype List a = List (Mu (XNor a)) --   > instance Functor List where---   >   map f (List mu) = List (firstMap f mu)+--   >   fmap f (List mu) = List (firstMap f mu) firstMap :: (DFunctor d, Bifunctor f) => (a -> b) -> d (f a) -> d (f b) firstMap f = dmap (first f) 

@@ -1,3 +1,6 @@+{-# LANGUAGE StrictData #-}++-- | Common pattern functors (and instances for them). module Yaya.Pattern where  import Control.Applicative@@ -18,7 +21,7 @@ import Numeric.Natural  -- | Isomorphic to 'Maybe (a, b)', it’s also the pattern functor for lists.-data XNor a b = Neither | Both a b deriving (Functor, Foldable, Traversable)+data XNor a b = Neither | Both ~a b deriving (Functor, Foldable, Traversable)  instance Bifunctor XNor where   bimap f g = \case@@ -27,7 +30,8 @@  -- | Isomorphic to `(a, Maybe b)`, it’s also the pattern functor for non-empty --   lists.-data AndMaybe a b = Only a | Indeed a b deriving (Functor, Foldable, Traversable)+data AndMaybe a b = Only a | Indeed ~a b+  deriving (Functor, Foldable, Traversable)  instance Bifunctor AndMaybe where   bimap f g = \case

@@ -35,7 +35,7 @@ cataM φ = cata (φ <=< sequenceA)  -- | A recursion scheme that allows to algebras to see each others’ results. (A---   generalization of 'zygo'.) This is an example that falls outside the scope+--   generalization of `zygo`.) This is an example that falls outside the scope --   of “comonadic folds”, but _would_ be covered by “adjoint folds”. mutu   :: (Recursive t f, Functor f)@@ -103,7 +103,7 @@ histo = gcata (distCofreeT id)  -- | A recursion scheme that gives you access to the original structure as you---   fold. (A specialization of 'zygo'.)+--   fold. (A specialization of `zygo`.) para   :: (Steppable t f, Recursive t f, Functor f)   => GAlgebra ((,) t) f a@@ -112,8 +112,8 @@ para = gcata (distTuple embed)  -- | A recursion scheme that uses a “helper algebra” to provide additional---   information when folding. (A generalization of 'para', and specialization---   of 'mutu'.)+--   information when folding. (A generalization of `para`, and specialization+--   of `mutu`.) zygo   :: (Recursive t f, Functor f)   => Algebra f b@@ -124,7 +124,7 @@  -- | This definition is different from the one given by `gcataM (distTuple φ')` --   because it has a monadic “helper” algebra. But at least it gives us the---   opportunity to show how 'zygo' is a specialization of 'mutu'.+--   opportunity to show how `zygo` is a specialization of `mutu`. zygoM   :: (Monad m, Recursive t f, Traversable f)   => AlgebraM m f b@@ -133,7 +133,7 @@   -> m a zygoM φ' φ = mutuM (φ' . fmap snd) φ --- | Potentially-infinite lists, like 'Data.List'.+-- | Potentially-infinite lists, like `[]`. type Colist a = Nu (XNor a)  -- | Finite lists.@@ -145,12 +145,12 @@ -- | Finite natural numbers. type Nat = Mu Maybe --- | Represents partial functions that may eventually return a value ('Left').+-- | Represents partial functions that may eventually return a value (`Left`). -- NB: This is a newtype so we can create the usual instances. newtype Partial a = Partial { fromPartial :: Nu (Either a) } --- TODO: There may be some way to do this over an arbitrary 'newtype', or at---       least a way to do it over an arbitrary 'Iso'.+-- TODO: There may be some way to do this over an arbitrary @newtype@, or at+--       least a way to do it over an arbitrary `Iso`. insidePartial :: (Nu (Either a) -> Nu (Either b)) -> Partial a -> Partial b insidePartial f = Partial . f . fromPartial @@ -171,16 +171,16 @@         insidePartial         $ elgotAna (seqEither project) ((fromPartial +++ Right) . project) --- | Always-infinite streams (as opposed to 'Colist', which _may_ terminate).+-- | Always-infinite streams (as opposed to `Colist`, which _may_ terminate). type Stream a = Nu ((,) a) --- | A more general implementation of 'fmap', because it can also work to, from,+-- | A more general implementation of `fmap`, because it can also work to, from, --   or within monomorphic structures, obviating the need for classes like---  'MonoFunctor'.+--  `Data.MonoTraversable.MonoFunctor`. map :: (Recursive t (f a), Steppable u (f b), Bifunctor f) => (a -> b) -> t -> u map f = cata (embed . first f) --- | A version of `map` that applies to Corecursive structures.+-- | A version of `Yaya.Zoo.map` that applies to Corecursive structures. comap   :: (Projectable t (f a), Corecursive u (f b), Bifunctor f)   => (a -> b)@@ -188,10 +188,10 @@   -> u comap f = ana (first f . project) --- | A more general implementation of 'traverse', because it can also work to,---   from, or within monomorphic structures, obviating the need for classes like---  'MonoTraversable'.--- TODO: Weaken the 'Monad' constraint to 'Applicative'.+-- TODO: Weaken the `Monad` constraint to `Applicative`.+-- | A more general implementation of `Data.Traversable.traverse`, because it+--   can also work to, from, or within monomorphic structures, obviating the+--   need for classes like `Data.MonoTraversable.MonoTraversable`. traverse   :: ( Recursive t (f a)      , Steppable u (f b)@@ -203,8 +203,8 @@   -> m u traverse f = cata (fmap embed . bitraverse f pure <=< sequenceA) --- | A more general implementation of 'contramap', because it can also work to,---   from, or within monomorphic structures.+-- | A more general implementation of `Data.Functor.contramap`, because it can+--   also work to, from, or within monomorphic structures. contramap   :: (Recursive t (f b), Steppable u (f a), Profunctor f)   => (a -> b)

@@ -1,29 +0,0 @@-{-# LANGUAGE TemplateHaskell #-}--module Test.Fold where--import           Hedgehog-import qualified Hedgehog.Gen as Gen--import           Yaya.Fold.Common-import           Yaya.Hedgehog.Expr-import           Yaya.Hedgehog.Fold--prop_muCataCancel :: Property-prop_muCataCancel =-  property $ law_cataCancel size =<< forAll (genExpr (Gen.sized genMuExpr))--prop_muCataRefl :: Property-prop_muCataRefl =-  property $ law_cataRefl =<< forAll (Gen.sized genMuExpr)---- prop_muCataCompose :: Property--- prop_muCataCompose =---   property $ law_cataCompose size id =<< forAll genMuExpr---- prop_nuAnaCancel :: Property--- prop_nuAnaCancel =---   property $ law_anaCancel size =<< forAll (genExpr (Gen.sized genNuExpr))--tests :: IO Bool-tests = checkParallel $$(discover)

@@ -1,19 +0,0 @@-{-# LANGUAGE TemplateHaskell #-}--module Test.Fold.Common where--import           Hedgehog-import qualified Hedgehog.Gen as Gen--import           Yaya.Fold-import           Yaya.Fold.Common-import           Yaya.Hedgehog.Expr--prop_heightLtSize :: Property-prop_heightLtSize =-  property-  (assert . uncurry (<) . fmap toInteger . cata (zipAlgebras height size)-   =<< forAll (Gen.sized genMuExpr))--tests :: IO Bool-tests = checkParallel $$(discover)

@@ -1,28 +0,0 @@-{-# LANGUAGE TemplateHaskell  #-}-{-# LANGUAGE TypeApplications #-}--module Test.Fold.Retrofit where--import           Hedgehog-import qualified Hedgehog.Gen as Gen--import           Yaya.Fold.Common-import           Yaya.Hedgehog.Expr-import           Yaya.Hedgehog.Fold--import           Test.Retrofit--prop_exprAnaRefl :: Property-prop_exprAnaRefl =-  property $ law_anaRefl =<< forAll (Gen.sized (expression @DExpr))--prop_exprCataCancel :: Property-prop_exprCataCancel =-  property $ law_cataCancel size =<< forAll (genExpr (Gen.sized (expression @DExpr)))--prop_exprCataRefl :: Property-prop_exprCataRefl =-  property $ law_cataRefl =<< forAll (Gen.sized (expression @DExpr))--tests :: IO Bool-tests = checkParallel $$(discover)

@@ -1,41 +0,0 @@--- | The point of this module is that it should compile _without_ importing any---   other Yaya modules.-module Test.Retrofit where--import qualified Yaya.Hedgehog.Expr as ExprF-import           Yaya.Retrofit--data DExpr-  = Lit Int-  | Add DExpr DExpr-  | Mult DExpr DExpr--instance Projectable DExpr ExprF.Expr where-  project = \case-    Lit i -> ExprF.Lit i-    Add a b -> ExprF.Add a b-    Mult a b -> ExprF.Mult a b--instance Steppable DExpr ExprF.Expr where-  embed = \case-    ExprF.Lit i -> Lit i-    ExprF.Add a b -> Add a b-    ExprF.Mult a b -> Mult a b--instance Corecursive DExpr ExprF.Expr where-  ana ψ = embed . fmap (ana ψ) . ψ---- | This is unsafe, but we really just want to make sure all the methods are---   available.-instance Recursive DExpr ExprF.Expr where-  cata φ = φ . fmap (cata φ) . project---- | This can be derived in this case, but we want to ensure we could define it---   if necessary.-instance Eq DExpr where-  (==) = recursiveEq---- | This can be derived in this case, but we want to ensure we could define it---   if necessary.-instance Show DExpr where-  showsPrec = recursiveShowsPrec

@@ -1,19 +0,0 @@-import           Control.Monad-import           System.Exit (exitFailure)-import           System.IO (BufferMode(..), hSetBuffering, stdout, stderr)--import qualified Test.Fold as Fold-import qualified Test.Fold.Common as Fold.Common-import qualified Test.Fold.Retrofit as Fold.Retrofit--main :: IO ()-main = do-  hSetBuffering stdout LineBuffering-  hSetBuffering stderr LineBuffering--  results <- sequence [ Fold.tests-                      , Fold.Common.tests-                      , Fold.Retrofit.tests-                      ]--  unless (and results) exitFailure

@@ -1,5 +1,5 @@ name:                yaya-version:             0.2.1.0+version:             0.2.1.2 synopsis:            Total recursion schemes. description:         Recursion schemes allow you to separate recursion from your                      business logic – making your own operations simpler, more@@ -55,24 +55,6 @@                      , RankNTypes                      , ScopedTypeVariables                      , TupleSections-  default-language:    Haskell2010--test-suite yaya-test-  type:                exitcode-stdio-1.0-  hs-source-dirs:      test-  main-is:             test.hs-  other-modules:       Test.Fold-                     , Test.Fold.Common-                     , Test.Fold.Retrofit-                     , Test.Retrofit-  build-depends:       base-                     , deriving-compat-                     , hedgehog-                     , yaya >= 0.1.0-                     , yaya-hedgehog >= 0.1.0-  default-extensions:  LambdaCase-                     , MultiParamTypeClasses-  ghc-options:         -threaded -rtsopts -with-rtsopts=-N -Wall   default-language:    Haskell2010  source-repository head