-- 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.2.2.2


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

-- | Base functor of <tt>[]</tt>.
data ListF a b
Nil :: ListF a b
Cons :: a -> b -> ListF a b

-- | 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

-- | Base functor for <a>Tree</a>.
data TreeF a b
NodeF :: a -> ForestF a b -> TreeF a b
type ForestF a b = [b]
instance GHC.Generics.Generic1 (Data.Functor.Base.ListF a)
instance GHC.Generics.Generic (Data.Functor.Base.ListF a b)
instance (GHC.Read.Read a, GHC.Read.Read b) => GHC.Read.Read (Data.Functor.Base.ListF a b)
instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Data.Functor.Base.ListF a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Data.Functor.Base.ListF a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.Functor.Base.ListF a 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 GHC.Generics.Generic1 (Data.Functor.Base.TreeF a)
instance GHC.Generics.Generic (Data.Functor.Base.TreeF a b)
instance (GHC.Read.Read a, GHC.Read.Read b) => GHC.Read.Read (Data.Functor.Base.TreeF a b)
instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Data.Functor.Base.TreeF a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Data.Functor.Base.TreeF a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.Functor.Base.TreeF a b)
instance Data.Functor.Classes.Eq2 Data.Functor.Base.TreeF
instance GHC.Classes.Eq a => Data.Functor.Classes.Eq1 (Data.Functor.Base.TreeF a)
instance Data.Functor.Classes.Ord2 Data.Functor.Base.TreeF
instance GHC.Classes.Ord a => Data.Functor.Classes.Ord1 (Data.Functor.Base.TreeF a)
instance GHC.Show.Show a => Data.Functor.Classes.Show1 (Data.Functor.Base.TreeF a)
instance Data.Functor.Classes.Show2 Data.Functor.Base.TreeF
instance Data.Functor.Classes.Read2 Data.Functor.Base.TreeF
instance GHC.Read.Read a => Data.Functor.Classes.Read1 (Data.Functor.Base.TreeF a)
instance GHC.Base.Functor (Data.Functor.Base.TreeF a)
instance Data.Foldable.Foldable (Data.Functor.Base.TreeF a)
instance Data.Traversable.Traversable (Data.Functor.Base.TreeF a)
instance Data.Bifunctor.Bifunctor Data.Functor.Base.TreeF
instance Data.Bifoldable.Bifoldable Data.Functor.Base.TreeF
instance Data.Bitraversable.Bitraversable Data.Functor.Base.TreeF
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
instance Data.Functor.Classes.Eq2 Data.Functor.Base.ListF
instance GHC.Classes.Eq a => Data.Functor.Classes.Eq1 (Data.Functor.Base.ListF a)
instance Data.Functor.Classes.Ord2 Data.Functor.Base.ListF
instance GHC.Classes.Ord a => Data.Functor.Classes.Ord1 (Data.Functor.Base.ListF a)
instance GHC.Show.Show a => Data.Functor.Classes.Show1 (Data.Functor.Base.ListF a)
instance Data.Functor.Classes.Show2 Data.Functor.Base.ListF
instance Data.Functor.Classes.Read2 Data.Functor.Base.ListF
instance GHC.Read.Read a => Data.Functor.Classes.Read1 (Data.Functor.Base.ListF a)
instance GHC.Base.Functor (Data.Functor.Base.ListF a)
instance Data.Foldable.Foldable (Data.Functor.Base.ListF a)
instance Data.Traversable.Traversable (Data.Functor.Base.ListF a)
instance Data.Bifunctor.Bifunctor Data.Functor.Base.ListF
instance Data.Bifoldable.Bifoldable Data.Functor.Base.ListF
instance Data.Bitraversable.Bitraversable Data.Functor.Base.ListF


module Data.Functor.Foldable

-- | Obtain the base functor for a recursive datatype.
--   
--   The core idea of this library is that instead of writing recursive
--   functions on a recursive datatype, we prefer to write non-recursive
--   functions on a related, non-recursive datatype we call the "base
--   functor".
--   
--   For example, <tt>[a]</tt> is a recursive type, and its corresponding
--   base functor is <tt><a>ListF</a> a</tt>:
--   
--   <pre>
--   data <a>ListF</a> a b = <a>Nil</a> | <a>Cons</a> a b
--   type instance <a>Base</a> [a] = <a>ListF</a> a
--   </pre>
--   
--   The relationship between those two types is that if we replace
--   <tt>b</tt> with <tt><a>ListF</a> a</tt>, we obtain a type which is
--   isomorphic to <tt>[a]</tt>.
type family Base t :: * -> *

-- | Base functor of <tt>[]</tt>.
data ListF a b
Nil :: ListF a b
Cons :: a -> b -> ListF a b

-- | A recursive datatype which can be unrolled one recursion layer at a
--   time.
--   
--   For example, a value of type <tt>[a]</tt> can be unrolled into a
--   <tt><a>ListF</a> a [a]</tt>. Ifthat unrolled value is a <a>Cons</a>,
--   it contains another <tt>[a]</tt> which can be unrolled as well, and so
--   on.
--   
--   Typically, <a>Recursive</a> types also have a <a>Corecursive</a>
--   instance, in which case <a>project</a> and <a>embed</a> are inverses.
class Functor (Base t) => Recursive t

-- | Unroll a single recursion layer.
--   
--   <pre>
--   &gt;&gt;&gt; project [1,2,3]
--   Cons 1 [2,3]
--   </pre>
project :: Recursive t => t -> Base t t

-- | Unroll a single recursion layer.
--   
--   <pre>
--   &gt;&gt;&gt; project [1,2,3]
--   Cons 1 [2,3]
--   </pre>
project :: (Recursive t, Generic t, Generic (Base t t), GCoerce (Rep t) (Rep (Base t t))) => t -> Base t t

-- | A recursive datatype which can be rolled up one recursion layer at a
--   time.
--   
--   For example, a value of type <tt><a>ListF</a> a [a]</tt> can be rolled
--   up into a <tt>[a]</tt>. This <tt>[a]</tt> can then be used in a
--   <a>Cons</a> to construct another <tt><a>ListF</a> a [a]</tt>, which
--   can be rolled up as well, and so on.
--   
--   Typically, <a>Corecursive</a> types also have a <a>Recursive</a>
--   instance, in which case <a>embed</a> and <a>project</a> are inverses.
class Functor (Base t) => Corecursive t

-- | Roll up a single recursion layer.
--   
--   <pre>
--   &gt;&gt;&gt; embed (Cons 1 [2,3])
--   [1,2,3]
--   </pre>
embed :: Corecursive t => Base t t -> t

-- | Roll up a single recursion layer.
--   
--   <pre>
--   &gt;&gt;&gt; embed (Cons 1 [2,3])
--   [1,2,3]
--   </pre>
embed :: (Corecursive t, Generic t, Generic (Base t t), GCoerce (Rep (Base t t)) (Rep t)) => Base t t -> t

-- | Folds a recursive type down to a value, one layer at a time.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   let mySum :: [Int] -&gt; Int
--       mySum = fold $ \case
--         Nil -&gt; 0
--         Cons x sumXs -&gt; x + sumXs
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; mySum [10,11,12]
--   33
--   </pre>
--   
--   In our running example, one layer consists of an <a>Int</a> and a list
--   of recursive positions. In <tt>Tree Int</tt>, those recursive
--   positions contain sub-trees of type <tt>Tree Int</tt>. Since we are
--   working one layer at a time, the <tt>Base t a -&gt; a</tt> function is
--   not given a <tt>Tree Int</tt>, but a <tt>TreeF Int String</tt>. That
--   is, each recursive position contains the <a>String</a> resulting from
--   recursively folding the corresponding sub-tree.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   let pprint1 :: Tree Int -&gt; String
--       pprint1 = fold $ \case
--         NodeF i [] -&gt; show i
--         NodeF i ss -&gt; show i ++ ": [" ++ intercalate ", " ss ++ "]"
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putStrLn $ pprint1 myTree
--   0: [1, 2, 3: [31: [311: [3111, 3112]]]]
--   </pre>
--   
--   More generally, the <tt>t</tt> argument is the recursive value, the
--   <tt>a</tt> is the final result, and the <tt>Base t a -&gt; a</tt>
--   function explains how to reduce a single layer full of recursive
--   results down to a result.
fold :: Recursive t => (Base t a -> a) -> t -> a

-- | An alias for <a>fold</a>.
--   
--   <a>fold</a> is by far the most common recursion-scheme, because
--   working one layer at a time is the most common strategy for writing a
--   recursive function. But there are also other, rarer strategies.
--   Researchers have given names to the most common strategies, and their
--   name for <a>fold</a> is "catamorphism". They also give its <tt>Base t
--   a -&gt; a</tt> argument a special name, "(<tt>Base t</tt>)-algebra".
--   More generally, a function of the form <tt>f a -&gt; a</tt> is called
--   an "f-algebra".
--   
--   The names might seem intimidating at first, but using the standard
--   nomenclature has benefits. If you program with others, it can be
--   useful to have a shared vocabulary to refer to those recursion
--   patterns. For example, you can discuss which type of recursion is the
--   most appropriate for the problem at hand. Names can also help to
--   structure your thoughts while writing recursive functions.
--   
--   The rest of this module lists a few of the other recursion-schemes
--   which are common enough to have a name. In this section, we restrict
--   our attention to those which fold a recursive structure down to a
--   value. In the examples all functions will be of type <tt>Tree Int
--   -&gt; String</tt>.
cata :: Recursive t => (Base t a -> a) -> t -> a

-- | A specialization of <a>cata</a> for effectful folds.
--   
--   <a>cataA</a> is the same as <a>cata</a>, but with a more specialized
--   type. The only reason it exists is to make it easier to discover how
--   to use this library with effects.
--   
--   For our running example, let's improve the output format of our
--   pretty-printer by using indentation. To do so, we will need to keep
--   track of the current indentation level. We will do so using a
--   <tt>Reader Int</tt> effect. Our recursive positions will thus contain
--   <tt>Reader Int String</tt> actions, not <tt>String</tt>s. This means
--   we need to run those actions in order to get the results.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   let pprint2 :: Tree Int -&gt; String
--       pprint2 = flip runReader 0 . cataA go
--         where
--           go :: TreeF Int (Reader Int String)
--              -&gt; Reader Int String
--           go (NodeF i rss) = do
--             -- rss :: [Reader Int String]
--             -- ss  :: [String]
--             ss &lt;- local (+ 2) $ sequence rss
--             indent &lt;- ask
--             let s = replicate indent ' ' ++ "* " ++ show i
--             pure $ intercalate "\n" (s : ss)
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putStrLn $ pprint2 myTree
--   * 0
--     * 1
--     * 2
--     * 3
--       * 31
--         * 311
--           * 3111
--           * 3112
--   </pre>
--   
--   The fact that the recursive positions contain <tt>Reader</tt> actions
--   instead of <a>String</a>s gives us some flexibility. Here, we are able
--   to increase the indentation by running those actions inside a
--   <tt>local</tt> block. More generally, we can control the order of
--   their side-effects, interleave them with other effects, etc.
--   
--   A similar technique is to specialize <a>cata</a> so that the result is
--   a function. This makes it possible for data to flow down in addition
--   to up. In this modified version of our running example, the
--   indentation level flows down from the root to the leaves, while the
--   resulting strings flow up from the leaves to the root.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   let pprint3 :: Tree Int -&gt; String
--       pprint3 t = cataA go t 0
--         where
--           go :: TreeF Int (Int -&gt; String)
--              -&gt; Int -&gt; String
--           go (NodeF i fs) indent
--               -- fs :: [Int -&gt; String]
--             = let indent' = indent + 2
--                   ss = map (\f -&gt; f indent') fs
--                   s = replicate indent ' ' ++ "* " ++ show i
--               in intercalate "\n" (s : ss)
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putStrLn $ pprint3 myTree
--   * 0
--     * 1
--     * 2
--     * 3
--       * 31
--         * 311
--           * 3111
--           * 3112
--   </pre>
cataA :: Recursive t => (Base t (f a) -> f a) -> t -> f a

-- | A variant of <a>cata</a> in which recursive positions also include the
--   original sub-tree, in addition to the result of folding that sub-tree.
--   
--   For our running example, let's add a number to each node indicating
--   how many children are below it. To do so, we will need to count those
--   nodes from the original sub-tree.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   let pprint4 :: Tree Int -&gt; String
--       pprint4 = flip runReader 0 . para go
--         where
--           go :: TreeF Int (Tree Int, Reader Int String)
--              -&gt; Reader Int String
--           go (NodeF i trss) = do
--             -- trss :: [(Tree Int, Reader Int String)]
--             -- ts   :: [Tree Int]
--             -- rss  :: [Reader Int String]
--             -- ss   :: [String]
--             let (ts, rss) = unzip trss
--             let count = sum $ fmap length ts
--             ss &lt;- local (+ 2) $ sequence rss
--             indent &lt;- ask
--             let s = replicate indent ' '
--                  ++ "* " ++ show i
--                  ++ " (" ++ show count ++ ")"
--             pure $ intercalate "\n" (s : ss)
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putStrLn $ pprint4 myTree
--   * 0 (7)
--     * 1 (0)
--     * 2 (0)
--     * 3 (4)
--       * 31 (3)
--         * 311 (2)
--           * 3111 (0)
--           * 3112 (0)
--   </pre>
--   
--   One common use for <a>para</a> is to construct a new tree which reuses
--   most of the sub-trees from the original. In the following example, we
--   insert a new node under the leftmost leaf. This requires allocating
--   new nodes along a path from the root to that leaf, while keeping every
--   other sub-tree untouched.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   let insertLeftmost :: Int -&gt; Tree Int -&gt; Tree Int
--       insertLeftmost new = para go
--         where
--           go :: TreeF Int (Tree Int, Tree Int)
--              -&gt; Tree Int
--           go (NodeF i []) = Node i [Node new []]
--           go (NodeF i ((_orig, recur) : tts))
--               -- tts :: [(Tree Int, Tree Int)]
--             = let (origs, _recurs) = unzip tts
--               in Node i (recur : origs)
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putStrLn $ pprint4 $ insertLeftmost 999 myTree
--   * 0 (8)
--     * 1 (1)
--       * 999 (0)
--     * 2 (0)
--     * 3 (4)
--       * 31 (3)
--         * 311 (2)
--           * 3111 (0)
--           * 3112 (0)
--   </pre>
para :: Recursive t => (Base t (t, a) -> a) -> t -> a

-- | A variant of <a>cata</a> which includes the results of all the
--   descendents, not just the direct children.
--   
--   Like <a>para</a>, a sub-tree is provided for each recursive position.
--   Each node in that sub-tree is annotated with the result for that
--   descendent. The <a>Cofree</a> type is used to add those annotations.
--   
--   For our running example, let's recreate GitHub's directory compression
--   algorithm. Notice that in <a>the repository for this package</a>,
--   GitHub displays <tt>src/Data/Functor</tt>, not <tt>src</tt>:
--   
--   
--   GitHub does this because <tt>src</tt> only contains one entry:
--   <tt>Data</tt>. Similarly, <tt>Data</tt> only contains one entry:
--   <tt>Functor</tt>. <tt>Functor</tt> contains several entries, so the
--   compression stops there. This helps users get to the interesting
--   folders more quickly.
--   
--   Before we use <a>histo</a>, we need to define a helper function
--   <tt>rollup</tt>. It collects nodes until it reaches a node which
--   doesn't have exactly one child. It also returns the labels of that
--   node's children.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   let rollup :: [Cofree (TreeF node) label]
--              -&gt; ([node], [label])
--       rollup [_ :&lt; NodeF node cofrees] =
--         let (nodes, label) = rollup cofrees
--         in (node : nodes, label)
--       rollup cofrees =
--         ([], fmap extract cofrees)
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let foobar xs = 1 :&lt; NodeF "foo" [2 :&lt; NodeF "bar" xs]
--   
--   &gt;&gt;&gt; rollup [foobar []]
--   (["foo","bar"],[])
--   
--   &gt;&gt;&gt; rollup [foobar [3 :&lt; NodeF "baz" [], 4 :&lt; NodeF "quux" []]]
--   (["foo","bar"],[3,4])
--   </pre>
--   
--   The value <tt>foobar []</tt> can be interpreted as the tree <tt>NodeF
--   "foo" [NodeF "bar" []]</tt>, plus two annotations. The <tt>"foo"</tt>
--   node is annotated with <tt>1</tt>, while the <tt>"bar"</tt> node is
--   annotated with <tt>2</tt>. When we call <a>histo</a> below, those
--   annotations are recursive results of type <tt>Int -&gt; String</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   let pprint5 :: Tree Int -&gt; String
--       pprint5 t = histo go t 0
--         where
--           go :: TreeF Int (Cofree (TreeF Int) (Int -&gt; String))
--              -&gt; Int -&gt; String
--           go (NodeF node cofrees) indent
--               -- cofrees :: [Cofree (TreeF Int) (Int -&gt; String)]
--               -- fs :: [Int -&gt; String]
--             = let indent' = indent + 2
--                   (nodes, fs) = rollup cofrees
--                   ss = map (\f -&gt; f indent') fs
--                   s = replicate indent ' '
--                    ++ "* " ++ intercalate " / " (fmap show (node : nodes))
--               in intercalate "\n" (s : ss)
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putStrLn $ pprint5 myTree
--   * 0
--     * 1
--     * 2
--     * 3 / 31 / 311
--       * 3111
--       * 3112
--   </pre>
--   
--   One common use for <a>histo</a> is to cache the value computed for
--   smaller sub-trees. In the Fibonacci example below, the recursive type
--   is <a>Natural</a>, which is isomorphic to <tt>[()]</tt>. Our annotated
--   sub-tree is thus isomorphic to a list of annotations. In our case,
--   each annotation is the result which was computed for a smaller number.
--   We thus have access to a list which caches all the Fibonacci numbers
--   we have computed so far.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   let fib :: Natural -&gt; Integer
--       fib = histo go
--         where
--           go :: Maybe (Cofree Maybe Integer) -&gt; Integer
--           go Nothing = 1
--           go (Just (_ :&lt; Nothing)) = 1
--           go (Just (fibNMinus1 :&lt; Just (fibNMinus2 :&lt; _)))
--             = fibNMinus1 + fibNMinus2
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fmap fib [0..10]
--   [1,1,2,3,5,8,13,21,34,55,89]
--   </pre>
--   
--   In general, <tt>Cofree f a</tt> can be thought of as a cache that has
--   the same shape as the recursive structure which was given as input.
histo :: Recursive t => (Base t (Cofree (Base t) a) -> a) -> t -> a
zygo :: Recursive t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a

-- | A generalization of <tt>unfoldr</tt>. The starting seed is expanded
--   into a base functor whose recursive positions contain more seeds,
--   which are themselves expanded, and so on.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   
--   &gt;&gt;&gt; let ourEnumFromTo :: Int -&gt; Int -&gt; [Int]
--   
--   &gt;&gt;&gt; ourEnumFromTo lo hi = ana go lo where
--   
--   &gt;&gt;&gt; go i = if i &gt; hi then Nil else Cons i (i + 1)
--   
--   &gt;&gt;&gt; :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; ourEnumFromTo 1 4
--   [1,2,3,4]
--   </pre>
unfold :: Corecursive t => (a -> Base t a) -> a -> t

-- | An alias for <a>unfold</a>.
ana :: Corecursive t => (a -> Base t a) -> a -> t
apo :: Corecursive t => (a -> Base t (Either t a)) -> a -> t
futu :: Corecursive t => (a -> Base t (Free (Base t) a)) -> a -> t

-- | An optimized version of <tt>fold f . unfold g</tt>.
--   
--   Useful when your recursion structure is shaped like a particular
--   recursive datatype, but you're neither consuming nor producing that
--   recursive datatype. For example, the recursion structure of quick sort
--   is a binary tree, but its input and output is a list, not a binary
--   tree.
--   
--   <pre>
--   &gt;&gt;&gt; data BinTreeF a b = Tip | Branch b a b deriving (Functor)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   
--   &gt;&gt;&gt; let quicksort :: Ord a =&gt; [a] -&gt; [a]
--   
--   &gt;&gt;&gt; quicksort = refold merge split where
--   
--   &gt;&gt;&gt; split []     = Tip
--   
--   &gt;&gt;&gt; split (x:xs) = let (l, r) = partition (&lt;x) xs in Branch l x r
--   
--   &gt;&gt;&gt; 
--   
--   &gt;&gt;&gt; merge Tip            = []
--   
--   &gt;&gt;&gt; merge (Branch l x r) = l ++ [x] ++ r
--   
--   &gt;&gt;&gt; :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; quicksort [1,5,2,8,4,9,8]
--   [1,2,4,5,8,8,9]
--   </pre>
refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b

-- | An alias for <a>refold</a>.
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
chrono :: Functor f => (f (Cofree f b) -> b) -> (a -> f (Free f a)) -> a -> b

-- | Convert from one recursive representation to another.
--   
--   <pre>
--   &gt;&gt;&gt; refix ["foo", "bar"] :: Fix (ListF String)
--   Fix (Cons "foo" (Fix (Cons "bar" (Fix Nil))))
--   </pre>
refix :: (Recursive s, Corecursive t, Base s ~ Base t) => s -> t

-- | Convert from one recursive type to another.
--   
--   <pre>
--   &gt;&gt;&gt; showTree $ hoist (\(NonEmptyF h t) -&gt; NodeF [h] (maybeToList t)) ( 'a' :| "bcd")
--   (a (b (c d)))
--   </pre>
hoist :: (Recursive s, Corecursive t) => (forall a. Base s a -> Base t a) -> s -> t

-- | 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' :: forall a b. (a -&gt; a -&gt; b) -&gt; [a] -&gt; [a] -&gt; [b]
--       zipWith' f xs ys = cotransverse g (Pair xs ys) where
--         g :: Pair (ListF a c) -&gt; ListF b (Pair c)
--         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

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

-- | Mendler-style recursion
mpara :: (forall y. (y -> c) -> (y -> Fix f) -> 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

-- | Mendler-style semi-mutual recursion
mzygo :: (forall y. (y -> b) -> f y -> b) -> (forall y. (y -> c) -> (y -> b) -> f y -> c) -> Fix f -> c

-- | Mendler-style coiteration
mana :: (forall y. (x -> y) -> x -> f y) -> x -> Fix f

-- | Mendler-style corecursion
mapo :: (forall y. (Fix f -> y) -> (x -> y) -> x -> f y) -> x -> Fix f

-- | Mendler-style course-of-values coiteration
mfutu :: (forall y. (f y -> y) -> (x -> y) -> x -> f y) -> x -> Fix f

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

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

-- | 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

-- | 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

-- | 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
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
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
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

-- | 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

-- | 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
gapo :: Corecursive t => (b -> Base t b) -> (a -> Base t (Either b 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

-- | 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

-- | 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
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
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

-- | 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
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)
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)
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)
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)
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)

-- | 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
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 (Data.Tree.Tree a)
instance Data.Functor.Foldable.Corecursive (Data.Tree.Tree 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.Fix.Fix f)
instance GHC.Base.Functor f => Data.Functor.Foldable.Corecursive (Data.Fix.Fix f)
instance GHC.Base.Functor f => Data.Functor.Foldable.Recursive (Data.Fix.Mu f)
instance GHC.Base.Functor f => Data.Functor.Foldable.Corecursive (Data.Fix.Mu f)
instance GHC.Base.Functor f => Data.Functor.Foldable.Corecursive (Data.Fix.Nu f)
instance GHC.Base.Functor f => Data.Functor.Foldable.Recursive (Data.Fix.Nu 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 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')

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>
--   
--   <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>.
--   
--   Allowing <a>makeBaseFunctor</a> to take both <a>Name</a>s and
--   <a>Dec</a>s as an argument is why it exists as a method in a type
--   class. For trickier data-types, like rose-tree (see also
--   <tt>Cofree</tt>):
--   
--   <pre>
--   data Rose f a = Rose a (f (Rose f a))
--   </pre>
--   
--   we can invoke <a>makeBaseFunctor</a> with an instance declaration to
--   provide needed context for instances. (c.f.
--   <tt>StandaloneDeriving</tt>)
--   
--   <pre>
--   <a>makeBaseFunctor</a> [d| instance Functor f =&gt; Recursive (Rose f a) |]
--   </pre>
--   
--   will create
--   
--   <pre>
--   data RoseF f a r = RoseF a (f fr)
--     deriving (<a>Functor</a>, <a>Foldable</a>, <a>Traversable</a>)
--   
--   type instance <tt>Base</tt> (Rose f a) = RoseF f a
--   
--   instance Functor f =&gt; <tt>Recursive</tt> (Rose f a) where
--     <tt>project</tt> (Rose x xs) = RoseF x xs
--   
--   instance Functor f =&gt; <tt>Corecursive</tt> (Rose f a) where
--     <tt>embed</tt> (RoseF x xs) = Rose x xs
--   </pre>
--   
--   Some doctests:
--   
--   <pre>
--   &gt;&gt;&gt; data Expr a = Lit a | Add (Expr a) (Expr a) | Expr a :* [Expr a]; makeBaseFunctor ''Expr
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :t AddF
--   AddF :: r -&gt; r -&gt; ExprF a r
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; data Rose f a = Rose a (f (Rose f a)); makeBaseFunctor $ asQ [d| instance Functor f =&gt; Recursive (Rose f a) |]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :t RoseF
--   RoseF :: a -&gt; f r -&gt; RoseF f a r
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let rose = Rose 1 (Just (Rose 2 (Just (Rose 3 Nothing))))
--   
--   &gt;&gt;&gt; cata (\(RoseF x f) -&gt; x + maybe 0 id f) rose
--   6
--   </pre>
class MakeBaseFunctor a

-- | <pre>
--   <a>makeBaseFunctor</a> = <a>makeBaseFunctorWith</a> <a>baseRules</a>
--   </pre>
makeBaseFunctor :: MakeBaseFunctor a => a -> DecsQ

-- | Build base functor with a custom configuration.
makeBaseFunctorWith :: MakeBaseFunctor a => BaseRules -> a -> 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
instance Data.Functor.Foldable.TH.MakeBaseFunctor a => Data.Functor.Foldable.TH.MakeBaseFunctor [a]
instance Data.Functor.Foldable.TH.MakeBaseFunctor a => Data.Functor.Foldable.TH.MakeBaseFunctor (Language.Haskell.TH.Syntax.Q a)
instance Data.Functor.Foldable.TH.MakeBaseFunctor Language.Haskell.TH.Syntax.Name
instance Data.Functor.Foldable.TH.MakeBaseFunctor Language.Haskell.TH.Syntax.Dec
