!      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Safe27 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" <gelisam@gmail.com>, "Oleg Grenrus" <oleg.grenrus@iki.fi>, "Ryan Scott" <ryan.gl.scott@gmail.com> experimental non-portableSafe&'1278=>?@AHSUVX|3*Frecursion-schemesJA 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-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]Jrecursion-schemesFokkinga's postpromorphismKrecursion-schemesA generalized postpromorphismLrecursion-schemesIA 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]. Ifthat 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-schemesA generalization of . The elements of the base functor, called the "recursive positions", give the result of folding the sub-tree at that position.:{let oursum = cata $ \caseNil -> 0Cons x acc -> x + acc:}oursum [1,2,3]6Orecursion-schemes A variant of Nv in which recursive positions also include the original sub-tree, in addition to the result of folding that sub-tree.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-schemesAn optimized version of cata f . ana 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 = hylo merge split wheresplit [] = Tip=split (x:xs) = let (l, r) = partition (<x) xs in Branch l x rmerge Tip = []$merge (Branch l x r) = l ++ [x] ++ r:}quicksort [1,5,2,8,4,9,8][1,2,4,5,8,8,9]Wrecursion-schemes An alias for N.Xrecursion-schemes An alias for H.Yrecursion-schemes An alias for V.Zrecursion-schemesA generalized catamorphism[recursion-schemesA generalized catamorphism]recursion-schemesA generalized anamorphism^recursion-schemesA generalized anamorphism`recursion-schemesA generalized hylomorphismarecursion-schemesA generalized hylomorphismfrecursion-schemes+Convert from one recursive type to another.PshowTree $ hoist (\(NonEmptyF h t) -> 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-schemesCourse-of-value iterationvrecursion-schemesMendler-style iterationwrecursion-schemes'Mendler-style course-of-value iterationxrecursion-schemesElgot algebrasyrecursion-schemesElgot coalgebras: 0http://comonad.com/reader/2008/elgot-coalgebras/zrecursion-schemes!Zygohistomorphic prepromorphisms:&A corrected and modernized version of Chttp://www.haskell.org/haskellwiki/Zygohistomorphic_prepromorphisms{recursion-schemes Effectful W.!This is a type specialisation of N./An example terminating a recursion immediately:NcataA (\alg -> case alg of { Nil -> pure (); Cons a _ -> Const [a] }) "hello" Const "h"|recursion-schemesAn effectful version of f. Properties: |  =   Examples:OThe weird type of first argument allows user to decide an order of sequencing:Btransverse (\x -> print (void x) *> sequence x) "foo" :: IO String Cons 'f' () Cons 'o' () Cons 'o' ()Nil"foo"Btransverse (\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-schemesLChurch 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 pointNrecursion-schemesa (Base t)-algebrarecursion-schemes fixed pointrecursion-schemesresultZrecursion-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 recursion; FHGIJKLNMOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|};S LNMOPQRlZhjpqbctu\TUikrsdeFHGIJK]_mnoV`fgW[X^Yavwxyz{|}SafeSX 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 Gdata ExprF a x = LitF a | AddF x x | x :*$ [x] deriving (, , ) 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:n works properly only with ADTs. Existentials and GADTs aren't supported, as we don't try to do better than  lhttps://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#deriving-functor-instancesGHC's DeriveFunctor. Allowing  to take both s and rs 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 N 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 Base/ (Rose f a) = RoseF f a instance Functor f =>  Recursive (Rose f a) where project1 (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 AddFAddF :: r -> r -> ExprF a r%data Rose f a = Rose a (f (Rose f a))C; makeBaseFunctor [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  Recursive or  Corecursive instances, e.g. BmakeBaseFunctor [d| instance Functor f => Recursive (Rose f a) |] VThis way we can provide a context for generated instances. Note that this instance's  still generates all of Base type instance,  Recursive and  Corecursive instances.recursion-schemes make instancerecursion-schemes make instanceSafec       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~,recursion-schemes-5.2-Ex0tGf8Lxlf3PzdGCbpfy4Data.Functor.BaseData.Functor.FoldableData.Functor.Foldable.TH Data.TreeTree Data.ListNonEmptyPaths_recursion_schemesForestFTreeFNodeF NonEmptyFheadtailListFNilCons$fBitraversableListF$fBifoldableListF$fBifunctorListF$fTraversableListF$fFoldableListF$fFunctorListF $fRead1ListF $fRead2ListF $fShow2ListF $fShow1ListF $fOrd1ListF $fOrd2ListF $fEq1ListF $fEq2ListF$fBitraversableNonEmptyF$fBifoldableNonEmptyF$fBifunctorNonEmptyF$fTraversableNonEmptyF$fFoldableNonEmptyF$fFunctorNonEmptyF$fRead1NonEmptyF$fRead2NonEmptyF$fShow2NonEmptyF$fShow1NonEmptyF$fOrd1NonEmptyF$fOrd2NonEmptyF$fEq1NonEmptyF$fEq2NonEmptyF$fBitraversableTreeF$fBifoldableTreeF$fBifunctorTreeF$fTraversableTreeF$fFoldableTreeF$fFunctorTreeF $fRead1TreeF $fRead2TreeF $fShow2TreeF $fShow1TreeF $fOrd1TreeF $fOrd2TreeF $fEq1TreeF $fEq2TreeF $fEqListF $fOrdListF $fShowListF $fReadListF$fGenericListF$fGeneric1ListF $fEqNonEmptyF$fOrdNonEmptyF$fShowNonEmptyF$fReadNonEmptyF$fGenericNonEmptyF$fGeneric1NonEmptyF $fEqTreeF $fOrdTreeF $fShowTreeF $fReadTreeF$fGenericTreeF$fGeneric1TreeF Corecursiveembedanaapopostprogpostpro RecursiveprojectcataparagparapreprogpreproBasedistPara distParaThylofoldunfoldrefoldgcatagfolddistCataganagunfolddistAnaghylogrefoldfutugfutudistFutu distGFutuhoistrefixzygodistZygogzygo distZygoTgapodistApodistGApo distGApoThistoghisto distHisto distGHistochronogchronomcatamhistoelgotcoelgotzygoHistoPreprocataA 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$fCorecursive[] $fRecursive[] BaseRulesMakeBaseFunctormakeBaseFunctormakeBaseFunctorWith baseRules baseRulesType baseRulesConbaseRulesField$fMakeBaseFunctorDec$fMakeBaseFunctorName$fMakeBaseFunctorQ$fMakeBaseFunctor[]base Data.FoldablefoldrlambekcolambekData.Traversable sequenceAGHC.BasepureData.Functor.Identity runIdentityGHC.ListzipWith D:R:BaseF%data-fix-0.3.0-FaaNgXifXnhHfaye3afnG4Data.FixMuD:R:BaseEither D:R:BaseMaybe D:R:BaseFreeT D:R:BaseFreeD:R:BaseCofreeTD:R:BaseCofree!free-5.1.3-5J5m6Whlv3F1SbmBznqUkcControl.Monad.Free.ChurchFFunctorFoldable Traversabletemplate-haskellLanguage.Haskell.TH.SyntaxNameDec mkMorphismtypeVarsconAppsT substType makePrimForDImakePrimForDI'version getBinDir getLibDir getDynLibDir getDataDir getLibexecDir getSysconfDirgetDataFileName