recursion 1.1.0.0 → 1.2.0.0
raw patch · 4 files changed
+34/−31 lines, 4 files
Files
- CHANGELOG.md +5/−0
- README.md +1/−1
- recursion.cabal +1/−1
- src/Control/Recursion.hs +27/−29
CHANGELOG.md view
@@ -1,5 +1,10 @@ # recursion +## 1.2.0.0++* Remove `chema`+* Add rewrite rules for `cata`/`ana`.+ ## 1.1.0.0 * Add `NonEmptyF` and relevant instances
README.md view
@@ -1,4 +1,4 @@-# yayo+# recursion This is heavily inspired by Edward Kmett's [recursion-schemes](http://hackage.haskell.org/package/recursion-schemes)
recursion.cabal view
@@ -1,6 +1,6 @@ cabal-version: 1.18 name: recursion-version: 1.1.0.0+version: 1.2.0.0 license: BSD3 license-file: LICENSE copyright: Copyright: (c) 2018 Vanessa McHale
src/Control/Recursion.hs view
@@ -29,8 +29,6 @@ , meta , meta' , dicata- -- * Mutual recursion- , chema -- * Mendler-style recursion schemes , mhisto , mcata@@ -41,8 +39,6 @@ -- * Helper functions , lambek , colambek- -- * Helper types- , Lens' ) where import Control.Arrow ((&&&))@@ -51,6 +47,7 @@ import Data.Foldable (toList) import Data.List.NonEmpty (NonEmpty (..)) import qualified Data.List.NonEmpty as NE+import Data.Traversable (Traversable (..)) import Numeric.Natural (Natural) type family Base t :: * -> *@@ -59,20 +56,10 @@ project :: t -> Base t t - -- | Catamorphism. Folds a structure. (see [here](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.125&rep=rep1&type=pdf))- cata :: (Base t a -> a) -> t -> a- cata f = c where c = f . fmap c . project-- class (Functor (Base t)) => Corecursive t where embed :: Base t t -> t - -- | Anamorphism, meant to build up a structure recursively.- ana :: (a -> Base t a) -> a -> t- ana g = a where a = embed . fmap a . g---- | Base functor for a list of type @[a]@. data ListF a b = Cons a b | Nil deriving (Functor)@@ -86,9 +73,6 @@ newtype Mu f = Mu (forall a. (f a -> a) -> a) --- | A map of \\( F \\)-coalgebras-type Lens' s a = forall f . Functor f => (a -> f a) -> s -> f s- type instance Base (Fix f) = f type instance Base (Mu f) = f@@ -114,11 +98,9 @@ instance Functor f => Corecursive (Nu f) where embed = colambek- ana = Nu instance Functor f => Recursive (Mu f) where project = lambek- cata f (Mu g) = g f instance Functor f => Corecursive (Mu f) where embed m = Mu (\f -> f (fmap (cata f) m))@@ -139,10 +121,34 @@ embed (NonEmptyF x Nothing) = x :| [] embed (NonEmptyF x (Just xs)) = x :| toList xs +-- | Catamorphism. Folds a structure. (see [here](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.125&rep=rep1&type=pdf))+cata :: (Recursive t) => (Base t a -> a) -> t -> a+cata f = c where c = f . fmap c . project+{-# NOINLINE [0] cata #-}++{-# RULES+ "cata/Mu" forall f (g :: forall a. (f a -> a) -> a). cata f (Mu g) = g f;+ #-}++-- | Anamorphism, meant to build up a structure recursively.+ana :: (Corecursive t) => (a -> Base t a) -> a -> t+ana g = a where a = embed . fmap a . g+{-# NOINLINE [0] ana #-}++{-# RULES+ "ana/Nu" forall (f :: a -> f a). ana f = Nu f;+ #-}++-- | Base functor for a list of type @[a]@. -- | Hylomorphism; fold a structure while buildiung it up. hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b hylo f g = h where h = f . fmap h . g+{-# NOINLINE [0] hylo #-} +{-# RULES+ "ana/cata/hylo" forall f g x. cata f (ana g x) = hylo f g x;+ #-}+ cataM :: (Recursive t, Traversable (Base t), Monad m) => (Base t a -> m a) -> t -> m a cataM f = c where c = f <=< (traverse c . project) @@ -207,7 +213,7 @@ elgot :: Functor f => (f a -> a) -> (b -> Either a (f b)) -> b -> a elgot phi psi = h where h = either id (phi . fmap h) . psi --- | Anamorphism allowing shortcuts.+-- | Anamorphism allowing shortcuts. Compare 'apo' micro :: (Corecursive a) => (b -> Either a (Base a b)) -> b -> a micro = elgot embed @@ -215,14 +221,6 @@ coelgot :: Functor f => ((a, f b) -> b) -> (a -> f a) -> a -> b coelgot phi psi = h where h = phi . ((,) <*> (fmap h . psi)) --- | Apomorphism+-- | Apomorphism. Compare 'micro'. apo :: (Corecursive t) => (a -> Base t (Either t a)) -> a -> t apo g = a where a = embed . fmap (either id a) . g---- Entangle two anamorphisms.-chema :: (Corecursive t')- => ((a -> f a) -> Lens' b b) -- ^ A lens parametric in an \\( F \\)-coalgebra that allows @b@ to inspect itself.- -> (a -> f a) -- ^ A @(Base t)@-coalgebra- -> (b -> Base t' b) -- ^ A @(Base t')@-coalgebra- -> b -> t'-chema = (ana .*)