-- 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 [].
data ListF a b
Nil :: ListF a b
Cons :: a -> b -> ListF a b
-- | Base Functor for NonEmpty
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 Tree.
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, [a] is a recursive type, and its corresponding
-- base functor is ListF a:
--
--
-- data ListF a b = Nil | Cons a b
-- type instance Base [a] = ListF a
--
--
-- The relationship between those two types is that if we replace
-- b with ListF a, we obtain a type which is
-- isomorphic to [a].
type family Base t :: * -> *
-- | Base functor of [].
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 [a] can be unrolled into a
-- ListF a [a]. Ifthat unrolled value is a Cons,
-- it contains another [a] which can be unrolled as well, and so
-- on.
--
-- Typically, Recursive types also have a Corecursive
-- instance, in which case project and embed are inverses.
class Functor (Base t) => Recursive t
-- | Unroll a single recursion layer.
--
--
-- >>> project [1,2,3]
-- Cons 1 [2,3]
--
project :: Recursive t => t -> Base t t
-- | Unroll a single recursion layer.
--
--
-- >>> project [1,2,3]
-- Cons 1 [2,3]
--
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 ListF a [a] can be rolled
-- up into a [a]. This [a] can then be used in a
-- Cons to construct another ListF a [a], which
-- can be rolled up as well, and so on.
--
-- Typically, Corecursive types also have a Recursive
-- instance, in which case embed and project are inverses.
class Functor (Base t) => Corecursive t
-- | Roll up a single recursion layer.
--
--
-- >>> embed (Cons 1 [2,3])
-- [1,2,3]
--
embed :: Corecursive t => Base t t -> t
-- | Roll up a single recursion layer.
--
--
-- >>> embed (Cons 1 [2,3])
-- [1,2,3]
--
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.
--
--
-- >>> :{
-- let mySum :: [Int] -> Int
-- mySum = fold $ \case
-- Nil -> 0
-- Cons x sumXs -> x + sumXs
-- :}
--
--
--
-- >>> mySum [10,11,12]
-- 33
--
--
-- In our running example, one layer consists of an Int and a list
-- of recursive positions. In Tree Int, those recursive
-- positions contain sub-trees of type Tree Int. Since we are
-- working one layer at a time, the Base t a -> a function is
-- not given a Tree Int, but a TreeF Int String. That
-- is, each recursive position contains the String resulting from
-- recursively folding the corresponding sub-tree.
--
--
-- >>> :{
-- let pprint1 :: Tree Int -> String
-- pprint1 = fold $ \case
-- NodeF i [] -> show i
-- NodeF i ss -> show i ++ ": [" ++ intercalate ", " ss ++ "]"
-- :}
--
--
--
-- >>> putStrLn $ pprint1 myTree
-- 0: [1, 2, 3: [31: [311: [3111, 3112]]]]
--
--
-- More generally, the t argument is the recursive value, the
-- a is the final result, and the Base t a -> a
-- 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 fold.
--
-- fold 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 fold is "catamorphism". They also give its Base t
-- a -> a argument a special name, "(Base t)-algebra".
-- More generally, a function of the form f a -> a 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 Tree Int
-- -> String.
cata :: Recursive t => (Base t a -> a) -> t -> a
-- | A specialization of cata for effectful folds.
--
-- cataA is the same as cata, 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
-- Reader Int effect. Our recursive positions will thus contain
-- Reader Int String actions, not Strings. This means
-- we need to run those actions in order to get the results.
--
--
-- >>> :{
-- let pprint2 :: Tree Int -> String
-- pprint2 = flip runReader 0 . cataA go
-- where
-- go :: TreeF Int (Reader Int String)
-- -> Reader Int String
-- go (NodeF i rss) = do
-- -- rss :: [Reader Int String]
-- -- ss :: [String]
-- ss <- local (+ 2) $ sequence rss
-- indent <- ask
-- let s = replicate indent ' ' ++ "* " ++ show i
-- pure $ intercalate "\n" (s : ss)
-- :}
--
--
--
-- >>> putStrLn $ pprint2 myTree
-- * 0
-- * 1
-- * 2
-- * 3
-- * 31
-- * 311
-- * 3111
-- * 3112
--
--
-- The fact that the recursive positions contain Reader actions
-- instead of Strings gives us some flexibility. Here, we are able
-- to increase the indentation by running those actions inside a
-- local block. More generally, we can control the order of
-- their side-effects, interleave them with other effects, etc.
--
-- A similar technique is to specialize cata 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.
--
--
-- >>> :{
-- let pprint3 :: Tree Int -> String
-- pprint3 t = cataA go t 0
-- where
-- go :: TreeF Int (Int -> String)
-- -> Int -> String
-- go (NodeF i fs) indent
-- -- fs :: [Int -> String]
-- = let indent' = indent + 2
-- ss = map (\f -> f indent') fs
-- s = replicate indent ' ' ++ "* " ++ show i
-- in intercalate "\n" (s : ss)
-- :}
--
--
--
-- >>> putStrLn $ pprint3 myTree
-- * 0
-- * 1
-- * 2
-- * 3
-- * 31
-- * 311
-- * 3111
-- * 3112
--
cataA :: Recursive t => (Base t (f a) -> f a) -> t -> f a
-- | A variant of cata 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.
--
--
-- >>> :{
-- let pprint4 :: Tree Int -> String
-- pprint4 = flip runReader 0 . para go
-- where
-- go :: TreeF Int (Tree Int, Reader Int String)
-- -> 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 <- local (+ 2) $ sequence rss
-- indent <- ask
-- let s = replicate indent ' '
-- ++ "* " ++ show i
-- ++ " (" ++ show count ++ ")"
-- pure $ intercalate "\n" (s : ss)
-- :}
--
--
--
-- >>> putStrLn $ pprint4 myTree
-- * 0 (7)
-- * 1 (0)
-- * 2 (0)
-- * 3 (4)
-- * 31 (3)
-- * 311 (2)
-- * 3111 (0)
-- * 3112 (0)
--
--
-- One common use for para 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.
--
--
-- >>> :{
-- let insertLeftmost :: Int -> Tree Int -> Tree Int
-- insertLeftmost new = para go
-- where
-- go :: TreeF Int (Tree Int, Tree Int)
-- -> 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)
-- :}
--
--
--
-- >>> putStrLn $ pprint4 $ insertLeftmost 999 myTree
-- * 0 (8)
-- * 1 (1)
-- * 999 (0)
-- * 2 (0)
-- * 3 (4)
-- * 31 (3)
-- * 311 (2)
-- * 3111 (0)
-- * 3112 (0)
--
para :: Recursive t => (Base t (t, a) -> a) -> t -> a
-- | A variant of cata which includes the results of all the
-- descendents, not just the direct children.
--
-- Like para, a sub-tree is provided for each recursive position.
-- Each node in that sub-tree is annotated with the result for that
-- descendent. The Cofree type is used to add those annotations.
--
-- For our running example, let's recreate GitHub's directory compression
-- algorithm. Notice that in the repository for this package,
-- GitHub displays src/Data/Functor, not src:
--
--
-- GitHub does this because src only contains one entry:
-- Data. Similarly, Data only contains one entry:
-- Functor. Functor contains several entries, so the
-- compression stops there. This helps users get to the interesting
-- folders more quickly.
--
-- Before we use histo, we need to define a helper function
-- rollup. 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.
--
--
-- >>> :{
-- let rollup :: [Cofree (TreeF node) label]
-- -> ([node], [label])
-- rollup [_ :< NodeF node cofrees] =
-- let (nodes, label) = rollup cofrees
-- in (node : nodes, label)
-- rollup cofrees =
-- ([], fmap extract cofrees)
-- :}
--
--
--
-- >>> let foobar xs = 1 :< NodeF "foo" [2 :< NodeF "bar" xs]
--
-- >>> rollup [foobar []]
-- (["foo","bar"],[])
--
-- >>> rollup [foobar [3 :< NodeF "baz" [], 4 :< NodeF "quux" []]]
-- (["foo","bar"],[3,4])
--
--
-- The value foobar [] can be interpreted as the tree NodeF
-- "foo" [NodeF "bar" []], plus two annotations. The "foo"
-- node is annotated with 1, while the "bar" node is
-- annotated with 2. When we call histo below, those
-- annotations are recursive results of type Int -> String.
--
--
-- >>> :{
-- let pprint5 :: Tree Int -> String
-- pprint5 t = histo go t 0
-- where
-- go :: TreeF Int (Cofree (TreeF Int) (Int -> String))
-- -> Int -> String
-- go (NodeF node cofrees) indent
-- -- cofrees :: [Cofree (TreeF Int) (Int -> String)]
-- -- fs :: [Int -> String]
-- = let indent' = indent + 2
-- (nodes, fs) = rollup cofrees
-- ss = map (\f -> f indent') fs
-- s = replicate indent ' '
-- ++ "* " ++ intercalate " / " (fmap show (node : nodes))
-- in intercalate "\n" (s : ss)
-- :}
--
--
--
-- >>> putStrLn $ pprint5 myTree
-- * 0
-- * 1
-- * 2
-- * 3 / 31 / 311
-- * 3111
-- * 3112
--
--
-- One common use for histo is to cache the value computed for
-- smaller sub-trees. In the Fibonacci example below, the recursive type
-- is Natural, which is isomorphic to [()]. 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.
--
--
-- >>> :{
-- let fib :: Natural -> Integer
-- fib = histo go
-- where
-- go :: Maybe (Cofree Maybe Integer) -> Integer
-- go Nothing = 1
-- go (Just (_ :< Nothing)) = 1
-- go (Just (fibNMinus1 :< Just (fibNMinus2 :< _)))
-- = fibNMinus1 + fibNMinus2
-- :}
--
--
--
-- >>> fmap fib [0..10]
-- [1,1,2,3,5,8,13,21,34,55,89]
--
--
-- In general, Cofree f a 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 unfoldr. The starting seed is expanded
-- into a base functor whose recursive positions contain more seeds,
-- which are themselves expanded, and so on.
--
--
-- >>> :{
--
-- >>> let ourEnumFromTo :: Int -> Int -> [Int]
--
-- >>> ourEnumFromTo lo hi = ana go lo where
--
-- >>> go i = if i > hi then Nil else Cons i (i + 1)
--
-- >>> :}
--
--
--
-- >>> ourEnumFromTo 1 4
-- [1,2,3,4]
--
unfold :: Corecursive t => (a -> Base t a) -> a -> t
-- | An alias for unfold.
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 fold f . unfold g.
--
-- 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.
--
--
-- >>> data BinTreeF a b = Tip | Branch b a b deriving (Functor)
--
--
--
-- >>> :{
--
-- >>> let quicksort :: Ord a => [a] -> [a]
--
-- >>> quicksort = refold merge split where
--
-- >>> split [] = Tip
--
-- >>> split (x:xs) = let (l, r) = partition (<x) xs in Branch l x r
--
-- >>>
--
-- >>> merge Tip = []
--
-- >>> merge (Branch l x r) = l ++ [x] ++ r
--
-- >>> :}
--
--
--
-- >>> quicksort [1,5,2,8,4,9,8]
-- [1,2,4,5,8,8,9]
--
refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
-- | An alias for refold.
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.
--
--
-- >>> refix ["foo", "bar"] :: Fix (ListF String)
-- Fix (Cons "foo" (Fix (Cons "bar" (Fix Nil))))
--
refix :: (Recursive s, Corecursive t, Base s ~ Base t) => s -> t
-- | Convert from one recursive type to another.
--
--
-- >>> showTree $ hoist (\(NonEmptyF h t) -> NodeF [h] (maybeToList t)) ( 'a' :| "bcd")
-- (a (b (c d)))
--
hoist :: (Recursive s, Corecursive t) => (forall a. Base s a -> Base t a) -> s -> t
-- | An effectful version of hoist.
--
-- Properties:
--
--
-- transverse sequenceA = pure
--
--
-- Examples:
--
-- The weird type of first argument allows user to decide an order of
-- sequencing:
--
--
-- >>> transverse (\x -> print (void x) *> sequence x) "foo" :: IO String
-- Cons 'f' ()
-- Cons 'o' ()
-- Cons 'o' ()
-- Nil
-- "foo"
--
--
--
-- >>> transverse (\x -> sequence x <* print (void x)) "foo" :: IO String
-- Nil
-- Cons 'o' ()
-- Cons 'o' ()
-- Cons 'f' ()
-- "foo"
--
transverse :: (Recursive s, Corecursive t, Functor f) => (forall a. Base s (f a) -> f (Base t a)) -> s -> f t
-- | A coeffectful version of hoist.
--
-- Properties:
--
--
-- cotransverse distAna = runIdentity
--
--
-- Examples:
--
-- Stateful transformations:
--
--
-- >>> :{
-- cotransverse
-- (\(u, b) -> case b of
-- Nil -> Nil
-- Cons x a -> Cons (if u then toUpper x else x) (not u, a))
-- (True, "foobar") :: String
-- :}
-- "FoObAr"
--
--
-- We can implement a variant of zipWith
--
--
-- >>> data Pair a = Pair a a deriving Functor
--
--
--
-- >>> :{
-- let zipWith' :: forall a b. (a -> a -> b) -> [a] -> [a] -> [b]
-- zipWith' f xs ys = cotransverse g (Pair xs ys) where
-- g :: Pair (ListF a c) -> 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)
-- :}
--
--
--
-- >>> zipWith' (*) [1,2,3] [4,5,6]
-- [4,10,18]
--
--
--
-- >>> zipWith' (*) [1,2,3] [4,5,6,8]
-- [4,10,18]
--
--
--
-- >>> zipWith' (*) [1,2,3,3] [4,5,6]
-- [4,10,18]
--
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:
-- http://comonad.com/reader/2008/elgot-coalgebras/
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
-- http://www.haskell.org/haskellwiki/Zygohistomorphic_prepromorphisms
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.
--
-- e.g.
--
--
-- data Expr a
-- = Lit a
-- | Add (Expr a) (Expr a)
-- | Expr a :* [Expr a]
-- deriving (Show)
--
-- makeBaseFunctor ''Expr
--
--
-- will create
--
--
-- data ExprF a x
-- = LitF a
-- | AddF x x
-- | x :*$ [x]
-- deriving (Functor, Foldable, Traversable)
--
-- type instance Base (Expr a) = ExprF a
--
-- instance Recursive (Expr a) where
-- project (Lit x) = LitF x
-- project (Add x y) = AddF x y
-- project (x :* y) = x :*$ y
--
-- instance Corecursive (Expr a) where
-- embed (LitF x) = Lit x
-- embed (AddF x y) = Add x y
-- embed (x :*$ y) = x :* y
--
--
-- Notes:
--
-- makeBaseFunctor works properly only with ADTs. Existentials and
-- GADTs aren't supported, as we don't try to do better than GHC's
-- DeriveFunctor.
--
-- Allowing makeBaseFunctor to take both Names and
-- Decs as an argument is why it exists as a method in a type
-- class. For trickier data-types, like rose-tree (see also
-- Cofree):
--
--
-- data Rose f a = Rose a (f (Rose f a))
--
--
-- we can invoke makeBaseFunctor with an instance declaration to
-- provide needed context for instances. (c.f.
-- StandaloneDeriving)
--
--
-- makeBaseFunctor [d| instance Functor f => Recursive (Rose f a) |]
--
--
-- will create
--
--
-- data RoseF f a r = RoseF a (f fr)
-- deriving (Functor, Foldable, Traversable)
--
-- type instance Base (Rose f a) = RoseF f a
--
-- instance Functor f => Recursive (Rose f a) where
-- project (Rose x xs) = RoseF x xs
--
-- instance Functor f => Corecursive (Rose f a) where
-- embed (RoseF x xs) = Rose x xs
--
--
-- Some doctests:
--
--
-- >>> data Expr a = Lit a | Add (Expr a) (Expr a) | Expr a :* [Expr a]; makeBaseFunctor ''Expr
--
--
--
-- >>> :t AddF
-- AddF :: r -> r -> ExprF a r
--
--
--
-- >>> data Rose f a = Rose a (f (Rose f a)); makeBaseFunctor $ asQ [d| instance Functor f => Recursive (Rose f a) |]
--
--
--
-- >>> :t RoseF
-- RoseF :: a -> f r -> RoseF f a r
--
--
--
-- >>> let rose = Rose 1 (Just (Rose 2 (Just (Rose 3 Nothing))))
--
-- >>> cata (\(RoseF x f) -> x + maybe 0 id f) rose
-- 6
--
class MakeBaseFunctor a
-- |
-- makeBaseFunctor = makeBaseFunctorWith baseRules
--
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 BaseRules: append F or $ to data
-- type, constructors and field names.
baseRules :: BaseRules
-- | How to name the base functor type.
--
-- Default is to append F or $.
baseRulesType :: Functor f => ((Name -> Name) -> f (Name -> Name)) -> BaseRules -> f BaseRules
-- | How to rename the base functor type constructors.
--
-- Default is to append F or $.
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 F or $.
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