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


-- | 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 Data.Bifoldable.Bifoldable Data.Functor.Base.ListF
instance Data.Bifoldable.Bifoldable Data.Functor.Base.NonEmptyF
instance Data.Bifoldable.Bifoldable Data.Functor.Base.TreeF
instance Data.Bifunctor.Bifunctor Data.Functor.Base.ListF
instance Data.Bifunctor.Bifunctor Data.Functor.Base.NonEmptyF
instance Data.Bifunctor.Bifunctor Data.Functor.Base.TreeF
instance Data.Bitraversable.Bitraversable Data.Functor.Base.ListF
instance Data.Bitraversable.Bitraversable Data.Functor.Base.NonEmptyF
instance Data.Bitraversable.Bitraversable Data.Functor.Base.TreeF
instance GHC.Classes.Eq a => Data.Functor.Classes.Eq1 (Data.Functor.Base.ListF a)
instance GHC.Classes.Eq a => Data.Functor.Classes.Eq1 (Data.Functor.Base.NonEmptyF a)
instance GHC.Classes.Eq a => Data.Functor.Classes.Eq1 (Data.Functor.Base.TreeF a)
instance Data.Functor.Classes.Eq2 Data.Functor.Base.ListF
instance Data.Functor.Classes.Eq2 Data.Functor.Base.NonEmptyF
instance Data.Functor.Classes.Eq2 Data.Functor.Base.TreeF
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.Functor.Base.ListF a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.Functor.Base.NonEmptyF a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.Functor.Base.TreeF a b)
instance GHC.Internal.Data.Foldable.Foldable (Data.Functor.Base.ListF a)
instance GHC.Internal.Data.Foldable.Foldable (Data.Functor.Base.NonEmptyF a)
instance GHC.Internal.Data.Foldable.Foldable (Data.Functor.Base.TreeF a)
instance GHC.Internal.Base.Functor (Data.Functor.Base.ListF a)
instance GHC.Internal.Base.Functor (Data.Functor.Base.NonEmptyF a)
instance GHC.Internal.Base.Functor (Data.Functor.Base.TreeF a)
instance GHC.Internal.Generics.Generic1 (Data.Functor.Base.ListF a)
instance GHC.Internal.Generics.Generic1 (Data.Functor.Base.NonEmptyF a)
instance GHC.Internal.Generics.Generic1 (Data.Functor.Base.TreeF a)
instance GHC.Internal.Generics.Generic (Data.Functor.Base.ListF a b)
instance GHC.Internal.Generics.Generic (Data.Functor.Base.NonEmptyF a b)
instance GHC.Internal.Generics.Generic (Data.Functor.Base.TreeF a b)
instance GHC.Classes.Ord a => Data.Functor.Classes.Ord1 (Data.Functor.Base.ListF a)
instance GHC.Classes.Ord a => Data.Functor.Classes.Ord1 (Data.Functor.Base.NonEmptyF a)
instance GHC.Classes.Ord a => Data.Functor.Classes.Ord1 (Data.Functor.Base.TreeF a)
instance Data.Functor.Classes.Ord2 Data.Functor.Base.ListF
instance Data.Functor.Classes.Ord2 Data.Functor.Base.NonEmptyF
instance Data.Functor.Classes.Ord2 Data.Functor.Base.TreeF
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Data.Functor.Base.ListF a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Data.Functor.Base.NonEmptyF a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Data.Functor.Base.TreeF a b)
instance GHC.Internal.Read.Read a => Data.Functor.Classes.Read1 (Data.Functor.Base.ListF a)
instance GHC.Internal.Read.Read a => Data.Functor.Classes.Read1 (Data.Functor.Base.NonEmptyF a)
instance GHC.Internal.Read.Read a => Data.Functor.Classes.Read1 (Data.Functor.Base.TreeF a)
instance Data.Functor.Classes.Read2 Data.Functor.Base.ListF
instance Data.Functor.Classes.Read2 Data.Functor.Base.NonEmptyF
instance Data.Functor.Classes.Read2 Data.Functor.Base.TreeF
instance (GHC.Internal.Read.Read a, GHC.Internal.Read.Read b) => GHC.Internal.Read.Read (Data.Functor.Base.ListF a b)
instance (GHC.Internal.Read.Read a, GHC.Internal.Read.Read b) => GHC.Internal.Read.Read (Data.Functor.Base.NonEmptyF a b)
instance (GHC.Internal.Read.Read a, GHC.Internal.Read.Read b) => GHC.Internal.Read.Read (Data.Functor.Base.TreeF a b)
instance GHC.Internal.Show.Show a => Data.Functor.Classes.Show1 (Data.Functor.Base.ListF a)
instance GHC.Internal.Show.Show a => Data.Functor.Classes.Show1 (Data.Functor.Base.NonEmptyF a)
instance GHC.Internal.Show.Show a => Data.Functor.Classes.Show1 (Data.Functor.Base.TreeF a)
instance Data.Functor.Classes.Show2 Data.Functor.Base.ListF
instance Data.Functor.Classes.Show2 Data.Functor.Base.NonEmptyF
instance Data.Functor.Classes.Show2 Data.Functor.Base.TreeF
instance (GHC.Internal.Show.Show a, GHC.Internal.Show.Show b) => GHC.Internal.Show.Show (Data.Functor.Base.ListF a b)
instance (GHC.Internal.Show.Show a, GHC.Internal.Show.Show b) => GHC.Internal.Show.Show (Data.Functor.Base.NonEmptyF a b)
instance (GHC.Internal.Show.Show a, GHC.Internal.Show.Show b) => GHC.Internal.Show.Show (Data.Functor.Base.TreeF a b)
instance GHC.Internal.Data.Traversable.Traversable (Data.Functor.Base.ListF a)
instance GHC.Internal.Data.Traversable.Traversable (Data.Functor.Base.NonEmptyF a)
instance GHC.Internal.Data.Traversable.Traversable (Data.Functor.Base.TreeF a)


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

-- | 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>. If that 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
($dmproject) :: (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
($dmembed) :: (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 GHC.Internal.Base.Functor f => Data.Functor.Foldable.Corecursive (Control.Comonad.Cofree.Cofree f a)
instance (GHC.Internal.Base.Functor w, GHC.Internal.Base.Functor f) => Data.Functor.Foldable.Corecursive (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance Data.Functor.Foldable.Corecursive (GHC.Internal.Data.Either.Either a b)
instance GHC.Internal.Base.Functor f => Data.Functor.Foldable.Corecursive (Control.Monad.Free.Church.F f a)
instance GHC.Internal.Base.Functor f => Data.Functor.Foldable.Corecursive (Data.Fix.Fix f)
instance GHC.Internal.Base.Functor f => Data.Functor.Foldable.Corecursive (Control.Monad.Free.Free f a)
instance (GHC.Internal.Base.Functor m, GHC.Internal.Base.Functor f) => Data.Functor.Foldable.Corecursive (Control.Monad.Trans.Free.FreeT f m a)
instance Data.Functor.Foldable.Corecursive [a]
instance Data.Functor.Foldable.Corecursive (GHC.Internal.Maybe.Maybe a)
instance GHC.Internal.Base.Functor f => Data.Functor.Foldable.Corecursive (Data.Fix.Mu f)
instance Data.Functor.Foldable.Corecursive GHC.Num.Natural.Natural
instance Data.Functor.Foldable.Corecursive (GHC.Internal.Base.NonEmpty a)
instance GHC.Internal.Base.Functor f => Data.Functor.Foldable.Corecursive (Data.Fix.Nu f)
instance Data.Functor.Foldable.Corecursive (Data.Tree.Tree a)
instance (Data.Functor.Foldable.GCoerce f g, Data.Functor.Foldable.GCoerce f' g') => Data.Functor.Foldable.GCoerce (f GHC.Internal.Generics.:*: f') (g GHC.Internal.Generics.:*: g')
instance (Data.Functor.Foldable.GCoerce f g, Data.Functor.Foldable.GCoerce f' g') => Data.Functor.Foldable.GCoerce (f GHC.Internal.Generics.:+: f') (g GHC.Internal.Generics.:+: g')
instance Data.Functor.Foldable.GCoerce (GHC.Internal.Generics.K1 i c) (GHC.Internal.Generics.K1 j c)
instance Data.Functor.Foldable.GCoerce f g => Data.Functor.Foldable.GCoerce (GHC.Internal.Generics.M1 i c f) (GHC.Internal.Generics.M1 i c' g)
instance Data.Functor.Foldable.GCoerce GHC.Internal.Generics.U1 GHC.Internal.Generics.U1
instance Data.Functor.Foldable.GCoerce GHC.Internal.Generics.V1 GHC.Internal.Generics.V1
instance GHC.Internal.Base.Functor f => Data.Functor.Foldable.Recursive (Control.Comonad.Cofree.Cofree f a)
instance (GHC.Internal.Base.Functor w, GHC.Internal.Base.Functor f) => Data.Functor.Foldable.Recursive (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance Data.Functor.Foldable.Recursive (GHC.Internal.Data.Either.Either a b)
instance GHC.Internal.Base.Functor f => Data.Functor.Foldable.Recursive (Control.Monad.Free.Church.F f a)
instance GHC.Internal.Base.Functor f => Data.Functor.Foldable.Recursive (Data.Fix.Fix f)
instance GHC.Internal.Base.Functor f => Data.Functor.Foldable.Recursive (Control.Monad.Free.Free f a)
instance (GHC.Internal.Base.Functor m, GHC.Internal.Base.Functor f) => Data.Functor.Foldable.Recursive (Control.Monad.Trans.Free.FreeT f m a)
instance Data.Functor.Foldable.Recursive [a]
instance Data.Functor.Foldable.Recursive (GHC.Internal.Maybe.Maybe a)
instance GHC.Internal.Base.Functor f => Data.Functor.Foldable.Recursive (Data.Fix.Mu f)
instance Data.Functor.Foldable.Recursive GHC.Num.Natural.Natural
instance Data.Functor.Foldable.Recursive (GHC.Internal.Base.NonEmpty a)
instance GHC.Internal.Base.Functor f => Data.Functor.Foldable.Recursive (Data.Fix.Nu f)
instance Data.Functor.Foldable.Recursive (Data.Tree.Tree a)

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 <a>Base</a> (Expr a) = ExprF a
--   
--   instance <a>Recursive</a> (Expr a) where
--       <a>project</a> (Lit x)   = LitF x
--       <a>project</a> (Add x y) = AddF x y
--       <a>project</a> (x :* y)  = x :*$ y
--   
--   instance <a>Corecursive</a> (Expr a) where
--       <a>embed</a> (LitF x)   = Lit x
--       <a>embed</a> (AddF x y) = Add x y
--       <a>embed</a> (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 <a>Base</a> (Rose f a) = RoseF f a
--   
--   instance Functor f =&gt; <a>Recursive</a> (Rose f a) where
--     <a>project</a> (Rose x xs) = RoseF x xs
--   
--   instance Functor f =&gt; <a>Corecursive</a> (Rose f a) where
--     <a>embed</a> (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 Language.Haskell.TH.Syntax.Dec
instance Data.Functor.Foldable.TH.MakeBaseFunctor a => Data.Functor.Foldable.TH.MakeBaseFunctor [a]
instance Data.Functor.Foldable.TH.MakeBaseFunctor Language.Haskell.TH.Syntax.Name
instance Data.Functor.Foldable.TH.MakeBaseFunctor a => Data.Functor.Foldable.TH.MakeBaseFunctor (Language.Haskell.TH.Syntax.Q a)
