:      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcde f g h i j k l m n o p q r s t u v w x y z { | } ~  Difference list  Empty list Singleton list  Given a list is9 of unique natural numbers, returns a function that maps  each number in is! to a unique number in the range [0 .. length is-1]. The  complexity is O( maximum is). KCount the number of occurrences of each element in the list. The result is = an array mapping each element to its number of occurrences. 4Upper and lower bound on the elements to be counted Elements to be counted KPartitions the list such that two elements are in the same sub-list if and G only if they satisfy the equivalence check. The complexity is O(n^2). A9Representation of a fully polymorphic constraint -- i.e. (   a)  is satisfied by all types a. 3Symbols that act as witnesses of their result type  Witness of a (  ctx a)$ constraint. This is different from  ( ctx a)', which witnesses the class encoded by ctx.   2 has a single constructor for all contexts, while  has different & constructors for different contexts. .An abstract representation of a constraint on a. An instance might look  as follows:  ' instance MyClass a => Sat MyContext a  where 7 data Witness MyContext a = MyClass a => MyWitness  witness = MyWitness This allows us to use (  MyContext a) instead of  (MyClass a). The  point with this is that  MyContext) can be provided as a parameter, so this K effectively allows us to parameterize on class constraints. Note that the K existential context in the data definition is important. This means that,  given a constraint (  MyContext a)&, we can always construct the context   (MyClass a) by calling the ! method (the class instance only % declares the reverse relationship). =This way of parameterizing over type classes was inspired by   Restricted Data Types in Haskell (John Hughes, Haskell Workshop , 1999). N-ary syntactic functions  has any type of the form:   desugarN ::  ( Syntactic a dom  , Syntactic b dom  , ...  , Syntactic x dom  ) => (a -> b -> ... -> x) ) -> ( AST dom (Full (Internal a)) ) -> AST dom (Full (Internal b))  -> ... ) -> AST dom (Full (Internal x))  ) ...and vice versa for . !It is assumed that for all types A fulfilling ( A dom):  5 eval a == eval (desugar $ (id :: A -> A) $ sugar a) (using +Language.Syntactic.Analysis.Evaluation.eval) Injection from sub to sup Partial projection from sup to sub !Co-product of two symbol domains #Fully applied abstract syntax tree ?Generic abstract syntax tree, parameterized by a symbol domain  In general, ( dom (a ) b))$ represents a partially applied (or > unapplied) constructor, missing at least one argument, while  ( dom (,+ a))0 represents a fully applied constructor, i.e. a  complete syntax tree. 7 It is not possible to construct a total value of type ( dom a) that ! does not fulfill the constraint (' a). Note that the hidden class  mentioned in the type of   is  interchangeable with '.  !7Expressions in syntactic are supposed to have the form  (' a => expr a)!. This class lets us witness the ' ? constraint of an expression without examining the expression. "# A witness of (' a) $%Returns the result type (,+ removed) of a '. This is a public  alias for the hidden type . &Maps a ' to a simpler form where ) has been replaced by ->,  and ,+> has been removed. This is a public alias for the hidden type  . ''Fully or partially applied constructor ,This is a public alias for the hidden class . The only instances  are:  instance ConsType' (Full a) - instance ConsType' b => ConsType' (a :-> b) 'Fully or partially applied constructor IThis class is private to the module to guarantee that all members of the  class have the form:   Full a  a1 :-> Full a2  a1 :-> a2 :-> ... :-> Full an (The closed class also has the property:  ConsType' (a :-> b) iff. ConsType' b. (6Heterogeneous list, indexed by a container type and a ' );The type of a partially applied (or unapplied) constructor *+(The type of a fully applied constructor ,-.%Make a constructor evaluation from a & representation /0.Convert a heterogeneous list to a normal list 1.Convert a heterogeneous list to a normal list 2=Change the container of each element in a heterogeneous list 3*Apply the syntax tree to listed arguments 4!Semantic constructor application 5Syntactic type casting 6Like 7/ but with the result indexed by the constructor' s result  type 7 Query an : using a function that gets direct access to the top-most  constructor and its sub-trees $This function can be used to create $ traversal functions indexed by the  symbol types, for example:   class Count subDomain  where J count' :: Count domain => subDomain a -> HList (AST domain) a -> Int  < instance (Count sub1, Count sub2) => Count (sub1 :+: sub2)  where - count' (InjectL a) args = count' a args - count' (InjectR a) args = count' a args  ) count :: Count dom => ASTF dom a -> Int  count = queryNode count' Here, count' represents some static analysis on an . Each constructor  in the tree will be queried by count'% indexed by the corresponding symbol  type. That way, count'2 can be seen as an open-ended function on an open  data type. The (Count domain) constraint on count' is to allow recursion  over sub-trees. Let's say we have a symbol   data Add a  where + Add :: Add (Int :-> Int :-> Full Int)  Then the Count instance for Add might look as follows:  instance Count Add  where : count' Add (a :*: b :*: Nil) = 1 + count a + count b 8 Transform an : using a function that gets direct access to the top-most < constructor and its sub-trees. This function is similar to 7, but  returns a transformed & rather than abstract interpretation. 9:&Type application for constraining the ctx type of a parameterized symbol ;7  !"#$%&'()*+,-./0123456789:;5+,-)*('&%#$!"./01234 5678  9 :;5    !""#$$%&'()**+,-,-./0123456789:;<1Equality for expressions. The difference between  and < is that  <D allows comparison of expressions with different value types. It is M assumed that when the types differ, the expressions also differ. The reason L for allowing comparison of different types is that this is convenient when ) the types are existentially quantified. => Computes a / for an expression. Expressions that are equal  according to = must result in the same hash: = a b ==> > a == > b<=><=><=>=> ?@FConvert a partially applied constructor to a syntax tree given a list  of rendered missing arguments AIRender an expression as concrete syntax. A complete instance must define  either of the methods B and C. BRender an expression as a  CHRender a partially applied constructor given a list of rendered missing  arguments DPrint an expression 'Convert an expression to a syntax tree E!Show syntax tree using ASCII art F"Print syntax tree using ASCII art ?@ABCDEFABCD?@EF?@@ABCBCDEFGHEvaluation of expressions IGHIGHIGHHI JK5Annotating an expression with arbitrary information. KThis can be used to annotate every node of a syntax tree, which is done by  changing   AST dom a to   AST (Ann info dom) a  Injection/.projection of an annotated tree is done using  O / P. LMNOPQ)Get the annotation of the top-level node R%Collect the annotations of all nodes JKLMNOPQR KLMNJOPQR JKLMNLMNOPQRN  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQR S4Class of expressions that can be treated as symbols TUVWA zero-argument symbol XA one-argument symbol YA two-argument symbol ZA three-argument symbol [A four-argument symbol \Default implementation of = ]Default implementation of > ^Default implementation of C _Default implementation of H STUVWXYZ[\]^_ UVWXYZ[ST\]^_ STTUVVWXYZ[\]^_`abLiteral with explicit context cLiteral d1Partial literal projection with explicit context `abcd`abcd`aabcd efg-Conditional expression with explicit context hConditional expression iPartial fe" projection with explicit context efghiefghieffghi j.Expressions for selecting elements of a tuple klmnopqr$Expressions for constructing tuples stuvwxyPartial r" projection with explicit context z{|}~Partial j" projection with explicit context #Return the selected position, e.g. K selectPos (Sel3 poly :: Select Poly ((Int,Int,Int,Int) :-> Full Int)) = 3 jklmnopqrstuvwxyz{|}~rxwvutsyz{|}~jqponmlkjqponmlkklmnopqrxwvutsstuvwxyz{|}~  Let binding A C expression is really just an application of a lambda binding (the  argument (a -> b) is preferably constructed by ). %The class of n-ary binding functions 3N-ary binding by nested use of the supplied binder Lambda binding  Variables Variable identifier Partial " projection with explicit context Partial " projection with explicit context KAlpha equivalence in an environment of variable equivalences. The supplied M equivalence function gets called when the argument expressions are not both  s, both  s or both . HAlpha-equivalence on lambda expressions. Free variables are taken to be . equivalent if they have the same identifier. /Evaluation of possibly open lambda expressions (Evaluation of closed lambda expressions Partial " projection with explicit context =? does strict identifier comparison; i.e. no alpha equivalence. > assigns the same hash to all  bindings. This is a valid 9 over-approximation that enables the following property:  a b ==> > a == > b=? does strict identifier comparison; i.e. no alpha equivalence. >9 assigns the same hash to all variables. This is a valid 9 over-approximation that enables the following property:  a b ==> > a == > b 5Convenient class alias for n-ary syntactic functions Higher-order lambda binding Lambda binding N-ary lambda binding "Let binding with explicit context  Let binding CTranslating expressions with higher-order binding to corresponding ' expressions using first-order binding ;Reifying an n-ary syntactic function with explicit context %Reifying an n-ary syntactic function   !%Pattern functor representation of an  with s "Abstract Syntax Graph" <A representation of a syntax tree with explicit sharing. An  is valid if  and only if  succeeds (and the  field is correct). Top-level expression 'Mapping from node id to sub-expression Total number of nodes An  with hidden result type Placeholder for a syntax tree Node identifier Partial " projection with explicit context "Show syntax graph using ASCII art #Print syntax graph using ASCII art "Update the node identifiers in an  using the supplied reindexing  function LReindex the nodes according to the given index mapping. The number of nodes L is unchanged, so if the index mapping is not 1:1, the resulting graph will  contain duplicates. %Reindex the nodes to be in the range  [0 .. l-1], where l is the number  of nodes in the graph DRemove duplicate nodes from a graph. The function only looks at the   of each node. The  field is updated accordingly. Folding over a graph >The user provides a function to fold a single constructor (an "algebra"). J The result contains the result of folding the whole graph as well as the O result of each internal node, represented both as an array and an association , list. Each node is processed exactly once.  Convert an  to an  by inlining all nodes IFind the child nodes of each node in an expression. The child nodes of a  node n* are the first nodes along all paths from n. >Count the number of occurrences of each node in an expression %Inline all nodes that are not shared HCompute a table (both array and list representation) of hash values for  each node IPartitions the nodes such that two nodes are in the same sub-list if and $ only if they are alpha-equivalent. =Common sub-expression elimination based on alpha-equivalence !!! of a (c (,+ a)) with hidden result type 0Return a fresh identifier from the given supply Shorthand used by  GWrites out a list of encountered nodes and returns the top expression. 4Convert a syntax tree to a sharing-preserving graph :This function is not referentially transparent (hence the ). However, it M is well-behaved in the sense that the worst thing that could happen is that ; sharing is lost. It is not possible to get false sharing. <A function that decides whether a given node can be shared.   means "don't share";  means "share". Nodes whose  result type fulfills (  ctx a)! can be shared, which is why the  function returns a  . Shorthand used by  GWrites out a list of encountered nodes and returns the top expression. 4Convert a syntax tree to a sharing-preserving graph CReifying an n-ary syntactic function to a sharing-preserving graph :This function is not referentially transparent (hence the ). However, it M is well-behaved in the sense that the worst thing that could happen is that ; sharing is lost. It is not possible to get false sharing. <A function that decides whether a given node can be shared.   means "don't share";  means "share". Nodes whose  result type fulfills (  ctx a)! can be shared, which is why the  function returns a  .  !"#$%&'()*+,-./01234556789:;<<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[[\]^_`abcddefghijklmnnopq r r s t u v w x y z { | } ~                                    syntactic-0.5 Language.Syntactic.Sharing.UtilsLanguage.Syntactic.Syntax$Language.Syntactic.Analysis.Equality"Language.Syntactic.Analysis.Render&Language.Syntactic.Analysis.Evaluation$Language.Syntactic.Features.Annotate"Language.Syntactic.Features.Symbol#Language.Syntactic.Features.Literal%Language.Syntactic.Features.Condition!Language.Syntactic.Features.Tuple#Language.Syntactic.Features.Binding/Language.Syntactic.Features.Binding.HigherOrder Language.Syntactic.Sharing.Graph%Language.Syntactic.Sharing.StableName Language.Syntactic.Sharing.Reify"Language.Syntactic.Sharing.ReifyHOLanguage.Syntactic.Language.Syntactic.Features.TupleSyntacticPolyDListemptysingle fromDListreindexcount fullPartitionPoly WitnessSatContext witnessSatWitness'SatWitnesswitness SyntacticNdesugarNsugarN SyntacticInternaldesugarsugar:<:injectproject:+:InjectRInjectLASTFAST:$:Symbol WitnessCons witnessConsConsWit EvalResultConsEvalConsTypeHList:->PartialFullresultfromEvaltoEval listHList listHListMmapHListappHList$:resugar queryNodeI queryNode transformNodewitness' withContextpolyExprEqexprEqexprHashToTree toTreePartRenderrender renderPart printExprshowASTdrawASTEvalevaluateevalFullAnnSTFAnnannInfoannExpr injectAnn projectAnngetInfo collectInfoIsSymboltoSymSymsym0sym1sym2sym3sym4 exprEqFunc exprHashFuncrenderPartFunc evaluateFuncLiterallitCtxlit prjLiteral Condition conditionCtx condition prjConditionSelectSel7Sel6Sel5Sel4Sel3Sel2Sel1TupleTup7Tup6Tup5Tup4Tup3Tup2prjTuple desugarTup2 desugarTup3 desugarTup4 desugarTup5 desugarTup6 desugarTup7 prjSelect selectPos sugarTup2 sugarTup3 sugarTup4 sugarTup5 sugarTup6 sugarTup7LetNAryNAryEvalbindNLambdaVariableVarId varIntegershowVar prjVariable prjLambdaalphaEqMalphaEq evalLambdaM evalLambdaprjLet ReifiableHOASTFHOASTHOLambdalambdalambdaN letBindCtxletBindreifyMreifyTopreifyCtxreifySyntaxPFDomPFNodePFAppPFASG topExpression graphNodesnumNodesSomeASTNodeNodeId nodeIntegershowNodeprjNodeshowASGdrawASGreindexNodesAST reindexNodesreindexNodesFrom0nubNodes liftSome2 foldGraph inlineAll nodeChildren occurrences inlineSingle hashNodespartitionNodescseHistoryStNamestCasthash lookHistoryrememberfresh reifyGraph reifyGraphTopWrapunWrap ConsType' EvalResult' ConsEval' fromEval'toEval' listHList' listHListM' mapHList' appHList':*:Nilbase GHC.ClassesEqdata-hash-0.1.0.0Data.Hash.BaseHashGHC.BaseStringtoTree$fExprEqLambda$fExprEqVariableSystem.Mem.StableName StableName GraphMonad reifyGraphMghc-prim GHC.TypesIO Data.MaybeNothingJust