~       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~  Safe-Infered Safe-InferedA 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.  Annotations. !The fixed-point type. $ The attribute of the root node. %AA function forgetting all the attributes from an annotated tree. $ !"#$% !"#$%$%!"#  !"#$% Safe-Infered&A  paramorphism is a generalized (right) fold. )A  catamorphism( is a simpler version of a paramorphism *An  anamorphism is simply an unfold. +A  hylomorphism: is the composition of a catamorphism and an anamorphism. &'()*+&'()*+&'()*+&'()*+ 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. 10Apply the given function to each child in turn. 23Builds 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. 3Extracts the ith child. 52Number of children. This is the generalization of  to foldable functors:  sizeF x = length (toList x) 6DEnumerates children from the left to the right, starting with zero. H Also returns the number of children. This is just a simple application  of . 9Extracting the "shape" of the functor :,Zips two structures if they are compatible. <)Zipping two structures using a function. =Unsafe version of <7: 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. >Monadic version of <. TODO: better name? ,-./0123456789:;<=>? ,-./0123456789:;<=>? -./012345678,9:;<=>?,-./0123456789:;<=>? Safe-Infered @ The list of direct descendants. AGThe 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 ] BBottom-up transformation. D>Top-down transformation. This provided only for completeness;  usually, it is B what you want use instead. F'Non-recursive top-down transformation. H9Bottom-up transformation until a normal form is reached. JWe annotate9 the nodes of the tree with functions which replace that  particular subtree. KFlattened version of J. L(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. @ABCDEFGHIJKLMN@ABCDEFGHIJKLMN@ABCDEFGHIJKLMN@ABCDEFGHIJKLMN Safe-InferedOMap over annotations ' annMap f = unAttrib . fmap f . Attrib P 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) QGeneralization of scanr for trees. SMonadic version of P. T 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 UGeneralization of scanl for trees VMonadic version of T. XMonadic top-down "sweep" of a tree. It'0s kind of a more complicated folding version of V. [ This is unsafe in the sense that the user is responsible to retain the shape of the node.  TODO: better name? YAn attributed version of X. Probably more useful. ZKSynthetising attributes via an accumulating map in a left-to-right fashion  (the order is the same as in foldl). [KSynthetising attributes via an accumulating map in a right-to-left fashion  (the order is the same as in foldr). ^We use Z 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. aPBottom-up transformations to normal form (applying transformation exhaustively) A which automatically resynthetise attributes in case of changes. b4Merges two layers of annotations into a single one. d6Merges three layers of annotations into a single one. OPQRSTUVWXYZ[\]^_`abcdeOPQRSTUVWXYZ[\]^_`abcdeOPQRSTUVWXYZ[\]^_`abcdeOPQRSTUVWXYZ[\]^_`abcde Safe-Inferedf?The zipper type itself, which encodes a locations in thre tree Mu f. jQThe context or path type. The invariant we must respect is that there is exactly  one child with the  constructor. nA context node. o:Creates a zipper from a tree, with the focus at the root. pRestores a tree from a zipper. q?We attribute all nodes with a zipper focused at that location. rThe list of all locations. sThe zipper version of %. t*Extracts the subtree at focus. Synonym of h. u Replaces the subtree at focus. v Modifies the subtree at focus. w.Moves down to the child with the given index. ! The leftmost children has index 0. x"Moves down to the leftmost child. y#Moves down to the rightmost child. z 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. -fghijklmnopqrstuvwxyz{|}~'fghijklmnopqrstuvwxyz{|}~'njmklfghiopqrstuvwxyz{|}~'fghijmklnopqrstuvwxyz{|}~ Safe-Infered%The type of natural transformations. "Changing the structure of a tree. 0Lifting natural transformations to annotations.  Safe-InferedR  !"#$%&'()*+@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcde                   !"#$%&'()**+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrrstuuvwxyz{|}~             fixplate-0.1.2Data.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 attributeforgetparapara'paraListcataanahyloShape mapAccumL_ mapAccumR_holes holesListapplybuilderproject unsafeProjectsizeF enumerate enumerateWithenumerateWith_shapezipFunzipFzipWithFunsafeZipWithF zipWithFMunsafeZipWithFMchildrenuniverse transform transformMtopDownTransformtopDownTransformMdescenddescendMrewriterewriteMcontext contextListfoldLeft foldLeftLazy foldRightannMap synthetise synthetise'synthetiseList synthetiseMinheritinherit'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<#> tillNothingchain chainJustiterateNmapM_ mapAccumMstatesgetsputsmodify $fMonadStateT$fTraversableAttrib$fFoldableAttrib$fFunctorAttrib $fShowAttrib$fTraversableAnn $fFoldableAnn $fFunctorAnn $fReadFAnn $fShowFAnn $fOrdFAnn$fEqFAnn$fReadMu$fShowMu$fOrdMu$fEqMuGHC.Listlength $fShowShape $fOrdShape $fEqShape Data.EitherRight $fReadLoc $fReadPath $fShowLoc $fShowPath$fEqLoc$fEqPath