f      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~  Safe-Infered Safe-InferedCategorial dual of  . Equivalent to the free monad. A newtype wrapper around Attr f a so that we can make Attr f S an instance of Functor, Foldable and Traversable (and Comonad). This is necessary D since Haskell does not allow partial application of type synonyms. #Equivalent to the co-free comonad. " 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 :This a data type defined to be a place-holder for childs. * It is used in tree drawing, hashing, and Shape. +It is deliberately not made an instance of  , so that K you can choose your preferred style. For example, an acceptable choice is ' instance Show Hole where show _ = "_" !Categorical dual of %. Equivalent to Free f a "Categorical dual of &. %*Annotated fixed-point type. Equivalent to  CoFree f a &Type of annotations (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. : !"#$%&'()*+,-./0       !"#$%&'()*+,-./0 *+,-.&'()%"$#! /0* !"$#%&'()*+,-./0      Safe-Infered 1A  catamorphism: is the generalization of right fold from lists to trees. 2A  paramorphism0 is a more general version of the catamorphism. 3Another version of 2% (a bit less natural in some sense). 4A list version of 2 (compare with Uniplate) 5An  anamorphism@ is simply an unfold. Probably not very useful in this context. 6An  apomorphism) is a generalization of the anamorphism. 7A  hylomorphism: is the composition of a catamorphism and an anamorphism. 8A  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) :/Histomorphism. This is a kind of glorified cata/paramorphism, after all: & cata f == histo (f . fmap attribute) < para f == histo (f . fmap (\t -> (forget t, attribute t))) ;1Futumorphism. This is a more interesting unfold. <Monadic catamorphism. >Monadic paramorphism. @Another version of >. 123456789:;<=>?@123456789:;<=>?@123456789:;<=>?@123456789:;<=>?@ Safe-Infered AA 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 Hole } DThis can be used to decide whether two realizations are compatible. BEquivalent to reverse . toList. EJThe children together with functions replacing that particular child. G0Apply the given function to each child in turn. H3Builds 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. IExtracts the ith child. K2Number of children. This is the generalization of  to foldable functors:  sizeF x = length (toList x) LDEnumerates children from the left to the right, starting with zero. H Also returns the number of children. This is just a simple application  of . OExtracting the "shape" of the functor P,Zips two structures if they are compatible. R)Zipping two structures using a function. SUnsafe version of R7: 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. TMonadic version of R. TODO: better name? ABCDEFGHIJKLMNOPQRSTU !  ABCDEFGHIJKLMNOPQRSTU BCDEFGHIJKLMN AOPQRSTUABCDEFGHIJKLMNOPQRSTU ! Safe-Infered V The list of direct descendants. WGThe 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 ] XBottom-up transformation. Z>Top-down transformation. This provided only for completeness;  usually, it is X what you want use instead. \'Non-recursive top-down transformation. ^9Bottom-up transformation until a normal form is reached. `We annotate9 the nodes of the tree with functions which replace that  particular subtree. aFlattened version of `. b(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. VWXYZ[\]^_`abcdVWXYZ[\]^_`abcdVWXYZ[\]^_`abcdVWXYZ[\]^_`abcd Safe-InferedeMap over annotations ' annMap f = unAttrib . fmap f . Attrib f 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 j. gGeneralization of scanr for trees. See also k. hList version of f (compare with Uniplate) iMonadic version of f. j Synonym for f, motivated by the equation  $ attribute . synthCata f == cata f WThat is, it attributes all subtrees with the result of the corresponding catamorphism. k Synonym for g,. Note that this could be a special case of j:  I scanCata f == annZipWith (flip const) . synthCata (\(Ann a x) -> f a x)  Catamorphim (cata) is the generalization of foldr from lists to trees;  j is one generalization of scanr, and k is another generalization. lKAttributes all subtrees with the result of the corresponding paramorphism. $ attribute . synthPara f == para f mAnother version of l. & attribute . synthPara' f == para' f oSynthetising zygomorphism. ) attribute . synthZygo_ g h == zygo_ g h r.Accumulating catamorphisms. Generalization of  from lists to trees. sAccumulating paramorphisms. tCould be a special case of r: \ mapAccumCata f == second (annZipWith (flip const)) . synthAccumCata (\(Ann b t) -> f b t) # where second g (x,y) = (x, g y) u Synonym for i . If you don't need the result, use cataM_ instead. vMonadic version of l . If you don't need the result, use paraM_ instead. wMonadic version of m. x 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 yGeneralization of x. TODO: better name? zGeneralization of scanl from lists to trees. {Monadic version of x. }Monadic top-down "sweep" of a tree. It'0s kind of a more complicated folding version of {. [ This is unsafe in the sense that the user is responsible to retain the shape of the node.  TODO: better name? ~An attributed version of }. Probably more useful. KSynthetising 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  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. &efghijklmnopqrstuvwxyz{|}~)efghijklmnopqrstuvwxyz{|}~)efghijklmnopqrstuvwxzy{|}~&efghijklmnopqrstuvwxyz{|}~ Safe-Infered'Prints a tree. It is defined simply as  drawTree = putStrLn . showTree :Creates a string representation which can be printed with ". Generate a graphviz .dot file ## 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-Infered!Creates a multi-set from a list.    Safe-InferedJA type class of hashable objects. An instance has to compute the hash for  any hash function, using the "base" types (eg. Word32). Minimal complete definition: . The default for  is ( computeHash x = hashDigest x emptyHash A type class for hashes.  Minimal complete definition: , ,  and . +,-./01234567+,-./01234567  Safe-Infered8989  Safe-Infered:;:; Safe-Infered|  !"#$%&'()*+,-./0123456789:;<=>?@VWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~   Safe-InferedUA tree annotated with hashes of all subtrees. This gives us fast inequality testing, * and fast (but meaningless!) ordering for Map-s. gHash annotation (question: should the Hash field be strict? everything else in the library is lazy...) +This is custom datatype instead of reusing & because of the different Eq/Ord instances we need. The hash of the complete tree. This function uses the  instance to compute 8 the hash of a node; this way you always have a working . version without writing any additional code. ;However, you can also supply your own hash implementation 8 (which can be more efficient, for example), if you use  instead. 'Build a hashed node from the children. <=>?@AB <=>?@ABC !"#$%%&''()*+,-./0112334566789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                !"#$%&'()*+',-./0123 4 5 6 7 8 9 : ; < = > ? @ A B C D'EFGHIJKfixplate-0.1.4Data.Generics.FixplateData.Generics.Fixplate.OpenData.Generics.Fixplate.Base Data.Generics.Fixplate.Morphisms!Data.Generics.Fixplate.Traversals!Data.Generics.Fixplate.AttributesData.Generics.Fixplate.DrawData.Generics.Fixplate.Zipper Data.Generics.Fixplate.Structure!Data.Generics.Fixplate.Hash.Table!Data.Generics.Fixplate.Hash.Class%Data.Generics.Fixplate.Hash.FNV.FNV32%Data.Generics.Fixplate.Hash.FNV.FNV64Data.Generics.Fixplate.HashData.Generics.Fixplate.MiscbaseGHC.BasefmapFunctor Data.FoldableFoldableData.Traversable Traversable mapAccumR mapAccumLsequencemapM sequenceAtraversetoListfoldl1foldr1foldlfoldrfoldMapfoldCoAttrib unCoAttribAttribunAttribReadF readPrecFShowF showsPrecFOrdFcompareFEqFequalFHoleCoAttrCoAnnPureAttrAnnattrunAnnMuFixunFix attributeforgetshowFshowsFcataparapara'paraListanaapohylozygo_zygohistofutucataMcataM_paraMparaM_paraM'Shape toRevList 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'inheritinherit2inherit'inheritM inheritM_ topDownSweepMtopDownSweepM' synthAccumL synthAccumR synthAccumL_ synthAccumR_enumerateNodesenumerateNodes_synthTransform synthRewriteannZip annZipWithannZip3 annZipWith3drawTree drawTreeWithshowTree showTreeWith graphvizTreegraphvizTreeWithLocfocuspathPathunPathTopNoderootdefocus locations locationsList locForgetextractreplacemodifymoveDown moveDownL moveDownRmoveUp moveRightmoveLeftisTopisBottom isLeftmost isRightmost horizontalPos fullPathDown fullPathUpmoveTopleftmost rightmostunsafeMoveDownunsafeMoveDownLunsafeMoveDownR unsafeMoveUpunsafeMoveLeftunsafeMoveRightNatTrafo restructureliftAnn HashTable getHashValue unHashTableempty singletonfromListlookupmemberinsert insertWithbagHashable hashDigest computeHash HashValue hashWord8 hashWord16 hashWord32 hashWord64 emptyHashhashHashshowHexhashInthashWordhashBoolhashCharFNV32unFNV32FNV64unFNV64HashMuHashAnngetHash unHashAnntopHash forgetHashhashTree hashTreeWithhashNode hashNodeWithStateT runStateTBothFirstNoneTwoOneEmptyunsafeapp_prec<#>firstsecond tillNothingchain chainJustiterateNmapM_ mapAccumMstatesgetsputsmodify $fMonadStateTGHC.ShowShow $fOrdFAnn$fEqFAnn$fMonadCoAttrib$fTraversableCoAttrib$fFoldableCoAttrib$fFunctorCoAttrib$fShowCoAttrib$fTraversableAttrib$fFoldableAttrib$fFunctorAttrib $fShowAttrib$fTraversableCoAnn$fFoldableCoAnn$fFunctorCoAnn$fTraversableAnn $fFoldableAnn $fFunctorAnn $fShowFCoAnn $fOrdFCoAnn $fEqFCoAnn $fReadFAnn $fShowFAnn$fReadMu$fShowMu$fOrdMu$fEqMuGHC.Listlength $fShowShape $fShowVoid $fOrdShape $fEqShape System.IOputStrLn Data.EitherRight $fReadLoc $fReadPath $fShowLoc $fShowPath$fEqLoc$fEqPath$fHashable(,,,,)$fHashable(,,,)$fHashable(,,) $fHashable(,) $fHashable[]$fHashableChar$fHashableBool$fHashableWord $fHashableInt$fHashableWord64$fHashableWord32$fHashableWord16$fHashableWord8$fHashValueFNV32$fHashableFNV32$fHashValueFNV64$fHashableFNV64$fShowFHashAnn $fOrdFHashAnn $fEqFHashAnn$fTraversableHashAnn$fFoldableHashAnn$fFunctorHashAnn