3/      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvw x y z { | } ~       NoneDifference 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. 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). 4Upper and lower bound on the elements to be counted Elements to be counted None*Representation of "simple" types: types satisfying  ( a,  a,  a) 9Representation of a fully polymorphic constraint -- i.e. (  a)  is satisfied by all types a. 7Expressions that act as witnesses of their result type 7Expressions 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. Witness' 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 ) Injection from sub to sup Partial projection from sup to sub 7Class that performs the type-level recursion needed by = !Co-product of two symbol domains !#Fully applied abstract syntax tree "?Generic abstract syntax tree, parameterized by a symbol domain  In general, (" dom (a 0 b))$ represents a partially applied (or > unapplied) constructor, missing at least one argument, while  (" dom (2 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 (2 removed) of a +. This is a public  alias for the hidden type . *Maps a + to a simpler form where 0 has been replaced by ->,  and 2> 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 Signature' (Full a) / instance Signature' b => Signature' (a :-> b) ,2Can be used to turn a type constructor indexed by a to a type constructor  indexed by (2 a). This is useful together with /, which assumes " its constructor to be indexed by (2 a). That is, use   Args (WrapFull c) ...  instead of   Args c ... if c is not indexed by (2 a). /6Heterogeneous list, indexed by a container type and a + 0;The type of a partially applied (or unapplied) constructor 2(The type of a fully applied constructor 5%Make a constructor evaluation from a * representation 7.Convert a heterogeneous list to a normal list 8=Change the container of each element in a heterogeneous list 9FChange the container of each element in a heterogeneous list, monadic  version :.Apply the syntax tree to the listed arguments ;6Apply the evaluation function to the listed arguments <!Semantic constructor application =Generic symbol application = has any type of the form: G appSym :: (expr :<: AST dom, Typeable a, Typeable b, ..., Typeable x) * => expr (a :-> b :-> ... :-> Full x) 8 -> (ASTF dom a -> ASTF dom b -> ... -> ASTF dom x) >1Generic symbol application with explicit context ? with explicit context @ with explicit context ASyntactic type casting B"Sugared" symbol application B has any type of the form:  sugarSym ::  ( expr :<: AST dom  , Syntactic a dom  , Syntactic b dom  , ...  , Syntactic x dom I ) => expr (Internal a :-> Internal b :-> ... :-> Full (Internal x))  -> (a -> b -> ... -> x) C"Sugared"* symbol application with explicit context D Query an ": using a function that gets direct access to the top-most  constructor and its sub-trees %Note that, by instantiating the type c with " dom' , we get the " following type, which shows that D can be directly used to " transform syntax trees (see also F): Y (forall b . (Signature b, a ~ DenResult b) => dom b -> Args (AST dom) b -> ASTF dom' a)  -> ASTF dom a  -> ASTF dom' a EA simpler version of D $This function can be used to create "$ traversal functions indexed by the  symbol types, for example:   class Count subDomain  where I count' :: Count domain => subDomain a -> Args (AST domain) a -> Int  < instance (Count sub1, Count sub2) => Count (sub1 :+: sub2)  where * count' (InjL a) args = count' a args * count' (InjR a) args = count' a args  ) count :: Count dom => ASTF dom a -> Int  count = queryNodeSimple 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 8 count' Add (a :* b :* Nil) = 1 + count a + count b F A version of D0 where the result is a transformed syntax tree,  wrapped in a type constructor c I%Convenient default implementation of   J&Type application for constraining the ctx type of a parameterized symbol Y  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKL !"#$%&'J  !"#$%&'()*+,-./01234()56789:;<=>?@ABCDEFGHIJKLF23401/,-.+*)'(%&56789:;<"$#! =>?@ABCDEFGH IJKL?    !"$#%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKL !"#$%&'NoneM1Equality for expressions. The difference between  and M is that  MD 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. O Computes a */ for an expression. Expressions that are equal  according to N must result in the same hash: N a b ==> O a == O bMNO+,-.MNOMNOMNO+,-.NoneQFConvert a partially applied constructor to a syntax tree given a list  of rendered missing arguments RIRender an expression as concrete syntax. A complete instance must define  either of the methods S and T. SRender an expression as a / THRender a partially applied constructor given a list of rendered missing  arguments UPrint an expression V!Show syntax tree using ASCII art W"Print syntax tree using ASCII art PQRSTUVW012345PQRSTUVWRSTUPQVW PQRSTUVW012345NoneYEvaluation of expressions XYZ67XYZXYZXYZ67None [5Decorating an expression with additional information  One usage of [: is to decorate every node of a syntax tree. This is done  simply by changing   AST dom a to   AST (Decor info dom) a  Injection/.projection of an decorated tree is done using _ /  `. a_ with explicit context b` with explicit context c)Get the decoration of the top-level node d,Update the decoration of the top-level node eLLift a function that operates on expressions with associated information to  operate on an [9 expression. This function is convenient to use together  with e.g. E when the domain has the form  ([ info dom). f%Collect the decorations of all nodes g$Rendering of decorated syntax trees h.Show an decorated syntax tree using ASCII art i/Print an decorated syntax tree using ASCII art jStrip decorations from an " [\]^_`abcdefghij89:;<=>[\]^_`abcdefghij[\]^_`abcdefghij[\]^_`abcdefghij89:;<=>NoneX  !"#$%&'()*+,-./01234()56789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZNonek7Class of expressions that can be treated as constructs m/A representation of a syntactic construct as a / and an evaluation B function. It is not meant to be used as a syntactic symbol in an ". Its J only purpose is to provide the default implementations of functions like  N via the k class. qDefault implementation of N rDefault implementation of O sDefault implementation of T tDefault implementation of Y klmnopqrst?@A klmnopqrst mnopklqrst klmnopqrst?@ANone uvBCDEFGHIJuvuv uvBCDEFGHIJ None wxKLMNOPQRwxwx wxKLMNOPQR NoneyIdentity function yzSTUVWXYZ[yzyz yzSTUVWXYZ[ None {|\]^_`abc{|{| {|\]^_`abc None$Projection with explicit monad type }~defghij}~}~ }~defghij None.Expressions for selecting elements of a tuple These families ( - $) are needed because of the problem  described in:  Jhttp://emil-fp.blogspot.com/2011/08/fundeps-weaker-than-type-families.html $Expressions for constructing tuples #Return the selected position, e.g. K selectPos (Sel3 poly :: Select Poly ((Int,Int,Int,Int) :-> Full Int)) = 3 5klmnopqrstuvwxyz{|##(klmnopqrstuvwxyz{|None8Environments containing a list of variable equivalences  Let binding A C expression is really just an application of a lambda binding (the  argument (a -> b) is preferably constructed by ). Lambda binding  Variables Variable identifier "Let binding with explicit context Partial " projection with explicit context Capture-avoiding substitution LBeta-reduction of an expression. The expression to be reduced is assumed to  be a . (Evaluation of possibly open expressions !Evaluation of closed expressions %Convenient default implementation of  HAlpha-equivalence on lambda expressions. Free variables are taken to be . equivalent if they have the same identifier. }N? does strict identifier comparison; i.e. no alpha equivalence. O assigns the same hash to all  bindings. This is a valid 9 over-approximation that enables the following property:  a b ==> O a == O b~N? does strict identifier comparison; i.e. no alpha equivalence. O9 assigns the same hash to all variables. This is a valid 9 over-approximation that enables the following property:  a b ==> O a == O bKVariable to be substituted Expression to substitute for Expression to substitute in  Argument Function to be reduced }~B}~NoneNoneNoneHigher-order lambda binding Lambda binding CTranslating expressions with higher-order binding to corresponding ' expressions using first-order binding %Reifying an n-ary syntactic function  None#Basic optimization of a sub-domain FBottom-up optimization of a sub-domain. The optimization performed is H up to each instance, but the intention is to provide a sensible set of  "always-appropriate"+ optimizations. The default implementation  3 does only constant folding. This constant folding / uses the set of free variables to know when it's static evaluation is A possible. Thus it is possible to help constant folding of other K constructs by pruning away parts of the syntax tree that are known not to D be needed. For example, by replacing (using ordinary Haskell as an  example)   if True then a else b with a, we don''t need to report the free variables in b . This, in G turn, can lead to more constant folding higher up in the syntax tree. 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 {#, if the relevant type constraints  are satisfied. Optimize an expression %Convenient default implementation of  (uses  to  partially evaluate) None,User interface to embedded monadic programs (One-layer desugaring of monadic actions &One-layer sugaring of monadic actions None!Interface for binding constructs @Perform common sub-expression elimination and variable hoisting Like 9 but with common sub-expression elimination and variable  hoisting None%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 "Environment for alpha-equivalence An ! with hidden result type Placeholder for a syntax tree Node identifier "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 -%% None of a (c (2 a)) with hidden result type  0Return a fresh identifier from the given supply             None 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 .    None 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 .     !"#$%&'())*+,-./0123456789:;<=>?@AABCDEEFGHIJJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrrstuvwxyz{|}~                                         !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWX Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~             syntactic-0.8 Language.Syntactic.Sharing.UtilsLanguage.Syntactic.Syntax*Language.Syntactic.Interpretation.Equality(Language.Syntactic.Interpretation.Render,Language.Syntactic.Interpretation.Evaluation(Language.Syntactic.Constructs.Decoration+Language.Syntactic.Interpretation.Semantics'Language.Syntactic.Constructs.Condition'Language.Syntactic.Constructs.Construct&Language.Syntactic.Constructs.Identity%Language.Syntactic.Constructs.Literal#Language.Syntactic.Constructs.Monad#Language.Syntactic.Constructs.Tuple%Language.Syntactic.Constructs.Binding1Language.Syntactic.Constructs.Binding.HigherOrder.Language.Syntactic.Constructs.Binding.Optimize!Language.Syntactic.Frontend.Monad+Language.Syntactic.Sharing.SimpleCodeMotion Language.Syntactic.Sharing.Graph%Language.Syntactic.Sharing.StableName Language.Syntactic.Sharing.Reify"Language.Syntactic.Sharing.ReifyHOevalLanguage.Syntactic0Language.Syntactic.Constructs.TupleSyntacticPoly2Language.Syntactic.Constructs.TupleSyntacticSimpleDListemptysingle fromDListreindexcount fullPartition SimpleCtxPolyMaybeWitnessSatmaybeWitnessSat WitnessSat SatContext witnessSatSatWitSatWitnesswitness SyntacticNdesugarNsugarN SyntacticInternaldesugarsugar:<:injprjApplySym:+:InjRInjLASTFAST:$Sym WitnessCons witnessConsConsWit DenResult Denotation SignatureWrapFull unwrapFullArgs:->PartialFullresultfromEvaltoEvallistArgsmapArgsmapArgsMappArgs appEvalArgs$:appSym appSymCtxinjCtxprjCtxresugarsugarSym sugarSymCtx queryNodequeryNodeSimple transformNodewitnessByProxy fromSatWitmaybeWitnessSatDefault withContextpoly simpleCtxExprEqexprEqexprHashToTree toTreePartRenderrender renderPart printExprshowASTdrawASTEvalevaluateevalFullDecor decorInfo decorExprinjDecorprjDecor injDecorCtx prjDecorCtxgetInfo updateDecor liftDecor collectInfo toTreeDecor showDecor drawDecor stripDecorSemantic semantics SemanticsSem semanticName semanticEval exprEqSem exprHashSem renderPartSem evaluateSem Condition ConstructIdentityIdLiteralMONADWhenThenBindReturnprjMonadSelectSel7Sel6Sel5Sel4Sel3Sel2Sel1Sel7'Sel6'Sel5'Sel4'Sel3'Sel2'Sel1'TupleTup7Tup6Tup5Tup4Tup3Tup2 desugarTup2 desugarTup3 desugarTup4 desugarTup5 desugarTup6 desugarTup7 selectPos sugarTup2 sugarTup3 sugarTup4 sugarTup5 sugarTup6 sugarTup7AlphaEq alphaEqSymVarEqEnv prjVarEqEnv modVarEqEnvEvalBind evalBindSymLetLambdaVariableVarId varIntegershowVarletBindprjLetsubst betaReduce evalBindMevalBindevalBindSymDefaultalphaEqM alphaEqM2alphaEqalphaEqSymDefaultalphaEqChildrenHODomainHOLambdalambdareifyMreifyTopreifyOptimize optimizeSym ConstFolder optimizeMoptimizeoptimizeSymDefaultMonunMon desugarMonad sugarMonadBindDict prjVariable prjLambda injVariable injLambdainjLet codeMotiondefaultBindDict reifySmartSyntaxPFDomPFNodePFAppPFASG topExpression graphNodesnumNodesNodeEnvEqEnv NodeEqEnv prjNodeEqEnv modNodeEqEnvSomeASTNodeNodeId nodeIntegershowNodeshowASGdrawASGreindexNodesAST reindexNodesreindexNodesFrom0nubNodes liftSome2 foldGraph inlineAll nodeChildren occurrences inlineSingle hashNodespartitionNodescseHistoryStNamestCasthash lookHistoryrememberfresh reifyGraph reifyGraphTopghc-prim GHC.ClassesEqbaseGHC.ShowShowData.Typeable.InternalTypeable Signature' DenResult' Denotation':*Nil$fSatSimpleCtxa $fSatPolya$fMaybeWitnessSatctx:+:$fMaybeWitnessSatctxAST$fSyntacticN(->)(->)$fSyntacticNaia$fSyntacticASTdom $f:<:expr1:+:$f:<:expr1:+:0 $f:<:exprexpr $f:<:subAST$fApplySym:->(->)dom$fApplySymFullASTdom$fWitnessCons:+: $fSignaturea$fSignature':->$fSignature'Full SimpleWitPolyWitdata-hash-0.1.0.0Data.Hash.BaseHash$fEq:+: $fExprEq:+:$fEqAST $fExprEqASTGHC.BaseString $fToTree:+: $fToTreeAST $fShow:+: $fRender:+: $fShowAST $fRenderAST $fEval:+: $fEvalAST $fEvalDecor $fToTreeDecor $fRenderDecor $fExprEqDecor$fMaybeWitnessSatctxDecor$fWitnessSatDecor$fWitnessConsDecor$fEvalSemantics$fRenderSemantics$fExprEqSemantics$fToTreeCondition$fEvalCondition$fRenderCondition$fExprEqCondition$fSemanticCondition$fMaybeWitnessSatctx1Condition$fMaybeWitnessSatctxCondition$fWitnessSatCondition$fWitnessConsCondition$fEvalConstruct$fToTreeConstruct$fRenderConstruct$fExprEqConstruct$fMaybeWitnessSatctx1Construct$fMaybeWitnessSatctxConstruct$fWitnessSatConstruct$fWitnessConsConstruct$fToTreeIdentity$fEvalIdentity$fRenderIdentity$fExprEqIdentity$fSemanticIdentity$fMaybeWitnessSatctx1Identity$fMaybeWitnessSatctxIdentity$fWitnessSatIdentity$fWitnessConsIdentity $fEvalLiteral$fToTreeLiteral$fRenderLiteral$fExprEqLiteral$fMaybeWitnessSatctx1Literal$fMaybeWitnessSatctxLiteral$fWitnessSatLiteral$fWitnessConsLiteral $fToTreeMONAD $fEvalMONAD $fRenderMONAD $fExprEqMONAD$fSemanticMONAD$fMaybeWitnessSatctxMONAD$fWitnessConsMONAD$fToTreeSelect $fEvalSelect$fRenderSelect$fExprEqSelect$fSemanticSelect$fMaybeWitnessSatctx1Select$fMaybeWitnessSatctxSelect$fWitnessSatSelect$fWitnessConsSelect $fToTreeTuple $fEvalTuple $fRenderTuple $fExprEqTuple$fSemanticTuple$fMaybeWitnessSatctx1Tuple$fMaybeWitnessSatctxTuple$fWitnessSatTuple$fWitnessConsTuple$fExprEqLambda$fExprEqVariable$fAlphaEqVariableVariabledomenv$fAlphaEqLambdaLambdadomenv$fAlphaEqDecorDecorDecorenv$fAlphaEqMONADMONADdomenv$fAlphaEqLetLetdomenv$fAlphaEqSelectSelectdomenv$fAlphaEqTupleTupledomenv!$fAlphaEqConditionConditiondomenv$fAlphaEqLiteralLiteraldomenv!$fAlphaEqConstructConstructdomenv$fAlphaEqIdentityIdentitydomenv$fAlphaEq:+::+:domenv $fVarEqEnv[]$fEvalBindVariable$fEvalBindLambda$fEvalBindDecor$fEvalBindMONAD $fEvalBindLet$fEvalBindSelect$fEvalBindTuple$fEvalBindCondition$fEvalBindLiteral$fEvalBindConstruct$fEvalBindIdentity $fEvalBind:+: $fEvalLet $fToTreeLet $fRenderLet $fExprEqLet$fMaybeWitnessSatctxLet$fMaybeWitnessSatctxbLet$fWitnessSatLet$fWitnessConsLet$fToTreeLambda$fRenderLambda$fMaybeWitnessSatctx1Lambda$fWitnessConsLambda$fToTreeVariable$fRenderVariable$fMaybeWitnessSatctx1Variable$fMaybeWitnessSatctxVariable$fWitnessSatVariable$fWitnessConsVariable $fShowVarId$fSyntactic(,,,,,,)dom$fSyntactic(,,,,,)dom$fSyntactic(,,,,)dom$fSyntactic(,,,)dom$fSyntactic(,,)dom$fSyntactic(,)dom$fSyntactic(->):+:$fMaybeWitnessSatctx1HOLambda$fWitnessConsHOLambda$fOptimizeLambdactxdom$fOptimizeVariablectxdom$fOptimizeConditionctxdom$fOptimizeLetctxdom$fOptimizeSelectctxdom$fOptimizeTuplectxdom$fOptimizeLiteralctxdom$fOptimizeConstructctxdom$fOptimizeIdentityctxdom$fOptimize:+:ctxdom$fSyntacticMon:+: $fMonadMon$fFunctorSyntaxPF$fAlphaEqNodeNodedomenv $fVarEqEnv(,)$fNodeEqEnvdom(,) $fToTreeNode $fRenderNode$fWitnessConsNode $fShowNodeIdSystem.Mem.StableName StableName $fEqStName GHC.TypesIO Data.MaybeNothingJust