N      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmn 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). FRepresentation of "simple" types: types satisfying  ( a,  a,  a) 9Representation 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 1Language.Syntactic.Interpretation.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 01.Convert a heterogeneous list to a normal list 2.Convert a heterogeneous list to a normal list 3=Change the container of each element in a heterogeneous list 4FChange the container of each element in a heterogeneous list, monadic  version 5*Apply the syntax tree to listed arguments 6!Semantic constructor application 7Syntactic type casting 8Like 9/ but with the result indexed by the constructor' s result  type 9 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 :Like ;3 but with the result wrapped in a type constructor c ; Transform an : using a function that gets direct access to the top-most < constructor and its sub-trees. This function is similar to 9, but  returns a transformed & rather than abstract interpretation. <=&Type application for constraining the ctx type of a parameterized symbol >?=  !"#$%&'()*+,-./0123456789:;<=>?9,-.*+)('&$%"#/0123456! 789:; < =>?9   ! !"##$%%&'()*++,-.-./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. AB Computes a / for an expression. Expressions that are equal  according to A must result in the same hash: A a b ==> B a == B b@AB@AB@ABAB CDFConvert a partially applied constructor to a syntax tree given a list  of rendered missing arguments EIRender an expression as concrete syntax. A complete instance must define  either of the methods F and G. FRender an expression as a  GHRender a partially applied constructor given a list of rendered missing  arguments HPrint an expression 'Convert an expression to a syntax tree I!Show syntax tree using ASCII art J"Print syntax tree using ASCII art CDEFGHIJEFGHCDIJCDDEFGFGHIJKLEvaluation of expressions MKLMKLMKLLM NO5Annotating 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  S / T. PQRSTU)Get the annotation of the top-level node V%Collect the annotations of all nodes W$Rendering of annotated syntax trees X.Show an annotated syntax tree using ASCII art Y/Print an annotated syntax tree using ASCII art NOPQRSTUVWXY OPQRNSTUVWXY NOPQRPQRSTUVWXYW  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ4Class of expressions that can be treated as symbols [\]^_A zero-argument symbol `A one-argument symbol aA two-argument symbol bA three-argument symbol cA four-argument symbol d0Partial symbol projection with explicit context eDefault implementation of A fDefault implementation of B gDefault implementation of G hDefault implementation of L Z[\]^_`abcdefgh\]^_`abcdZ[efghZ[[\]]^_`abcdefghijkLiteral with explicit context lLiteral m1Partial literal projection with explicit context ijklmijklmijjklm nop-Conditional expression with explicit context qConditional expression rPartial on" projection with explicit context nopqrnopqrnoopqr s.Expressions for selecting elements of a tuple tuvwxyz{$Expressions for constructing tuples |}~Partial {" projection with explicit context Partial s" projection with explicit context #Return the selected position, e.g. K selectPos (Sel3 poly :: Select Poly ((Int,Int,Int,Int) :-> Full Int)) = 3 stuvwxyz{|}~{~}|szyxwvutszyxwvuttuvwxyz{~}||}~  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 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 A? does strict identifier comparison; i.e. no alpha equivalence. B assigns the same hash to all  bindings. This is a valid 9 over-approximation that enables the following property:  a b ==> B a == B bA? does strict identifier comparison; i.e. no alpha equivalence. B9 assigns the same hash to all variables. This is a valid 9 over-approximation that enables the following property:  a b ==> B a == B 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   Partial evaluation %Partial evaluation of a feature. The ( ) returned is the F set of free variables of the expression. However, free variables are  counted in a "lazy"5 sense: free variables from sub-expressions that are 7 never evaluated may not be counted. (The instance for  Conditional will J throw away the free variables of the pruned branch when the condition is F statically known. This is one reason why partial evaluation and free 7 variable calculation have to be done simultaneously.) Constant folder GGiven an expression and the statically known value of that expression, L returns a (possibly) new expression with the same meaning as the original. ! Typically, the result will be a ji#, if the relevant type constraints  are satisfied. !Partially evaluate an expression %Convenient default implementation of  (uses  to  evaluate) !%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  .  !!"#$%&'()*+,-./01234567889:;<=>??@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`aabcdefghijklmmnopqrstuvwxyyz{| } } ~                                            syntactic-0.6 Language.Syntactic.Sharing.UtilsLanguage.Syntactic.Syntax*Language.Syntactic.Interpretation.Equality(Language.Syntactic.Interpretation.Render,Language.Syntactic.Interpretation.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.Features.Binding.PartialEval Language.Syntactic.Sharing.Graph%Language.Syntactic.Sharing.StableName Language.Syntactic.Sharing.Reify"Language.Syntactic.Sharing.ReifyHOLanguage.Syntactic.Language.Syntactic.Features.TupleSyntacticPoly0Language.Syntactic.Features.TupleSyntacticSimpleDListemptysingle fromDListreindexcount fullPartition SimpleCtxPoly WitnessSatContext witnessSatWitness'SatWitnesswitness SyntacticNdesugarNsugarN SyntacticInternaldesugarsugar:<:injectproject:+:InjectRInjectLASTFAST:$:Symbol WitnessCons witnessConsConsWit EvalResultConsEvalConsTypeHList:->PartialFullresultfromEvaltoEval listHList listHListMmapHList mapHListMappHList$:resugar queryNodeI queryNodetransformNodeC transformNodewitness' withContextpoly simpleCtxExprEqexprEqexprHashToTree toTreePartRenderrender renderPart printExprshowASTdrawASTEvalevaluateevalFullAnnSTFAnnannInfoannExpr injectAnn projectAnngetInfo collectInfo toTreeAnnshowANNdrawANNIsSymboltoSymSym witnessSatSymsym0sym1sym2sym3sym4prjSym exprEqSym exprHashSym renderPartSym evaluateSymLiterallitCtxlit prjLiteral Condition conditionCtx condition prjConditionSelectSel7Sel6Sel5Sel4Sel3Sel2Sel1TupleTup7Tup6Tup5Tup4Tup3Tup2prjTuple desugarTup2 desugarTup3 desugarTup4 desugarTup5 desugarTup6 desugarTup7 prjSelect selectPos sugarTup2 sugarTup3 sugarTup4 sugarTup5 sugarTup6 sugarTup7LetNAryNAryEvalbindNLambdaVariableVarId varIntegershowVar prjVariable prjLambdaprjLetalphaEqMalphaEq evalLambdaM evalLambda ReifiableHOASTFHOASTHOLambdalambdalambdaN letBindCtxletBindreifyMreifyTopreifyCtxreify PartialEval partEvalFeat ConstFolder partialEvalM partialEvalpartEvalFeatDefaultSyntaxPFDomPFNodePFAppPFASG topExpression graphNodesnumNodesSomeASTNodeNodeId nodeIntegershowNodeprjNodeshowASGdrawASGreindexNodesAST reindexNodesreindexNodesFrom0nubNodes liftSome2 foldGraph inlineAll nodeChildren occurrences inlineSingle hashNodespartitionNodescseHistoryStNamestCasthash lookHistoryrememberfresh reifyGraph reifyGraphTopbase GHC.ClassesEqGHC.ShowShow Data.TypeableTypeableWrapunWrap ConsType' EvalResult' ConsEval' fromEval'toEval' listHList' listHListM' mapHList' mapHListM' appHList':*:Nil SimpleWitPolyWitdata-hash-0.1.0.0Data.Hash.BaseHashGHC.BaseStringtoTree$fExprEqLambda$fExprEqVariablecontainers-0.4.0.0Data.SetSetSystem.Mem.StableName StableName GraphMonad reifyGraphMghc-prim GHC.TypesIO Data.MaybeNothingJust