}      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~  Safe-Infered Safe-Infered A newtype wrapper around Attr f a so that we can make Attr f E an instance of Functor, Foldable and Traversable. This is necessary D since Haskell does not allow partial application of type synonyms. " Functorised"% versions of standard type classes. 3 If you have your a structure functor, for example   Expr e  = Kst Int  | Var String  | Add e e < deriving (Eq,Ord,Read,Show,Functor,Foldable,Traversable) 6you should make it an instance of these, so that the  fixed-point type Mu Expr can be an instance of  Eq, Ord and Show. Doing so is very easy:  - instance EqF Expr where equalF = (==) 0 instance OrdF Expr where compareF = compare 2 instance ShowF Expr where showsPrecF = showsPrec The Read6 instance depends on whether we are using GHC or not.  The Haskell98 version is  2 instance ReadF Expr where readsPrecF = readsPrec while the GHC version is 1 instance ReadF Expr where readPrecF = readPrec Annotated fixed-point type. Annotated functors. the annotation the original functor !The fixed-point type. $ The attribute of the root node. %AA function forgetting all the attributes from an annotated tree.  NOTE: The - instance for annotations first compares the  annotations , and then ; the functor part. If this is not the desired behaviour (it' s not clear to me at the moment X what is the good default here), you can use the standard newtype trick to define a new  behaviour.  NOTE: The P instance for annotations compares both the annotations and the original part. $ !"#$% !"#$%$%!"#  !"#$% Safe-Infered ,A  paramorphism is a generalized (right) fold. -Another version of ,+ (more natural in some sense; compare with 1). /A  catamorphism( is a simpler version of a paramorphism 0An  anamorphism@ is simply an unfold. Probably not very useful in this context. 1An  apomorphism) is a generalization of the anamorphism. 2A  hylomorphism: is the composition of a catamorphism and an anamorphism. 3A  zygomorphism< is a basically a catamorphism inside another catamorphism. P It could be implemented (somewhat wastefully) by first annotating each subtree : with the corresponding values of the inner catamorphism ( synthCata), then running ' a paramorphims on the annotated tree: % zygo_ g h == para' u . synthCata g  where , u = h . fmap (first attribute) . unAnn  first f (x,y) = (f x, y) 5 Futumorphism. Whatever it does. 6!Histomorphism. Whatever it does. 7Monadic paramorphism. 9Monadic catamorphism. &'()*+,-./0123456789:&'()*+,-./0123456789:,-./01234)*+&'(56789:&'()*+,-./0123456789: Safe-Infered ;A type encoding the "shape" of the functor data: < We ignore all the fields whose type is the parameter type,  but remember the rest:  - newtype Shape f = Shape { unShape :: f () } DThis can be used to decide whether two realizations are compatible. >JThe children together with functions replacing that particular child. @0Apply the given function to each child in turn. A3Builds up a structure from a list of the children. ; It is unsafe in the sense that it will throw an exception / if there are not enough elements in the list. BExtracts the ith child. D2Number of children. This is the generalization of  to foldable functors:  sizeF x = length (toList x) EDEnumerates children from the left to the right, starting with zero. H Also returns the number of children. This is just a simple application  of . HExtracting the "shape" of the functor I,Zips two structures if they are compatible. K)Zipping two structures using a function. LUnsafe version of K7: does not check if the two structures are compatible. W It is left-biased in the sense that the structure of the second argument is retained. MMonadic version of K. TODO: better name? ;<=>?@ABCDEFGHIJKLMN ;<=>?@ABCDEFGHIJKLMN <=>?@ABCDEFG;HIJKLMN;<=>?@ABCDEFGHIJKLMN Safe-Infered O The list of direct descendants. PGThe list of all substructures. Together with list-comprehension syntax I this is a powerful query tool. For example the following is how you get 2 the list of all variable names in an expression: 7 variables expr = [ s | Fix (Var s) <- universe expr ] QBottom-up transformation. S>Top-down transformation. This provided only for completeness;  usually, it is Q what you want use instead. U'Non-recursive top-down transformation. W9Bottom-up transformation until a normal form is reached. YWe annotate9 the nodes of the tree with functions which replace that  particular subtree. ZFlattened version of Y. [(Strict) left fold. Since Mu f3 is not a functor, but a data type, we cannot make  it an instance of the Foldable type class. OPQRSTUVWXYZ[\]OPQRSTUVWXYZ[\]OPQRSTUVWXYZ[\]OPQRSTUVWXYZ[\] Safe-Infered^Map over annotations ' annMap f = unAttrib . fmap f . Attrib _ Synthetised0 attributes are created in a bottom-up manner.  As an example, the sizes$ function computes the sizes of all  subtrees:  8 sizes :: (Functor f, Foldable f) => Mu f -> Attr f Int & sizes = synthetise (\t -> 1 + sum t)  (note that sum here is 7Data.Foldable.sum == Prelude.sum . Data.Foldable.toList)  See also c. `Generalization of scanr for trees. See also d. aList version of _ (compare with Uniplate) bMonadic version of _. c Synonym for _, motivated by the equation  $ attribute . synthCata f == cata f WThat is, it attributes all subtrees with the result of the corresponding catamorphism. d Synonym for `,. Note that this could be a special case of c:  I scanCata f == annZipWith (flip const) . synthCata (\(Ann a x) -> f a x)  Catamorphim (cata) is the generalization of foldr from lists to trees;  c is one generalization of scanr, and d is another generalization. eKAttributes all subtrees with the result of the corresponding paramorphism. $ attribute . synthPara f == para f fAnother version of e. This satisfies & attribute . synthPara' f == para' f hSynthetising zygomorphism. ) attribute . synthZygo_ g h == zygo_ g h k.Accumulating catamorphisms. Generalization of  from lists to trees. lAccumulating paramorphisms. mCould be a special case of k: \ mapAccumCata f == second (annZipWith (flip const)) . synthAccumCata (\(Ann b t) -> f b t) # where second g (x,y) = (x, g y) n Synonym for b . If you don't need the result, use cataM_ instead. oMonadic version of e . If you don't need the result, use paraM_ instead. pMonadic version of f. q Inherited/ attributes are created in a top-down manner.  As an example, the depths function computes the depth A (the distance from the root, incremented by 1) of all subtrees: + depths :: Functor f => Mu f -> Attr f Int " depths = inherit (\_ i -> i+1) 0 rGeneralization of scanl from lists to trees. sMonadic version of q. uMonadic top-down "sweep" of a tree. It'0s kind of a more complicated folding version of s. [ This is unsafe in the sense that the user is responsible to retain the shape of the node.  TODO: better name? vAn attributed version of u. Probably more useful. wKSynthetising attributes via an accumulating map in a left-to-right fashion  (the order is the same as in foldl). xKSynthetising attributes via an accumulating map in a right-to-left fashion  (the order is the same as in foldr). {We use w to number the nodes from 0 to (n-1) in * a left-to-right traversal fashion, where  n == length (universe tree)! is the number of substructures,  which is also returned. }GBottom-up transformations which automatically resynthetise attributes  in case of changes. ~PBottom-up transformations to normal form (applying transformation exhaustively) A which automatically resynthetise attributes in case of changes. 4Merges two layers of annotations into a single one. 6Merges three layers of annotations into a single one. %^_`abcdefghijklmnopqrstuvwxyz{|}~(^_`abcdefghijklmnopqrstuvwxyz{|}~(^_`abcdefghijklmnopqrstuvwxyz{|}~%^_`abcdefghijklmnopqrstuvwxyz{|}~ Safe-Infered?The zipper type itself, which encodes a locations in thre tree Mu f. QThe context or path type. The invariant we must respect is that there is exactly  one child with the  constructor. A context node. :Creates a zipper from a tree, with the focus at the root. Restores a tree from a zipper. ?We attribute all nodes with a zipper focused at that location. The list of all locations. The zipper version of %. *Extracts the subtree at focus. Synonym of .  Replaces the subtree at focus.  Modifies the subtree at focus. .Moves down to the child with the given index. ! The leftmost children has index 0. "Moves down to the leftmost child. #Moves down to the rightmost child.  Moves up. )Checks whether we are at the top (root). $Checks whether we cannot move down. MGives back the index of the given location among the children of its parent. S Indexing starts from zero. In case of root node (no parent), we also return zero. FWe return the full path from the root as a sequence of child indices.  This means that E loc == foldl (flip unsafeMoveDown) (moveTop loc) (fullPathDown loc) !The following equations hold for  and : & fullPathUp == reverse . fullPathDown < loc == foldr unsafeMoveDown (moveTop loc) (fullPathUp loc) +Moves to the top, by repeatedly moving up. Moves left until it can. / It should be faster than repeated left steps. Moves right until it can. 0 It should be faster than repeated right steps. -''' Safe-Infered%The type of natural transformations. "Changing the structure of a tree. 0Lifting natural transformations to annotations.  Safe-Inferedo  !"#$%&'()*+,-./0123456789:OPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                   !"#$%&'()**+,-./012234456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~             fixplate-0.1.3Data.Generics.FixplateData.Generics.Fixplate.OpenData.Generics.Fixplate.Base Data.Generics.Fixplate.Morphisms!Data.Generics.Fixplate.Traversals!Data.Generics.Fixplate.AttributesData.Generics.Fixplate.Zipper Data.Generics.Fixplate.StructureData.Generics.Fixplate.MiscbaseGHC.BasefmapFunctor Data.FoldableFoldableData.Traversable Traversable mapAccumR mapAccumLsequencemapM sequenceAtraversetoListfoldl1foldr1foldlfoldrfoldMapfoldAttribunAttribReadF readPrecFShowF showsPrecFOrdFcompareFEqFequalFAttrAnnattrunAnnMuFixunFix attributeforgetCoFreeunCoFreeFreeunFreeparapara'paraListcataanaapohylozygo_zygofutuhistoparaMparaM_cataMcataM_Shape mapAccumL_ mapAccumR_holes holesListapplybuilderproject unsafeProjectsizeF enumerate enumerateWithenumerateWith_shapezipFunzipFzipWithFunsafeZipWithF zipWithFMunsafeZipWithFMchildrenuniverse transform transformMtopDownTransformtopDownTransformMdescenddescendMrewriterewriteMcontext contextListfoldLeft foldLeftLazy foldRightannMap synthetise synthetise'synthetiseList synthetiseM synthCatascanCata synthPara synthPara'scanPara synthZygo_ synthZygo synthZygoWithsynthAccumCatasynthAccumPara mapAccumCata synthCataM synthParaM synthParaM'inheritinherit'inheritM inheritM_ topDownSweepMtopDownSweepM' synthAccumL synthAccumR synthAccumL_ synthAccumR_enumerateNodesenumerateNodes_synthTransform synthRewriteannZip annZipWithannZip3 annZipWith3LocfocuspathPathunPathTopNoderootdefocus locations locationsList locForgetextractreplacemodifymoveDown moveDownL moveDownRmoveUp moveRightmoveLeftisTopisBottom isLeftmost isRightmost horizontalPos fullPathDown fullPathUpmoveTopleftmost rightmostunsafeMoveDownunsafeMoveDownLunsafeMoveDownR unsafeMoveUpunsafeMoveLeftunsafeMoveRightNatTrafo restructureliftAnnStateT runStateTBothFirstNoneTwoOneEmptyunsafeapp_prec<#>firstsecond tillNothingchain chainJustiterateNmapM_ mapAccumMstatesgetsputsmodify $fMonadStateT $fOrdFAnn$fEqFAnn$fTraversableAttrib$fFoldableAttrib$fFunctorAttrib $fShowAttrib$fTraversableAnn $fFoldableAnn $fFunctorAnn $fReadFAnn $fShowFAnn$fReadMu$fShowMu$fOrdMu$fEqMuGHC.Listlength $fShowShape $fOrdShape $fEqShape Data.EitherRight $fReadLoc $fReadPath $fShowLoc $fShowPath$fEqLoc$fEqPath