-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Representing common recursion patterns as higher-order functions
--   
--   Many recursive functions share the same structure, e.g. pattern-match
--   on the input and, depending on the data constructor, either recur on a
--   smaller input or terminate the recursion with the base case. Another
--   one: start with a seed value, use it to produce the first element of
--   an infinite list, and recur on a modified seed in order to produce the
--   rest of the list. Such a structure is called a recursion scheme. Using
--   higher-order functions to implement those recursion schemes makes your
--   code clearer, faster, and safer. See README for details.
@package recursion-schemes
@version 5.1.3


-- | Base Functors for standard types not already expressed as a fixed
--   point.
module Data.Functor.Base

-- | Base Functor for <a>NonEmpty</a>
data NonEmptyF a b
NonEmptyF :: a -> Maybe b -> NonEmptyF a b
[head] :: NonEmptyF a b -> a
[tail] :: NonEmptyF a b -> Maybe b
instance GHC.Generics.Generic1 (Data.Functor.Base.NonEmptyF a)
instance GHC.Generics.Generic (Data.Functor.Base.NonEmptyF a b)
instance (GHC.Read.Read a, GHC.Read.Read b) => GHC.Read.Read (Data.Functor.Base.NonEmptyF a b)
instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Data.Functor.Base.NonEmptyF a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Data.Functor.Base.NonEmptyF a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.Functor.Base.NonEmptyF a b)
instance Data.Functor.Classes.Eq2 Data.Functor.Base.NonEmptyF
instance GHC.Classes.Eq a => Data.Functor.Classes.Eq1 (Data.Functor.Base.NonEmptyF a)
instance Data.Functor.Classes.Ord2 Data.Functor.Base.NonEmptyF
instance GHC.Classes.Ord a => Data.Functor.Classes.Ord1 (Data.Functor.Base.NonEmptyF a)
instance GHC.Show.Show a => Data.Functor.Classes.Show1 (Data.Functor.Base.NonEmptyF a)
instance Data.Functor.Classes.Show2 Data.Functor.Base.NonEmptyF
instance Data.Functor.Classes.Read2 Data.Functor.Base.NonEmptyF
instance GHC.Read.Read a => Data.Functor.Classes.Read1 (Data.Functor.Base.NonEmptyF a)
instance GHC.Base.Functor (Data.Functor.Base.NonEmptyF a)
instance Data.Foldable.Foldable (Data.Functor.Base.NonEmptyF a)
instance Data.Traversable.Traversable (Data.Functor.Base.NonEmptyF a)
instance Data.Bifunctor.Bifunctor Data.Functor.Base.NonEmptyF
instance Data.Bifoldable.Bifoldable Data.Functor.Base.NonEmptyF
instance Data.Bitraversable.Bitraversable Data.Functor.Base.NonEmptyF


module Data.Functor.Foldable
type family Base t :: * -> *

-- | Base functor of <tt>[]</tt>.
data ListF a b
Nil :: ListF a b
Cons :: a -> b -> ListF a b
newtype Fix f
Fix :: f (Fix f) -> Fix f
unfix :: Fix f -> f (Fix f)
newtype Mu f
Mu :: (forall a. (f a -> a) -> a) -> Mu f

-- | A specialized, faster version of <a>hoist</a> for <a>Mu</a>.
hoistMu :: (forall a. f a -> g a) -> Mu f -> Mu g
data Nu f
[Nu] :: (a -> f a) -> a -> Nu f

-- | A specialized, faster version of <a>hoist</a> for <a>Nu</a>.
hoistNu :: (forall a. f a -> g a) -> Nu f -> Nu g
class Functor (Base t) => Recursive t
project :: Recursive t => t -> Base t t
project :: (Recursive t, Generic t, Generic (Base t t), GCoerce (Rep t) (Rep (Base t t))) => t -> Base t t
cata :: Recursive t => (Base t a -> a) -> t -> a
para :: Recursive t => (Base t (t, a) -> a) -> t -> a
gpara :: (Recursive t, Corecursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (EnvT t w a) -> a) -> t -> a

-- | Fokkinga's prepromorphism
prepro :: (Recursive t, Corecursive t) => (forall b. Base t b -> Base t b) -> (Base t a -> a) -> t -> a
gprepro :: (Recursive t, Corecursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (forall c. Base t c -> Base t c) -> (Base t (w a) -> a) -> t -> a
gapo :: Corecursive t => (b -> Base t b) -> (a -> Base t (Either b a)) -> a -> t

-- | A generalized catamorphism
gcata :: (Recursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (w a) -> a) -> t -> a
zygo :: Recursive t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a
gzygo :: (Recursive t, Comonad w) => (Base t b -> b) -> (forall c. Base t (w c) -> w (Base t c)) -> (Base t (EnvT b w a) -> a) -> t -> a

-- | Course-of-value iteration
histo :: Recursive t => (Base t (Cofree (Base t) a) -> a) -> t -> a
ghisto :: (Recursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (CofreeT (Base t) w a) -> a) -> t -> a
futu :: Corecursive t => (a -> Base t (Free (Base t) a)) -> a -> t
gfutu :: (Corecursive t, Functor m, Monad m) => (forall b. m (Base t b) -> Base t (m b)) -> (a -> Base t (FreeT (Base t) m a)) -> a -> t
chrono :: Functor f => (f (Cofree f b) -> b) -> (a -> f (Free f a)) -> a -> b
gchrono :: (Functor f, Functor w, Functor m, Comonad w, Monad m) => (forall c. f (w c) -> w (f c)) -> (forall c. m (f c) -> f (m c)) -> (f (CofreeT f w b) -> b) -> (a -> f (FreeT f m a)) -> a -> b
distCata :: Functor f => f (Identity a) -> Identity (f a)
distPara :: Corecursive t => Base t (t, a) -> (t, Base t a)
distParaT :: (Corecursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> Base t (EnvT t w a) -> EnvT t w (Base t a)
distZygo :: Functor f => (f b -> b) -> f (b, a) -> (b, f a)
distZygoT :: (Functor f, Comonad w) => (f b -> b) -> (forall c. f (w c) -> w (f c)) -> f (EnvT b w a) -> EnvT b w (f a)
distHisto :: Functor f => f (Cofree f a) -> Cofree f (f a)
distGHisto :: (Functor f, Functor h) => (forall b. f (h b) -> h (f b)) -> f (CofreeT f h a) -> CofreeT f h (f a)
distFutu :: Functor f => Free f (f a) -> f (Free f a)
distGFutu :: (Functor f, Functor h) => (forall b. h (f b) -> f (h b)) -> FreeT f h (f a) -> f (FreeT f h a)
class Functor (Base t) => Corecursive t
embed :: Corecursive t => Base t t -> t
embed :: (Corecursive t, Generic t, Generic (Base t t), GCoerce (Rep (Base t t)) (Rep t)) => Base t t -> t
ana :: Corecursive t => (a -> Base t a) -> a -> t
apo :: Corecursive t => (a -> Base t (Either t a)) -> a -> t

-- | Fokkinga's postpromorphism
postpro :: (Corecursive t, Recursive t) => (forall b. Base t b -> Base t b) -> (a -> Base t a) -> a -> t

-- | A generalized postpromorphism
gpostpro :: (Corecursive t, Recursive t, Monad m) => (forall b. m (Base t b) -> Base t (m b)) -> (forall c. Base t c -> Base t c) -> (a -> Base t (m a)) -> a -> t

-- | A generalized anamorphism
gana :: (Corecursive t, Monad m) => (forall b. m (Base t b) -> Base t (m b)) -> (a -> Base t (m a)) -> a -> t
distAna :: Functor f => Identity (f a) -> f (Identity a)
distApo :: Recursive t => Either t (Base t a) -> Base t (Either t a)
distGApo :: Functor f => (b -> f b) -> Either b (f a) -> f (Either b a)
distGApoT :: (Functor f, Functor m) => (b -> f b) -> (forall c. m (f c) -> f (m c)) -> ExceptT b m (f a) -> f (ExceptT b m a)
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b

-- | A generalized hylomorphism
ghylo :: (Comonad w, Functor f, Monad m) => (forall c. f (w c) -> w (f c)) -> (forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b
hoist :: (Recursive s, Corecursive t) => (forall a. Base s a -> Base t a) -> s -> t
refix :: (Recursive s, Corecursive t, Base s ~ Base t) => s -> t
fold :: Recursive t => (Base t a -> a) -> t -> a

-- | A generalized catamorphism
gfold :: (Recursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (w a) -> a) -> t -> a
unfold :: Corecursive t => (a -> Base t a) -> a -> t

-- | A generalized anamorphism
gunfold :: (Corecursive t, Monad m) => (forall b. m (Base t b) -> Base t (m b)) -> (a -> Base t (m a)) -> a -> t
refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b

-- | A generalized hylomorphism
grefold :: (Comonad w, Functor f, Monad m) => (forall c. f (w c) -> w (f c)) -> (forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b

-- | Mendler-style iteration
mcata :: (forall y. (y -> c) -> f y -> c) -> Fix f -> c

-- | Mendler-style course-of-value iteration
mhisto :: (forall y. (y -> c) -> (y -> f y) -> f y -> c) -> Fix f -> c

-- | Elgot algebras
elgot :: Functor f => (f a -> a) -> (b -> Either a (f b)) -> b -> a

-- | Elgot coalgebras:
--   <a>http://comonad.com/reader/2008/elgot-coalgebras/</a>
coelgot :: Functor f => ((a, f b) -> b) -> (a -> f a) -> a -> b

-- | Zygohistomorphic prepromorphisms:
--   
--   A corrected and modernized version of
--   <a>http://www.haskell.org/haskellwiki/Zygohistomorphic_prepromorphisms</a>
zygoHistoPrepro :: (Corecursive t, Recursive t) => (Base t b -> b) -> (forall c. Base t c -> Base t c) -> (Base t (EnvT b (Cofree (Base t)) a) -> a) -> t -> a

-- | Effectful <a>fold</a>.
--   
--   This is a type specialisation of <a>cata</a>.
--   
--   An example terminating a recursion immediately:
--   
--   <pre>
--   &gt;&gt;&gt; cataA (\alg -&gt; case alg of { Nil -&gt; pure (); Cons a _ -&gt; Const [a] })  "hello"
--   Const "h"
--   </pre>
cataA :: Recursive t => (Base t (f a) -> f a) -> t -> f a

-- | An effectful version of <a>hoist</a>.
--   
--   Properties:
--   
--   <pre>
--   <a>transverse</a> <a>sequenceA</a> = <a>pure</a>
--   </pre>
--   
--   Examples:
--   
--   The weird type of first argument allows user to decide an order of
--   sequencing:
--   
--   <pre>
--   &gt;&gt;&gt; transverse (\x -&gt; print (void x) *&gt; sequence x) "foo" :: IO String
--   Cons 'f' ()
--   Cons 'o' ()
--   Cons 'o' ()
--   Nil
--   "foo"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; transverse (\x -&gt; sequence x &lt;* print (void x)) "foo" :: IO String
--   Nil
--   Cons 'o' ()
--   Cons 'o' ()
--   Cons 'f' ()
--   "foo"
--   </pre>
transverse :: (Recursive s, Corecursive t, Functor f) => (forall a. Base s (f a) -> f (Base t a)) -> s -> f t

-- | A coeffectful version of <a>hoist</a>.
--   
--   Properties:
--   
--   <pre>
--   <a>cotransverse</a> <a>distAna</a> = <a>runIdentity</a>
--   </pre>
--   
--   Examples:
--   
--   Stateful transformations:
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   cotransverse
--     (\(u, b) -&gt; case b of
--       Nil -&gt; Nil
--       Cons x a -&gt; Cons (if u then toUpper x else x) (not u, a))
--     (True, "foobar") :: String
--   :}
--   "FoObAr"
--   </pre>
--   
--   We can implement a variant of <a>zipWith</a>
--   
--   <pre>
--   &gt;&gt;&gt; data Pair a = Pair a a deriving Functor
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   let zipWith' :: (a -&gt; a -&gt; b) -&gt; [a] -&gt; [a] -&gt; [b]
--       zipWith' f xs ys = cotransverse g (Pair xs ys) where
--         g (Pair Nil        _)          = Nil
--         g (Pair _          Nil)        = Nil
--         g (Pair (Cons x a) (Cons y b)) = Cons (f x y) (Pair a b)
--       :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; zipWith' (*) [1,2,3] [4,5,6]
--   [4,10,18]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; zipWith' (*) [1,2,3] [4,5,6,8]
--   [4,10,18]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; zipWith' (*) [1,2,3,3] [4,5,6]
--   [4,10,18]
--   </pre>
cotransverse :: (Recursive s, Corecursive t, Functor f) => (forall a. f (Base s a) -> Base t (f a)) -> f s -> t
instance GHC.Generics.Generic1 (Data.Functor.Foldable.ListF a)
instance GHC.Generics.Generic (Data.Functor.Foldable.ListF a b)
instance (GHC.Read.Read a, GHC.Read.Read b) => GHC.Read.Read (Data.Functor.Foldable.ListF a b)
instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Data.Functor.Foldable.ListF a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Data.Functor.Foldable.ListF a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.Functor.Foldable.ListF a b)
instance (Data.Typeable.Internal.Typeable f, Data.Data.Data (f (Data.Functor.Foldable.Fix f))) => Data.Data.Data (Data.Functor.Foldable.Fix f)
instance Data.Functor.Foldable.Recursive [a]
instance Data.Functor.Foldable.Corecursive [a]
instance Data.Functor.Foldable.Recursive (GHC.Base.NonEmpty a)
instance Data.Functor.Foldable.Corecursive (GHC.Base.NonEmpty a)
instance Data.Functor.Foldable.Recursive GHC.Natural.Natural
instance Data.Functor.Foldable.Corecursive GHC.Natural.Natural
instance GHC.Base.Functor f => Data.Functor.Foldable.Recursive (Control.Comonad.Cofree.Cofree f a)
instance GHC.Base.Functor f => Data.Functor.Foldable.Corecursive (Control.Comonad.Cofree.Cofree f a)
instance (GHC.Base.Functor w, GHC.Base.Functor f) => Data.Functor.Foldable.Recursive (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance (GHC.Base.Functor w, GHC.Base.Functor f) => Data.Functor.Foldable.Corecursive (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance GHC.Base.Functor f => Data.Functor.Foldable.Recursive (Control.Monad.Free.Free f a)
instance GHC.Base.Functor f => Data.Functor.Foldable.Corecursive (Control.Monad.Free.Free f a)
instance (GHC.Base.Functor m, GHC.Base.Functor f) => Data.Functor.Foldable.Recursive (Control.Monad.Trans.Free.FreeT f m a)
instance (GHC.Base.Functor m, GHC.Base.Functor f) => Data.Functor.Foldable.Corecursive (Control.Monad.Trans.Free.FreeT f m a)
instance Data.Functor.Foldable.Recursive (GHC.Maybe.Maybe a)
instance Data.Functor.Foldable.Corecursive (GHC.Maybe.Maybe a)
instance Data.Functor.Foldable.Recursive (Data.Either.Either a b)
instance Data.Functor.Foldable.Corecursive (Data.Either.Either a b)
instance GHC.Base.Functor f => Data.Functor.Foldable.Recursive (Data.Functor.Foldable.Fix f)
instance GHC.Base.Functor f => Data.Functor.Foldable.Corecursive (Data.Functor.Foldable.Fix f)
instance GHC.Base.Functor f => Data.Functor.Foldable.Recursive (Data.Functor.Foldable.Mu f)
instance GHC.Base.Functor f => Data.Functor.Foldable.Corecursive (Data.Functor.Foldable.Mu f)
instance GHC.Base.Functor f => Data.Functor.Foldable.Recursive (Control.Monad.Free.Church.F f a)
instance GHC.Base.Functor f => Data.Functor.Foldable.Corecursive (Control.Monad.Free.Church.F f a)
instance GHC.Base.Functor f => Data.Functor.Foldable.Corecursive (Data.Functor.Foldable.Nu f)
instance GHC.Base.Functor f => Data.Functor.Foldable.Recursive (Data.Functor.Foldable.Nu f)
instance Data.Functor.Foldable.GCoerce f g => Data.Functor.Foldable.GCoerce (GHC.Generics.M1 i c f) (GHC.Generics.M1 i c' g)
instance Data.Functor.Foldable.GCoerce (GHC.Generics.K1 i c) (GHC.Generics.K1 j c)
instance Data.Functor.Foldable.GCoerce GHC.Generics.U1 GHC.Generics.U1
instance Data.Functor.Foldable.GCoerce GHC.Generics.V1 GHC.Generics.V1
instance (Data.Functor.Foldable.GCoerce f g, Data.Functor.Foldable.GCoerce f' g') => Data.Functor.Foldable.GCoerce (f GHC.Generics.:*: f') (g GHC.Generics.:*: g')
instance (Data.Functor.Foldable.GCoerce f g, Data.Functor.Foldable.GCoerce f' g') => Data.Functor.Foldable.GCoerce (f GHC.Generics.:+: f') (g GHC.Generics.:+: g')
instance (GHC.Base.Functor f, Data.Functor.Classes.Eq1 f) => GHC.Classes.Eq (Data.Functor.Foldable.Nu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Ord1 f) => GHC.Classes.Ord (Data.Functor.Foldable.Nu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Show1 f) => GHC.Show.Show (Data.Functor.Foldable.Nu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Read1 f) => GHC.Read.Read (Data.Functor.Foldable.Nu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Eq1 f) => GHC.Classes.Eq (Data.Functor.Foldable.Mu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Ord1 f) => GHC.Classes.Ord (Data.Functor.Foldable.Mu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Show1 f) => GHC.Show.Show (Data.Functor.Foldable.Mu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Read1 f) => GHC.Read.Read (Data.Functor.Foldable.Mu f)
instance Data.Functor.Classes.Eq1 f => GHC.Classes.Eq (Data.Functor.Foldable.Fix f)
instance Data.Functor.Classes.Ord1 f => GHC.Classes.Ord (Data.Functor.Foldable.Fix f)
instance Data.Functor.Classes.Show1 f => GHC.Show.Show (Data.Functor.Foldable.Fix f)
instance Data.Functor.Classes.Read1 f => GHC.Read.Read (Data.Functor.Foldable.Fix f)
instance Data.Functor.Classes.Eq2 Data.Functor.Foldable.ListF
instance GHC.Classes.Eq a => Data.Functor.Classes.Eq1 (Data.Functor.Foldable.ListF a)
instance Data.Functor.Classes.Ord2 Data.Functor.Foldable.ListF
instance GHC.Classes.Ord a => Data.Functor.Classes.Ord1 (Data.Functor.Foldable.ListF a)
instance GHC.Show.Show a => Data.Functor.Classes.Show1 (Data.Functor.Foldable.ListF a)
instance Data.Functor.Classes.Show2 Data.Functor.Foldable.ListF
instance Data.Functor.Classes.Read2 Data.Functor.Foldable.ListF
instance GHC.Read.Read a => Data.Functor.Classes.Read1 (Data.Functor.Foldable.ListF a)
instance GHC.Base.Functor (Data.Functor.Foldable.ListF a)
instance Data.Foldable.Foldable (Data.Functor.Foldable.ListF a)
instance Data.Traversable.Traversable (Data.Functor.Foldable.ListF a)
instance Data.Bifunctor.Bifunctor Data.Functor.Foldable.ListF
instance Data.Bifoldable.Bifoldable Data.Functor.Foldable.ListF
instance Data.Bitraversable.Bitraversable Data.Functor.Foldable.ListF

module Data.Functor.Foldable.TH

-- | Build base functor with a sensible default configuration.
--   
--   <i>e.g.</i>
--   
--   <pre>
--   data Expr a
--       = Lit a
--       | Add (Expr a) (Expr a)
--       | Expr a :* [Expr a]
--     deriving (Show)
--   
--   <a>makeBaseFunctor</a> ''Expr
--   </pre>
--   
--   will create
--   
--   <pre>
--   data ExprF a x
--       = LitF a
--       | AddF x x
--       | x :*$ [x]
--     deriving (<a>Functor</a>, <a>Foldable</a>, <a>Traversable</a>)
--   
--   type instance <tt>Base</tt> (Expr a) = ExprF a
--   
--   instance <tt>Recursive</tt> (Expr a) where
--       <tt>project</tt> (Lit x)   = LitF x
--       <tt>project</tt> (Add x y) = AddF x y
--       <tt>project</tt> (x :* y)  = x :*$ y
--   
--   instance <tt>Corecursive</tt> (Expr a) where
--       <tt>embed</tt> (LitF x)   = Lit x
--       <tt>embed</tt> (AddF x y) = Add x y
--       <tt>embed</tt> (x :*$ y)  = x :* y
--   </pre>
--   
--   <pre>
--   <a>makeBaseFunctor</a> = <a>makeBaseFunctorWith</a> <a>baseRules</a>
--   </pre>
--   
--   <i>Notes:</i>
--   
--   <a>makeBaseFunctor</a> works properly only with ADTs. Existentials and
--   GADTs aren't supported, as we don't try to do better than <a>GHC's
--   DeriveFunctor</a>.
makeBaseFunctor :: Name -> DecsQ

-- | Build base functor with a custom configuration.
makeBaseFunctorWith :: BaseRules -> Name -> DecsQ

-- | Rules of renaming data names
data BaseRules

-- | Default <a>BaseRules</a>: append <tt>F</tt> or <tt>$</tt> to data
--   type, constructors and field names.
baseRules :: BaseRules

-- | How to name the base functor type.
--   
--   Default is to append <tt>F</tt> or <tt>$</tt>.
baseRulesType :: Functor f => ((Name -> Name) -> f (Name -> Name)) -> BaseRules -> f BaseRules

-- | How to rename the base functor type constructors.
--   
--   Default is to append <tt>F</tt> or <tt>$</tt>.
baseRulesCon :: Functor f => ((Name -> Name) -> f (Name -> Name)) -> BaseRules -> f BaseRules

-- | How to rename the base functor type field names (in records).
--   
--   Default is to append <tt>F</tt> or <tt>$</tt>.
baseRulesField :: Functor f => ((Name -> Name) -> f (Name -> Name)) -> BaseRules -> f BaseRules
