úÎȔœmV      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTU(C) 2012 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportableSafe a p w replaces the free variable a with p in w.9substitute "hello" ["goodnight","Gracie"] ["hello","!!!"]["goodnight","Gracie","!!!"] a b w replaces a free variable a with another free variable b in w.5substituteVar "Alice" "Bob" ["Alice","Bob","Charlie"]["Bob","Bob","Charlie"]jIf a term has no free variables, you can freely change the type of free variables it is parameterized on. closed [12]Nothing closed ""Just [] :t closed ""closed "" :: Maybe [b]$A closed term has no free variables. isClosed []TrueisClosed [1,2,3]False(C) 2012-2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportableSafe1 Instances of # generate left modules over monads.2This means they should satisfy the following laws: m  V "a m m  (» x !’ k x W h) "a (m  k)  h –This guarantees that a typical Monad instance for an expression type where Bound instances appear will satisfy the Monad laws (see doc/BoundLaws.hs).If instances of  are monad transformers, then m  f "a m W X Y f@ implies the above laws, and is in fact the default definition.¡This is useful for types like expression lists, case alternatives, schemas, etc. that may not be expressions in their own right, but often contain expressions.Perform substitutionIf t is an instance of  MonadTransM and you are compiling on GHC >= 7.4, then this gets the default definition: m  f = m W X Y fA flipped version of (). () = Z () [\]^_`abc [\]^_`abc(C) 2012-2013 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportableNoneGUse to automatically derive d and e instances for your datatype.In GHC 7.10 or later the DeriveAnyClass% extension may be used to derive the Show1 and Read1 instances {- LANGUAGE DeriveAnyClass -} {- LANGUAGE DeriveFunctor -} {- LANGUAGE TemplateHaskell æ-} import Bound (Scope, makeBound) import Prelude.Extras (Read1, Show1) data Exp a = V a | App (Exp a) (Exp a) | Lam (Scope () Exp a) | I Int deriving (Functor, Read, Read1, Show, Show1) makeBound ''Exp  and in GHCi ÿ:ghci> :set -XDeriveAnyClass ghci> :set -XDeriveFunctor ghci> :set -XTemplateHaskell ghci> import Bound (Scope, makeBound) ghci> import Prelude.Extras (Read1, Show1) ghci> data Exp a = V a | App (Exp a) (Exp a) | Lam (Scope () Exp a) | I Int deriving (Functor, Read, Read1, Show, Show1); makeBound ''Exp or ¥ghci> :{ ghci| data Exp a = V a | App (Exp a) (Exp a) | Lam (Scope () Exp a) | I Int deriving (Functor, Read, Read1, Show, Show1) ghci| makeBound ''Exp ghci| :} If DeriveAnyClass9 is not used the instances must be declared explicitly:  data Exp a = V a | App (Exp a) (Exp a) | Lam (Scope () Exp a) | I Int deriving (Functor, Read, Show) instance Read1 Exp instance Show1 ExpmakeBound ''Exp @  or in GHCi: Åghci> :{ ghci| data Exp a = V a | App (Exp a) (Exp a) | Lam (Scope () Exp a) | I Int deriving (Functor, Read, Show) ghci| instance Read1 Exp ghci| instance Show1 Exp ghci| makeBound ''Exp ghci| :} f and g[ instances need to be derived differently if the data type's immediate components include Scope (or other instances of )In a file with {- LANGUAGE StandaloneDeriving -} at the top: pinstance Eq1 Exp deriving instance Eq a => Eq (Exp a) instance Ord1 Exp deriving instance Ord a => Ord (Exp a)  or in GHCi: žghci> :set -XStandaloneDeriving ghci> deriving instance Eq a => Eq (Exp a); instance Eq1 Exp ghci> deriving instance Ord a => Ord (Exp a); instance Ord1 Exp because their f and g instances require Exp to be a e:  instance (Monad f, Eq b, Eq1 f, Eq a) => Eq (Scope b f a) instance (Monad f, Ord b, Ord1 f, Ord a) => Ord (Scope b f a) ADoes not work yet for components that are lists or instances of h# or with a great deal other things.ijklmnopqrstu ijklmnopqrstu(C) 2012 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportable Trustworthy+0"I am not a number, I am a  free monad!"A  b a+ is a variable that may either be "bound" (  ) or "free" ( ).H(It is also technically a free monad in the same near-trivial sense as v.) this is a bound variable this is a free variable This provides a Prism that can be used with lens library to access a bound .   :: Prism (Var b a) (Var b' a) b b'@ This provides a Prism that can be used with lens library to access a free .   :: Prism (Var b a) (Var b a') a a'@  w xyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ   w xyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ(C) 2012-2013 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportable Trustworthy*+4IN b f a is an f$ expression with bound variables in b, and free variables in aaWe store bound variables as their generalized de Bruijn representation in that we're allowed to X (using  n) an entire tree rather than only succ individual variables, but we're still only allowed to do so once per . Weakening trees permits O(1)^ weakening and permits more sharing opportunities. Here the deBruijn 0 is represented by the   constructor of , while the de Bruijn : (which may be applied to an entire tree!) is handled by  .6NB: equality and comparison quotient out the distinct   placements allowed by the generalized de Bruijn representation and return the same result as a traditional de Bruijn representation would.FLogically you can think of this as if the shape were the traditional  f (Var b a), but the extra f a inside permits us a cheaper X.9Capture some free variables in an expression to yield a  with bound variables in b:m + Data.List$abstract (`elemIndex` "bar") "barry"Scope [B 0,B 1,B 2,B 2,F "y"]Abstract over a single variableabstract1 'x' "xyz"Scope [B (),F "y",F "z"]0Enter a scope, instantiating all bound variables:m + Data.ListLinstantiate (\x -> [toEnum (97 + x)]) $ abstract (`elemIndex` "bar") "barry""abccy"Enter a * that binds one variable, instantiating it+instantiate1 "x" $ Scope [B (),F "y",F "z"]"xyz"* quotients out the possible placements of   in x by distributing them all to the leaves. This yields a more traditional de Bruijn indexing scheme for bound variables.Since,  Y  "a ‘ we know that  Y  Y  "a and therefore ( . ) is idempotent.DConvert from traditional de Bruijn to generalized de Bruijn indices.#This requires a full tree traversal;Perform substitution on both bound and free variables in a .;Return a list of occurences of the variables bound by this .1Perform a change of variables on bound variables.IPerform a change of variables, reassigning both bound and free variables.>Perform a change of variables on bound variables given only a e instance A version of ) that can be used when you only have the e instance>Obtain a result by collecting information from bound variablesMObtain a result by collecting information from both bound and free variables’ the bound variables in a . “? both the variables bound by this scope and any free variables.!,mapM_ over the variables bound by this scope"A  ' that can be used when you only have a e instance#&Traverse both bound and free variables$&Traverse both bound and free variables%'mapM over both bound and free variables&A $' that can be used when you only have a e instance)This allows you to ” a .*#This is a higher-order analogue of “.,9instantiate bound variables using a list of new variables-#Lift a natural transformation from f to g into one between scopes.•SThe monad permits substitution on free variables, while preserving bound variables–—; is provides a list (with duplicates) of the free variables5 !"#$%&'()*+,-˜™š›œžŸ ¡¢£€¥Š§•š©–ª  !"#$%&'()*+,-  !"#$%&'(-)+*,3 !"#$%&'()*+,-˜™š›œžŸ ¡¢£€¥Š§•š©–ª(C) 2012 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportable Trustworthy+0.We track the choice of . n% as a forgettable property that does not affect the result of («) or ¬.)To compare names rather than values, use (  ¬ 0) instead.0 Extract the 0.1This provides an Iso+ that can be used to access the parts of a .. 1 :: Iso (. n a) (. m b) (n, a) (m, b) 2-Abstraction, capturing named bound variables.3Abstract over a single variable4fEnter a scope, instantiating all bound variables, but discarding (comonadic) meta data, like its name5Enter a 3 that binds one (named) variable, instantiating it. 5 = !./012345­®¯°±²³Žµ¶·ž¹º»ŒœŸ¿ÀÁÂÃÄÅ./012345./102345 ./012345­®¯°±²³Žµ¶·ž¹º»ŒœŸ¿ÀÁÂÃÄÅ(C) 2013 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportable Trustworthy*+4IN66 b f a is an f$ expression with bound variables in b, and free variables in a5This implements traditional de Bruijn indices, while   + implements generalized de Bruijn indices.[These traditional indices can be used to test the performance gain of generalized indices.While this type 6 is identical to   3 this module focuses on a drop-in replacement for   .WAnother use case is for syntaxes not stable under substitution, therefore with only a h instance and no e instance.99Capture some free variables in an expression to yield a 6 with bound variables in b:m + Data.List$abstract (`elemIndex` "bar") "barry"Scope [B 0,B 1,B 2,B 2,F 'y']:Abstract over a single variableabstract1 'x' "xyz"Scope [B (),F 'y',F 'z'];0Enter a scope, instantiating all bound variables:m + Data.ListLinstantiate (\x -> [toEnum (97 + x)]) $ abstract (`elemIndex` "bar") "barry""abccy"<Enter a 6* that binds one variable, instantiating it+instantiate1 "x" $ Scope [B (),F 'y',F 'z']"xyz">> is just another name for 8 and is exported to mimick . In particular no e constraint is required.?? is just another name for 6 and is exported to mimick . In particular no e constraint is required.@;Perform substitution on both bound and free variables in a 6.A;Return a list of occurences of the variables bound by this 6.B1Perform a change of variables on bound variables.CIPerform a change of variables, reassigning both bound and free variables.D>Perform a change of variables on bound variables given only a e instanceE A version of C) that can be used when you only have the e instanceFMObtain a result by collecting information from both bound and free variablesGMObtain a result by collecting information from both bound and free variablesH’ the bound variables in a 6.I“? both the variables bound by this scope and any free variables.J,mapM_ over the variables bound by this scopeKA I' that can be used when you only have a e instanceL&Traverse both bound and free variablesM&Traverse both bound and free variablesNThis allows you to ” a 6.O#This is a higher-order analogue of “.P9instantiate bound variables using a list of new variablesR'mapM over both bound and free variablesSA M' that can be used when you only have a e instanceÆSThe monad permits substitution on free variables, while preserving bound variablesÇ—; is provides a list (with duplicates) of the free variables56789:;<=>?@ABCDEFGHIJKLMNOPQRSTUÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ÆØÙÇÚ 6789:;<=>?@ABCDEFGHIJKLMNOPQRSTU 6789:;<>?@ABCDEFGHIJKLMRSTU=NQOP36789:;<=>?@ABCDEFGHIJKLMNOPQRSTUÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ÆØÙÇÚ (C) 2012 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportableNone  Û    !"#$%&'()*+,-./01234567899:;<=>?   !8"#$%&'()*+,-./45760123@AB@ACDEF@AG@AHIJKLMNOPQ@AR@ASTUVTUW@AXYZ[\ ]^_`abcd@efghijklmnopqrstuvwxyz{|}~@€@A‚@ƒ„@…†‡ˆ‰Š‹@ƒŒŽ‘’“”•–—˜™š›œžŸTU TU¡¢£€¥Š§š©ª«¬­®¯°±²³Žµ¶·ž¹ºŠ‹Ž‘’“”•–—˜™š›œžŸ»bound_9rxqxGiLTueCqhiWOqnho7 Bound.Term Bound.ClassBound.TH Bound.Var Bound.Scope Bound.NameBound.Scope.Simple Data.FunctiononBoundScopeControl.Monad.TransEitherT fromScopetoScope substitute substituteVarclosedisClosed>>>==<<< makeBoundVarBFunvar_B_Funscopeabstract abstract1 instantiate instantiate1splatbindingsmapBoundmapScope liftMBound liftMScope foldMapBound foldMapScopetraverseBound_traverseScope_ mapMBound_ mapMScope_ traverseBound traverseScope mapMBound mapMScopeserializeScopedeserializeScopebitraverseScopetransverseScopebitransverseScopeinstantiateVars hoistScopeNamename_Name abstractName abstract1NameinstantiateNameinstantiate1NamebaseGHC.Basereturn>>=trans_3eG64VdP2vzGjP6wJiCp5XControl.Monad.Trans.Classlift.flip$fBoundWriterT $fBoundStateT$fBoundReaderT $fBoundRWST $fBoundMaybeT $fBoundListT$fBoundIdentityT $fBoundErrorT $fBoundContT ApplicativeMonadghc-prim GHC.ClassesEqOrdFunctor Components ComponentVariablePropKonstExp constructBind construct interpret stripLast2getNamegetPure Data.EitherEither distinguisher $fRead1Var $fShow1Var $fOrd1Var$fEq1Var $fRead2Var $fShow2Var $fOrd2Var$fEq2Var$fBitraversableVar$fBifoldableVar$fBifunctorVar $fMonadVar$fApplicativeVar$fTraversableVar $fFoldableVar $fFunctorVar$fSerializeVar $fBinaryVar $fSerialVar $fSerial1Var $fSerial2Var $fHashableVar$fHashable1Var$fHashable2VarGHC.Enumsuccid Data.Foldable traverse_Data.Traversabletraversebifun_5YALODvEtA24oFsRFahHMXData.Bitraversable bitraverse $fMonadScope$fFoldableScopetoList$fSerializeScope $fBinaryScope $fSerialScope$fSerial1Scope$fHashableScope$fHashable1Scope $fBoundScope $fRead1Scope $fReadScope $fShow1Scope $fShowScope $fOrd1Scope $fOrdScope $fEq1Scope $fEqScope$fMonadTransScope$fApplicativeScope$fTraversableScope$fFunctorScope==compare$fSerializeName $fBinaryName $fSerialName $fSerial1Name $fSerial2Name $fRead2Name $fShow2Name $fOrd2Name $fEq2Name $fRead1Name $fShow1Name $fOrd1Name $fEq1Name $fComonadName$fBitraversableName$fBifoldableName$fBifunctorName$fTraversableName$fFoldableName $fFunctorName $fOrdName$fHashableName$fHashable1Name$fHashable2Name$fEqName