h*[=V      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~5.2.3 Safe-Inferred9:;<recursion-schemesBase functor for .recursion-schemesBase Functor for recursion-schemesBase functor of [].    (C) 2008-2015 Edward Kmett BSD-style (see the file LICENSE)"Samuel Glineau" , "Luc Tielen" , "Ryan Scott"  experimental non-portable Safe-Inferred)*67<=Ht/Frecursion-schemesA recursive datatype which can be rolled up one recursion layer at a time.For example, a value of type  a [a] can be rolled up into a [a]. This [a] can then be used in a   to construct another  a [a]-, which can be rolled up as well, and so on. Typically, F types also have a L instance, in which case G and M are inverses.Grecursion-schemes!Roll up a single recursion layer.embed (Cons 1 [2,3])[1,2,3]Hrecursion-schemes An alias for X.Jrecursion-schemesFokkinga's postpromorphismKrecursion-schemesA generalized postpromorphismLrecursion-schemesA recursive datatype which can be unrolled one recursion layer at a time.For example, a value of type [a] can be unrolled into a  a [a]. If that unrolled value is a  , it contains another [a]+ which can be unrolled as well, and so on. Typically, L types also have a F instance, in which case M and G are inverses.Mrecursion-schemes Unroll a single recursion layer.project [1,2,3] Cons 1 [2,3]Nrecursion-schemes An alias for W.W 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 W' is "catamorphism". They also give its  Base t a -> a argument a special name, "(Base t3)-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.Orecursion-schemes A variant of N 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 where5 go :: TreeF Int (Tree Int, Reader Int String) -> Reader Int String go (NodeF i trss) = do4 -- 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 O 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.:{ 1let 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)Qrecursion-schemesFokkinga's prepromorphismSrecursion-schemes1Obtain 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  a: data  a b =  |   a b type instance S [a] =  a ?The relationship between those two types is that if we replace b with  a*, we obtain a type which is isomorphic to [a].Vrecursion-schemes An alias for Y.Wrecursion-schemes Int mySum = fold $ \case Nil -> 0 Cons x sumXs -> x + sumXs:}mySum [10,11,12]331In our running example, one layer consists of an ' and a list of recursive positions. In Tree Int6, those recursive positions contain sub-trees of type Tree Int0. 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 String0. That is, each recursive position contains the ? 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.Xrecursion-schemesA 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]Yrecursion-schemesAn 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.9data BinTreeF a b = Tip | Branch b a b deriving (Functor) :{$let quicksort :: Ord a => [a] -> [a]$quicksort = refold merge split wheresplit [] = Tip=split (x:xs) = let (l, r) = partition ( NodeF [h] (maybeToList t)) ( 'a' :| "bcd") (a (b (c d)))grecursion-schemes5Convert from one recursive representation to another.*refix ["foo", "bar"] :: Fix (ListF String)-Fix (Cons "foo" (Fix (Cons "bar" (Fix Nil))))recursion-schemes1Lambek's lemma provides a default definition for M in terms of N and Grecursion-schemes>The dual of Lambek's lemma, provides a default definition for G in terms of H and Mprecursion-schemes A variant of N which includes the results of all the descendents, not just the direct children.Like O, a sub-tree is provided for each recursive position. Each node in that sub-tree is annotated with the result for that descendent. The ' type is used to add those annotations.For our running example, let's recreate GitHub's directory compression algorithm. Notice that in  6https://github.com/recursion-schemes/recursion-schemes the repository for this package, GitHub displays src/Data/Functor, not src: docs/github-compression.pngGitHub's code pageGitHub 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 p&, 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):}6let 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 p8 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 * 3112One common use for p is to cache the value computed for smaller sub-trees. In the Fibonacci example below, the recursive type is , 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 where5 go :: Maybe (Cofree Maybe Integer) -> Integer go Nothing = 1$ go (Just (_ :< Nothing)) = 18 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.vrecursion-schemesMendler-style iterationwrecursion-schemesMendler-style recursionxrecursion-schemes#Mendler-style semi-mutual recursionyrecursion-schemes'Mendler-style course-of-value iterationzrecursion-schemesMendler-style coiteration{recursion-schemesMendler-style corecursion|recursion-schemes*Mendler-style course-of-values coiteration}recursion-schemesElgot algebras~recursion-schemesElgot coalgebras: 0http://comonad.com/reader/2008/elgot-coalgebras/recursion-schemes!Zygohistomorphic prepromorphisms:&A corrected and modernized version of http://www.haskell.org/haskellwiki/Zygohistomorphic_prepromorphismsrecursion-schemesA specialization of N for effectful folds. is the same as N, 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 Int4 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 <- ask8 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 s 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 N 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 * 3112recursion-schemesAn effectful version of f. Properties:   =   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 StringNil Cons 'o' () Cons 'o' () Cons 'f' ()"foo"recursion-schemesA coeffectful version of f. Properties:  _ =   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 'data Pair a = Pair a a deriving Functor:{>let zipWith' :: forall a b. (a -> a -> b) -> [a] -> [a] -> [b]8 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]recursion-schemesChurch encoded free monads are Recursive/Corecursive, in the same way that  is.recursion-schemes0Example boring stub for non-recursive data typesrecursion-schemes0Example boring stub for non-recursive data typesrecursion-schemes8Free transformations of monads are Recursive/Corecursiverecursion-schemes%Free monads are Recursive/Corecursiverecursion-schemes:Cofree tranformations of comonads are Recursive/Corecusiverecursion-schemes)Cofree comonads are Recursive/Corecursiverecursion-schemes/It may be better to work with the instance for  directly.Hrecursion-schemesa (Base t)-coalgebrarecursion-schemesseedrecursion-schemesresulting fixed pointZrecursion-schemesa distributive lawrecursion-schemesa (Base t)-w-algebrarecursion-schemes fixed point[recursion-schemesa distributive lawrecursion-schemesa (Base t)-w-algebrarecursion-schemes fixed point]recursion-schemesa distributive lawrecursion-schemesa (Base t)-m-coalgebrarecursion-schemesseed^recursion-schemesa distributive lawrecursion-schemesa (Base t)-m-coalgebrarecursion-schemesseedirecursion-schemes(A distributive for semi-mutual recursionS LMNOQPRFGHIJKWphXbYVtgfvwyxz{|}~[Zqj^]lca`u\TUrsik_mnodeS LMFGWNOphXHIbYVtgfvwyxz{|QJ}~[ZPqj^]lca`uRK\TUrsik_mnode Safe-InferredV. recursion-schemesRules of renaming data namesrecursion-schemes9Build 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)  ''Expr  will create data ExprF a x = LitF a | AddF x x | x :*$ [x] deriving (, , ) type instance S (Expr a) = ExprF a instance L (Expr a) where M (Lit x) = LitF x M (Add x y) = AddF x y M (x :* y) = x :*$ y instance F (Expr a) where G (LitF x) = Lit x G (AddF x y) = Add x y G (x :*$ y) = x :* y Notes: works properly only with ADTs. Existentials and GADTs aren't supported, as we don't try to do better than  https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#deriving-functor-instancesGHC's DeriveFunctor. Allowing  to take both s and s 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  with an instance declaration to provide needed context for instances. (c.f. StandaloneDeriving) 3 [d| instance Functor f => Recursive (Rose f a) |]  will create .data RoseF f a r = RoseF a (f fr) deriving (, , ) type instance S/ (Rose f a) = RoseF f a instance Functor f => L (Rose f a) where M1 (Rose x xs) = RoseF x xs instance Functor f => F (Rose f a) where G (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 AddFAddF :: r -> r -> ExprF a rdata 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 r9let rose = Rose 1 (Just (Rose 2 (Just (Rose 3 Nothing)))),cata (\(RoseF x f) -> x + maybe 0 id f) rose6recursion-schemes  =   recursion-schemes/Build base functor with a custom configuration.recursion-schemesDefault  : append F or $, to data type, constructors and field names.recursion-schemes"How to name the base functor type.Default is to append F or $.recursion-schemes1How to rename the base functor type constructors.Default is to append F or $.recursion-schemes=How to rename the base functor type field names (in records).Default is to append F or $.recursion-schemes$makes clauses to rename constructorsrecursion-schemesExtract type variablesrecursion-schemes&Apply arguments to a type constructor.recursion-schemesProvides substitution for typesrecursion-schemesExpects declarations of L or F instances, e.g. makeBaseFunctor [d| instance Functor f => Recursive (Rose f a) |] This way we can provide a context for generated instances. Note that this instance's  still generates all of S type instance, L and F instances.recursion-schemes make instancerecursion-schemes make instance  Safe-InferredVu      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~        -recursion-schemes-5.2.3-7LiMGXjXoZvMaeUW0LkwMData.Functor.BaseData.Functor.FoldableData.Functor.Foldable.THrecursion-schemes Data.TreeTree Data.ListNonEmptyPaths_recursion_schemesForestFTreeFNodeF NonEmptyFheadtailListFNilCons$fBitraversableListF$fBifoldableListF$fBifunctorListF $fRead1ListF $fRead2ListF $fShow2ListF $fShow1ListF $fOrd1ListF $fOrd2ListF $fEq1ListF $fEq2ListF$fBitraversableNonEmptyF$fBifoldableNonEmptyF$fBifunctorNonEmptyF$fRead1NonEmptyF$fRead2NonEmptyF$fShow2NonEmptyF$fShow1NonEmptyF$fOrd1NonEmptyF$fOrd2NonEmptyF$fEq1NonEmptyF$fEq2NonEmptyF$fBitraversableTreeF$fBifoldableTreeF$fBifunctorTreeF $fRead1TreeF $fRead2TreeF $fShow2TreeF $fShow1TreeF $fOrd1TreeF $fOrd2TreeF $fEq1TreeF $fEq2TreeF $fEqTreeF $fOrdTreeF $fShowTreeF $fReadTreeF$fGenericTreeF$fGeneric1TYPETreeF$fFunctorTreeF$fFoldableTreeF$fTraversableTreeF $fEqNonEmptyF$fOrdNonEmptyF$fShowNonEmptyF$fReadNonEmptyF$fGenericNonEmptyF$fGeneric1TYPENonEmptyF$fFunctorNonEmptyF$fFoldableNonEmptyF$fTraversableNonEmptyF $fEqListF $fOrdListF $fShowListF $fReadListF$fGenericListF$fGeneric1TYPEListF$fFunctorListF$fFoldableListF$fTraversableListF Corecursiveembedanaapopostprogpostpro RecursiveprojectcataparagparapreprogpreproBasedistPara distParaThylofoldunfoldrefoldgcatagfolddistCataganagunfolddistAnaghylogrefoldfutugfutudistFutu distGFutuhoistrefixzygodistZygogzygo distZygoTgapodistApodistGApo distGApoThistoghisto distHisto distGHistochronogchronomcatamparamzygomhistomanamapomfutuelgotcoelgotzygoHistoPreprocataA transverse cotransverse$fGCoerce:+::+:$fGCoerce:*::*: $fGCoerceV1V1 $fGCoerceU1U1 $fGCoerceK1K1 $fGCoerceM1M1$fCorecursiveF $fRecursiveF $fRecursiveNu$fCorecursiveNu$fCorecursiveMu $fRecursiveMu$fCorecursiveFix$fRecursiveFix$fCorecursiveEither$fRecursiveEither$fCorecursiveMaybe$fRecursiveMaybe$fCorecursiveFreeT$fRecursiveFreeT$fCorecursiveFree$fRecursiveFree$fCorecursiveCofreeT$fRecursiveCofreeT$fCorecursiveCofree$fRecursiveCofree$fCorecursiveNatural$fRecursiveNatural$fCorecursiveTree$fRecursiveTree$fCorecursiveNonEmpty$fRecursiveNonEmpty$fCorecursiveList$fRecursiveList BaseRulesMakeBaseFunctormakeBaseFunctormakeBaseFunctorWith baseRules baseRulesType baseRulesConbaseRulesField$fMakeBaseFunctorDec$fMakeBaseFunctorName$fMakeBaseFunctorQ$fMakeBaseFunctorListghc-prim GHC.TypesIntbaseGHC.BaseStringlambekcolambekfree-5.2-HmzeSrLAi4cETfZjCGuvh5Control.Comonad.CofreeCofree ghc-bignumGHC.Num.NaturalNaturalData.Traversable sequenceApureData.Functor.Identity runIdentityGHC.ListzipWith D:R:BaseF%data-fix-0.3.3-H1wJiX9O4we5WdBFC8lIXMData.FixMuD:R:BaseEither D:R:BaseMaybe D:R:BaseFreeT D:R:BaseFreeD:R:BaseCofreeTD:R:BaseCofreeControl.Monad.Free.ChurchFFunctor Data.FoldableFoldable Traversabletemplate-haskellLanguage.Haskell.TH.SyntaxNameDec mkMorphismtypeVarsconAppsT substType makePrimForDImakePrimForDI'version getBinDir getLibDir getDynLibDir getDataDir getLibexecDirgetDataFileName getSysconfDir