!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                    Safe-Infered !"#$%&'()*+,-./0123 !"#$%&'()*+,-./012 !"#$%&'()*+,-./0123 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 4 , 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. -We call a tree "atomic" if it has no subtrees. .0Lifting natural transformations to annotations. /0Lifting natural transformations to annotations. 0 The attribute of the root node. 1AA function forgetting all the attributes from an annotated tree. 5 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. 6 NOTE: The P instance for annotations compares both the annotations and the original part. = !"#$%&'()*+,-./0123789:;<=>?@ABCDEFGHIJ56KLMN# !"#$%&'()*+,-./0123#*+,-&'()%."$#!/01 23- !"$#%&'()*+,-./0123789:;<=>?@ABCDEFGHIJ56KLMN Safe-Infered 4A  catamorphism: is the generalization of right fold from lists to trees. 5A  paramorphism0 is a more general version of the catamorphism. 6Another version of 5% (a bit less natural in some sense). 7A list version of 5 (compare with Uniplate) 8An  anamorphism@ is simply an unfold. Probably not very useful in this context. 9An  apomorphism) is a generalization of the anamorphism. :A  hylomorphism: is the composition of a catamorphism and an anamorphism. ;A  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. AMonadic paramorphism. CAnother version of A. 456789:;<=>?@ABC456789:;<=>?@ABC456789:;<=>?@ABC456789:;<=>?@ABC Safe-Infered DA 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. EEquivalent to reverse . toList. HJThe children together with functions replacing that particular child. J0Apply the given function to each child in turn. K3Builds 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. LExtracts the ith child. N2Number of children. This is the generalization of O to foldable functors:  sizeF x = length (toList x) ODEnumerates children from the left to the right, starting with zero. H Also returns the number of children. This is just a simple application  of . RExtracting the "shape" of the functor S,Zips two structures if they are compatible. U)Zipping two structures using a function. VUnsafe version of U7: 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. WMonadic version of U. TODO: better name? DEFGHIJKLMNOPQRSTUVWXPQRS  DEFGHIJKLMNOPQRSTUVWX EFGHIJKLMNOPQ DRSTUVWXDEFGHIJKLMNOPQRSTUVWXPQRS Safe-Infered Y The list of direct descendants. ZGThe 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 ] [Bottom-up transformation. ]>Top-down transformation. This provided only for completeness;  usually, it is [ what you want use instead. _>Non-recursive top-down transformation. This is basically just . `"Similarly, this is basically just . a9Bottom-up transformation until a normal form is reached. c$Bottom-up transformation (typically "shallow"*, that is, restricted to a single level) 2 which can change the structure functor (actually [ is a special case of this). eWe annotate9 the nodes of the tree with functions which replace that  particular subtree. fFlattened version of e. g(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. YZ[\]^_`abcdefghiYZ[\]^_`abcdefghiYZ[\]^_`abcdefghiYZ[\]^_`abcdefghi Safe-InferedjMap over annotations ' annMap f = unAttrib . fmap f . Attrib k 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 o. lGeneralization of scanr for trees. See also p. mList version of k (compare with Uniplate) nMonadic version of k. o Synonym for k, motivated by the equation  $ attribute . synthCata f == cata f WThat is, it attributes all subtrees with the result of the corresponding catamorphism. p Synonym for l,. Note that this could be a special case of o:  I scanCata f == annZipWith (flip const) . synthCata (\(Ann a x) -> f a x)  Catamorphim (cata) is the generalization of foldr from lists to trees;  o is one generalization of scanr, and p is another generalization. qKAttributes all subtrees with the result of the corresponding paramorphism. $ attribute . synthPara f == para f rAnother version of q. & attribute . synthPara' f == para' f tSynthetising zygomorphism. ) attribute . synthZygo_ g h == zygo_ g h w.Accumulating catamorphisms. Generalization of  from lists to trees. xAccumulating paramorphisms. yCould be a special case of w: \ mapAccumCata f == second (annZipWith (flip const)) . synthAccumCata (\(Ann b t) -> f b t) # where second g (x,y) = (x, g y) z Synonym for n . If you don't need the result, use cataM_ instead. {Monadic version of q . If you don't need the result, use paraM_ instead. |Monadic version of r. } 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 ~Generalization of }. TODO: better name? Generalization of scanl from lists to trees. Monadic version of }. 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. (jklmnopqrstuvwxyz{|}~+jklmnopqrstuvwxyz{|}~+jklmnopqrstuvwxyz{|}~(jklmnopqrstuvwxyz{|}~ Safe-Infered'Prints a tree. It is defined simply as  drawTree = putStrLn . showTree :Creates a string representation which can be printed with T. Generate a graphviz .dot file UU 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 V 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 1. *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. -WXYZ[\'''WXYZ[\  Safe-Infered7 is an efficient(?) implementation of finite maps from (Mu f) to an arbitrary type v. .Creates a trie-multiset from a list of trees. This is equivalent to   universeBag == bag . universe %TODO: more efficient implementation? %TODO: more efficient implementation? Union is left-biased:  union == unionWith const ]^]^ Safe-Infered  !"#$%&'()*+,-./0123456789:;<=>?@ABCYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~    Safe-Infered &A concrete hash implementation. We don't use type classes since 4 a hash type class does not belong to this library;  we don't want to restrict the user's design space 1Thus we simulate type classes with record types. #the hash of an empty byte sequence digest a (unicode) character digest a hash value UA 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. _`abcde_`abcde  Safe-Infered 0Note that the returned list is ordered by hash, not by keys like ! 2Keys together with their associated unique values )Look up a unique index, in the form of a  (hash,Int) pair, for any key. " If the user-supplied function is  injective/, then the result is guaranteed to be uniquely R associated to the given key in the past and future history of this table (but of 6 course not unique among different future histories).  union == unionWith const )This is unsafe in the sense that the two getHash functions g (supplied when the hash tables were created) must agree. The same applies for all the set operations. bIt is also left-biased in the sense that the unique indices from the left hashtable are retained, 7 while the unique indices from the right hashtable are changed. oThis is unsafe both in the above sense and also that it does not accepts the empty list (for the same reason). : The result belongs to the world-line of the first table. KThis one accepts the empty list. The empty imput creates a new world-line. ( intersection == intersectionWith const !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  .      fghijklmnopqr               fghijklmnopqr  Safe-Inferedstst Safe-Infereduvuvw !"#$%&''())*+,-./0123345567889:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLHMNOPQRST U V H W X Y Z [ \ ] ^ _ ` a b c d e f g h i j klmnfixplate-0.1.5Data.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.ZipperData.Generics.Fixplate.TrieData.Generics.Fixplate.Hash&Data.Generics.Fixplate.Util.Hash.Table&Data.Generics.Fixplate.Util.Hash.Class*Data.Generics.Fixplate.Util.Hash.FNV.FNV32*Data.Generics.Fixplate.Util.Hash.FNV.FNV64Data.Generics.Fixplate.MiscDataMapbaseGHC.BasefmapFunctor Data.FoldableFoldableData.Traversable Traversable mapAccumR mapAccumLsequencemapM sequenceAtraversetoListfoldl1foldr1foldlfoldrfoldMapfoldCoAttrib unCoAttribAttribunAttribReadF readPrecFShowF showsPrecFOrdFcompareFEqFequalFHoleCoAttrCoAnnPureAttrAnnattrunAnnMuFixunFixisAtomliftAnn liftCoAnn attributeforgetshowFshowsFcataparapara'paraListanaapohylozygo_zygohistofutucataMcataM_paraMparaM_paraM'Shape toRevList mapAccumL_ mapAccumR_holes holesListapplybuilderproject unsafeProjectsizeF enumerate enumerateWithenumerateWith_shapezipFunzipFzipWithFunsafeZipWithF zipWithFMunsafeZipWithFMchildrenuniverse transform transformMtopDownTransformtopDownTransformMdescenddescendMrewriterewriteM restructure restructureMcontext 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_synthTransformsynthTransform' synthRewrite synthRewrite'annZip annZipWithannZip3 annZipWith3drawTree drawTreeWithshowTree showTreeWith graphvizTreegraphvizTreeWithLocfocuspathPathunPathTopNoderootdefocus locations locationsList locForgetextractreplacemodifymoveDown moveDownL moveDownRmoveUp moveRightmoveLeftisTopisBottom isLeftmost isRightmost horizontalPos fullPathDown fullPathUpmoveTopleftmost rightmostunsafeMoveDownunsafeMoveDownLunsafeMoveDownR unsafeMoveUpunsafeMoveLeftunsafeMoveRightTriebag universeBagempty singletonlookupinsert insertWithupdatedeletefromList intersectionintersectionWithunion unionWith differencedifferenceWith HashValue _emptyHash _hashChar _hashHashHashMuHashAnngetHash unHashAnntopHash forgetHashhashTree hashTreeWithhashNode hashNodeWith HashTable getHashValue unHashTableBucketLeafnullkeysWithgetUniqueIndexmember unionsWith unionsWith'intersectionsWithintersectionsWith'mapWithUniqueIndicesHashable hashDigest computeHash hashWord8 hashWord16 hashWord32 hashWord64 emptyHashhashHashshowHexhashInthashWordhashBoolhashCharFNV32unFNV32FNV64unFNV64StateT runStateTBothFirstNoneTwoOneEmptyequating groupSortOnmapGroupSortOnmapGroupSortOn'unsafeapp_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 $fOrdHoleF $fEqHoleF$fShowFHashAnn $fOrdFHashAnn $fEqFHashAnn$fTraversableHashAnn$fFoldableHashAnn$fFunctorHashAnn$fHashable(,,,,)$fHashable(,,,)$fHashable(,,) $fHashable(,) $fHashable[]$fHashableChar$fHashableBool$fHashableWord $fHashableInt$fHashableWord64$fHashableWord32$fHashableWord16$fHashableWord8$fHashValueFNV32$fHashableFNV32$fHashValueFNV64$fHashableFNV64