úά¥Äu      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTU V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t non-portable (rank-2 types) experimentaldan.doel@gmail.com$The catamorphism for the free monad Lifts a distributive law of h over f to a distributive  law of Free h over f The free monad of a functor f , formally,  Free F A = mu X. A + FX portable experimentaldan.doel@gmail.comOA type constructor which takes three arguments and an associated map function.  Informally,  Trifunctor f implies Bifunctor (f a) with bimap = trimap id. MA type constructor which takes two arguments and an associated map function.  Informally,  Bifunctor f implies  Functor (f a) with fmap = bimap id. +Constant functors. Essentially the same as  , except that they also carry a value. The unit functor. (Note: this is not the same as () . In fact,   is the  fixpoint of ().) Functor composition. )(Note: Some compilers will let you write f `O` g rather than O f g; we'&ll be doing so here for readability.) 'Functor composition is associative, so f `O` (g `O` h) and (f `O` g) `O` h are equivalent. The functions  and  convert between the two. '(Operationally, they are equivalent to id". Their only purpose is to affect the type system.)     ;non-portable (rank-2 polymorphism, infix type constructors) experimentaldan.doel@gmail.com portable experimentaldan.doel@gmail.comu  defined in terms of $ $% with the arguments swapped. Dual to v  for monads. "Injects a value into the comonad. 1Calls a comonadic function in a modified context >Converts a list of comonadic functions into a single function  returning a list of values !(There are two ways to define a comonad: I. Provide definitions for u , ", and # satisfying these laws:   extract . duplicate == id  fmap extract . duplicate == id 8 duplicate . duplicate == fmap duplicate . duplicate II. Provide definitions for " and $ satisfying these laws:   extend extract == id  extract . extend f == f . extend f . extend g == extend (f . extend g) (u 2 cannot be defaulted, but a comonad which defines $ may simply set u  equal to .) $A comonad providing definitions for $ and #, must also satisfy these laws:  ! extend f == fmap f . duplicate  duplicate == extend id % fmap f == extend (f . duplicate) $(The first two are the defaults for $ and #, #and the third is the definition of .)  !"#$!"#$ portable experimentaldan.doel@gmail.com%Returns the context &;Returns the result of the preceeding operations running in  a modified context '>Returns a list of results created by running prior operations @ in modified contexts created by the list of context-modifiers. (=Lifts an operation into the context comonad. Syntactic sugar for fmap# when chaining comonad operations.  & liftCtx == extract . fmap f  w =>> liftCtx f == fmap f w %&'()*)*%&'(portable experimentaldan.doel@gmail.com+6anamorphism for building a cofree comonad from a seed .IConverts a value of the cofree comonad over Maybe into a non-empty list. /Lifts a distributive law of f over h to a distributive law  of f over Cofree h. 0 The cofree comonad of a functor h( (also known as an H-branching stream). ?Various comonads are a special instance of the cofree comonad:  Cofree Identity is an infinite stream   Cofree Maybe is a non-empty stream  Cofree [] is a rose tree  formally:  Cofree H A = nu X. A * HX +,-./012012,-+./non-portable (fundeps) experimentaldan.doel@gmail.com3Minimal definitions: 1.  leftAdjunct and  rightAdjunct 2. unit and counit Given functors f and g, Adjunction f g implies  Monad (g `'O'` f) and ! (f `'O'` g). 3456734567+non-portable (rank-2 polymorphism, fundeps) experimentaldan.doel@gmail.com8Deconstructor for M 9A generalized map, known formally as a  hylomorphism and written [| f, g |].   refold f g == : f . ; g :A generalized foldr, known formally as a  catmorphism and written (| f |).   fold f == 9 f T  fold f == @ (wx . fmap y ) (f . fmap y) ;A generalized unfoldr, known formally as an  anamorphism and written [( f )].   unfold f == 9 S f  unfold f == C (fmap wx .  unIdentity) (fmap wx . f) < A variant of : where the function f! also receives the result of the +inner recursive calls. Formally known as a  paramorphism and written <| f |>. Dual to A.    para == > S  para f == 9 f (fmap (id &&& id) . T)  para f == f . fmap (id &&& para f) . T #Example: Computing the factorials.   fact :: Integer -> Integer  fact = para g  where  g Nothing = 1 " g (Just (n,f)) = f * (n + 1)  For the base case 0!, g is passed Nothing . (Note that S Nothing == 0.)  For subsequent cases (n+1)!, g is passed n and n!.  (Note that S (Just n) == n + 1.) Point-free version: 0fact = para $ maybe 1 (uncurry (*) . first (+1)).  Example:  dropWhile  ( dropWhile :: (a -> Bool) -> [a] -> [a]  dropWhile p = para f  where  f Nil = [] 8 f (Pair x xs) = if p x then snd xs else x : fst xs Point-free version: L dropWhile p = para $ cons [] (\x xs -> if p x then snd xs else x : fst xs) =AImplements course-of-value recursion. At each step, the function  receives an F-branching stream (01) containing the previous values. Formally known as a  histomorphism and written {| f |}.    histo == ? id &Example: Computing Fibonacci numbers.   fibo :: Integer -> Integer  fibo = histo next  where 5 next :: Maybe (Cofree Maybe Integer) -> Integer 2 next Nothing = 0 2 next (Just (Consf _ Nothing)) = 1 6 next (Just (Consf m (Just (Consf n _)))) = m + n  For the base case F(0), next is passed Nothing and returns 0.  (Note that S Nothing == 0)  For F(1), next0 is passed a one-element stream, and returns 1.  For subsequent cases F(n), next is passed a the stream [F(n-1), F(n-2), ..., F(0)] and returns F(n-1)+F(n-2). >A generalization of < implementing " semi-mutual" recursion. Known formally as a  zygomorphism and written <| f |> ^g, where g is an auxiliary function. Dual to B.   zygo g == @ (g . fmap fst &&& fmap snd) ? Generalizes =. to cases where the recursion functor and the (stream functor are distinct. Known as a g-histomorphism.   g_histo g == @ (+ (fmap , ) (g . fmap -)) @ Generalizes :, >, and ?. Formally known as a g-catamorphism !and written (| f |)^(w,k), where w is a ! and k is a distributive law between n and the functor f. The behavior of foldWith is determined by the comonad w.  wx recovers :  ((,) a) recovers > (and <)  01 recovers ? (and =) A apomorphisms , dual to <    apo == B T  apo f == S . fmap (id ||| apo f) . f *Example: Appending a list to another list  append :: [a] -> [a] -> [a]  append = curry (apo f)  where 9 f :: ([a],[a]) -> ConsPair a (Either [a] ([a],[a]))  f ([], []) = Nil % f ([], y:ys) = Pair y (Left ys) + f (x:xs, ys) = Pair x (Right (xs,ys)) B"Generalized apomorphisms, dual to >   g_apo g == C (fmap Left . g ||| fmap Right) C;Generalized anamorphisms parameterized by a monad, dual to @  Identity recovers ;   (Either a) recovers B (and A) DGGeneralized hylomorphisms parameterized by both a monad and a comonad. FThis one combinator subsumes most-if-not-all the other combinators in this library.   w = Identity yields C   m = Identity yields @  Free m and Cofree w yields H, and therefore ? and F e and g$ are additional functors related to f by natural transformations 1that have been fused into the distributive laws. z,The kernel of the generalized hylomorphism. E-Futumorphism: course of argument coiteration    futu == G (S . fmap ,)  futu == F id Example, translated from /,Primitive (Co)Recursion and Course-of-Value (Co)Iteration, Categorically/ ( 3http://citeseer.ist.psu.edu/uustalu99primitive.html):  5 phi (x:y:zs) = Pair y . inFree . Pair x $ return zs   exch = futu phi , l = exch [1..] -- [2,1,4,3,6,5,8,7,10,9..] FGeneralized futumorphism   g_futu m == H (const  ) m (S . fmap ,)  g_futu m == C ( m) G>a chronomorphism, coined by Edward Kmett, subsumes both histo  and futumorphisms. HDGeneralized chronomorphism. The recursion functor is separated from @the Free and Cofree functors, and related by distributive laws.   g_chrono w m == D (/ w) ( m) IDDynamorphisms: a hylomorphism like combinator that captures dynamic  programming.    dyna f g == J8 id (fmap Identity . runIdentity) f (fmap Identity . g)  dyna f g == G f (fmap return . g) Example, translated from )Recursion Schemes for Dynamic Programming ( 'http://citeseer.ist.psu.edu/748315.html) section 4.2:  , data Poly a = Term | Single a | Double a a   instance Functor Poly where  fmap _ Term = Term $ fmap f (Single a) = Single (f a) , fmap f (Double a b) = Double (f a) (f b)   psi 0 = Term  psi n  | odd n = Single (n-1) ' | even n = Double (n-1) (n `div` 2)   phi Term = 1  phi (Single n) = n  phi (Double m n) = m + n  2 bp1 = refold phi psi -- hylo version; ineffcient   zeta 0 = Nil  zeta n = Pair n (n-1)   epsilon = headCofree   theta = tailCofree  ' pie x = let (Pair m y) = theta x in y   pieN 0 x = x  pieN n x = pieN (n-1) (pie x)   sigma Nil = Term  sigma (Pair n x) ! | odd n = Single (epsilon x) B | even n = Double (epsilon x) (epsilon (pieN (n`div`2 - 1) x)) 9 bp2 = dyna (phi . sigma) zeta -- dynamically programmed {Kernel of the dynamorphism JGeneralized dynamorphism   g_dyna w == D (/ w) KThe dual of dynamorphisms. LGeneralized codynamorphisms. MFixpoint of lists P$Creates a fixpoint for any functor. S formally, in[f] : f -> mu f T formally, in^-1[f] : mu f -> f 89:;<=>?@ABCDEFGHIJKLMNOPQRST:<>=?@;ABCEF9DGHIJKLRSTPQMNO8 UVWXYZ[\]^ ^UVWXYZ[\] _`abcdefg fg_`abcde hijklmnopqrst thijklmnopqsr| !"#$%&'()*+,,-./01234566789:;<<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_ ` a b C c d e f g h a b C c i j e k l m n o p q r s t u v w x y z {||}~€category-extras-0.2Control.Monad.FreeControl.FunctorControl.Functor.TransformControl.ComonadControl.Comonad.ContextControl.Comonad.CofreeControl.Functor.AdjunctionControl.Recursion Data.StreamData.InfiniteSeqData.InfiniteTreebaseGHC.Base mtl-1.1.0.2Control.Monad.IdentitycataFreeinFree distribFreeFreelComprComp Trifunctortrimap BifunctorbimapConstunConstUnitOCompdeComp transFunc funcTrans.>:>liftW=>>.>>localmapW parallelWunfoldW sequenceW CoKleisli unCoKleisliComonadextract duplicateextendgetmodify experimentliftCtxContext anaCofree headCofree tailCofree cofreeToList distribCofreeCofreeunCofree Adjunction leftAdjunct rightAdjunctunitcounitconsrefoldfoldunfoldparahistozygog_histofoldWithapog_apo unfoldWith refoldWithfutug_futuchronog_chronodynag_dynacodynag_codynaConsPairPairNilFixInFixpointinFoutFmkStreamheadtailelemAttoSeqtoList mapStreamStfibsStreamdroptoStreamSeqNatmkTreerootleftrightbranchFsurrealsshowTree showTreeWide showTree'showWiderotateLrotateRTreefmap>>=Identity runIdentity refoldWith'dyna'