cN\*|      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{ |}~|}~|~}}~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.  Annotations.  !The fixed-point type. "#$ The attribute of the root node. %AA function forgetting all the attributes from an annotated tree.  !"#$%$%!"#   !"#"#$%&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. &'()*+&'()*+&'()*+,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) .Generalization of scanr for trees. /01 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 2Generalization of scanl for trees 3KSynthetising attributes via an accumulating map in a left-to-right fashion  (the order is the same as in foldl). 4KSynthetising attributes via an accumulating map in a right-to-left fashion  (the order is the same as in foldr). 567We use 3 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. 894Merges two layers of annotations into a single one. :;6Merges three layers of annotations into a single one. <,-./0123456789:;<,-./0123456789:;<,-./0123456789:;< =>?JThe children together with functions replacing that particular child. @A0Apply the given function to each child in turn. B3Builds up a structure from a list of the children. CDEnumerates children from the left to the right, starting with zero. H Also returns the number of children. This is just a simple application  of  mapAccumL. DE  =>?@ABCDE =>?@ABCDE =>?@ABCDEF The list of direct descendants. GGThe 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 ] HBottom-up transformation. IJ>Top-down transformation. This provided only for completeness;  usually, it is H what you want use instead. KL'Non-recursive top-down transformation. MN9Bottom-up transformation until a normal form is reached. OPWe annotate9 the nodes of the tree with functions which replace that  particular subtree. QFlattened version of P. R(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. STFGHIJKLMNOPQRSTFGHIJKLMNOPQRSTFGHIJKLMNOPQRST$U?The zipper type itself, which encodes a locations in thre tree Mu f. VWXYQThe context or path type. The invariant we must respect is that there is exactly  one child with the  constructor. Z[\]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. aThe list of all locations. bThe zipper version of %. c*Extracts the subtree at focus. Synonym of W. d Replaces the subtree at focus. e Modifies the subtree at focus. f.Moves down to the child with the given index. ! The leftmost children has index 0. g"Moves down to the leftmost child. h#Moves down to the rightmost child. i Moves up. jkl)Checks whether we are at the top (root). m$Checks whether we cannot move down. nop+Moves to the top, by repeatedly moving up. qMoves left until it can. / It should be faster than repeated left steps. rMoves right until it can. 0 It should be faster than repeated right steps. stuvwx$UVWXYZ[\]^_`abcdefghijklmnopqrstuvwx$]Y\Z[UVWX^_`abcdefghijklmnopqrstuvwx$UVWXVWXY\Z[Z[\]^_`abcdefghijklmnopqrstuvwxy%The type of natural transformations. z"Changing the structure of a tree. {0Lifting natural transformations to annotations. yz{yz{yz{p  !"#$%&'()*+,-./0123456789:;<FGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{                   !"#$%&'()**+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`aabcddefghijklmnopqrstuvwxyz{|}~         fixplate-0.1.1Data.Generics.FixplateData.Generics.Fixplate.OpenData.Generics.Fixplate.Base Data.Generics.Fixplate.Morphisms!Data.Generics.Fixplate.Attributes!Data.Generics.Fixplate.TraversalsData.Generics.Fixplate.Zipper Data.Generics.Fixplate.StructureData.Generics.Fixplate.MiscbaseGHC.BasefmapFunctor Data.FoldableFoldableData.Traversable Traversable mapAccumR mapAccumLsequencemapM sequenceAtraversetoListfoldl1foldr1foldlfoldrfoldMapfoldAttribunAttribReadF readPrecFShowF showsPrecFOrdFcompareFEqFequalFAttrAnnattrunAnnMuFixunFix attributeforgetparapara'paraListcataanahyloannMap synthetise synthetise'synthetiseList synthetiseMinheritinherit' synthAccumL synthAccumR synthAccumL_ synthAccumR_enumerateNodesenumerateNodes_annZip annZipWithannZip3 annZipWith3 mapAccumL_ mapAccumR_holes holesListapplybuilder enumerate enumerateWithenumerateWith_childrenuniverse transform transformMtopDownTransformtopDownTransformMdescenddescendMrewriterewriteMcontext contextListfoldLeft foldLeftLazy foldRightLocfocuspathPathunPathTopNoderootdefocus locations locationsList locForgetextractreplacemodifymoveDown moveDownL moveDownRmoveUp moveRightmoveLeftisTopisBottom isLeftmost isRightmostmoveTopleftmost rightmostunsafeMoveDownunsafeMoveDownLunsafeMoveDownR unsafeMoveUpunsafeMoveLeftunsafeMoveRightNatTrafo restructureliftAnnBothFirstNoneTwoOneEmptyunsafeapp_prec<#> tillNothingchain chainJustiterateN Data.EitherRight