recursion 1.0.0.0 → 1.1.0.0

raw patch · 3 files changed

+47/−2 lines, 3 filesdep ~base

Dependency ranges changed: base

Files

• CHANGELOG.md +11/−0
• recursion.cabal +2/−2
• src/Control/Recursion.hs +34/−0

@@ -1,5 +1,16 @@ # recursion +## 1.1.0.0++* Add `NonEmptyF` and relevant instances+* Add `chema` for mutual recursion+* Drop support for GHC 7.10.3++## 1.0.0.0++* Rewrite completely in the style of `recursion-schemes`, making type inference+better.+ ## 0.1.1.0  * Add `dicata`

@@ -1,6 +1,6 @@ cabal-version: 1.18 name: recursion-version: 1.0.0.0+version: 1.1.0.0 license: BSD3 license-file: LICENSE copyright: Copyright: (c) 2018 Vanessa McHale@@ -36,7 +36,7 @@                       ExistentialQuantification RankNTypes TypeFamilies     ghc-options: -Wall     build-depends:-        base >=4.8 && <5,+        base >=4.9 && <5,         composition-prelude -any          if flag(development)

@@ -14,6 +14,7 @@     , Mu (..)     , Nu (..)     , ListF (..)+    , NonEmptyF (..)     -- * Recursion schemes     , hylo     , prepro@@ -28,6 +29,8 @@     , meta     , meta'     , dicata+    -- * Mutual recursion+    , chema     -- * Mendler-style recursion schemes     , mhisto     , mcata@@ -38,16 +41,22 @@     -- * Helper functions     , lambek     , colambek+    -- * Helper types+    , Lens'     ) where  import           Control.Arrow       ((&&&)) import           Control.Composition ((.*), (.**)) import           Control.Monad       ((<=<))+import           Data.Foldable       (toList)+import           Data.List.NonEmpty  (NonEmpty (..))+import qualified Data.List.NonEmpty  as NE import           Numeric.Natural     (Natural)  type family Base t :: * -> *  class (Functor (Base t)) => Recursive t where+     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))@@ -56,6 +65,7 @@   class (Functor (Base t)) => Corecursive t where+     embed :: Base t t -> t      -- | Anamorphism, meant to build up a structure recursively.@@ -67,12 +77,18 @@                | Nil                deriving (Functor) +data NonEmptyF a b = NonEmptyF a (Maybe b)+    deriving (Functor)+ newtype Fix f = Fix { unFix :: f (Fix f) }  data Nu f = forall a. Nu (a -> f a) a  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@@ -83,6 +99,8 @@  type instance Base [a] = ListF a +type instance Base (NonEmpty a) = NonEmptyF a+ instance Recursive Natural where     project 0 = Nothing     project n = Just (n-1)@@ -113,6 +131,14 @@     embed Nil         = []     embed (Cons x xs) = x : xs +instance Recursive (NonEmpty a) where+    project (x :| []) = NonEmptyF x Nothing+    project (x :| xs) = NonEmptyF x (Just (NE.fromList xs))++instance Corecursive (NonEmpty a) where+    embed (NonEmptyF x Nothing)   = x :| []+    embed (NonEmptyF x (Just xs)) = x :| toList xs+ -- | 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@@ -192,3 +218,11 @@ -- | Apomorphism 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 .*)