!9-      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~(C) 2012-2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportableSafe8bound Instances of # generate left modules over monads.2This means they should satisfy the following laws: m   "a m m  ( x ! k x  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    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.Note:  V isn't "really" a monad transformer, even if the kind matches. Therefore there isn't    instance.boundPerform substitutionIf t is an instance of  MonadTransM and you are compiling on GHC >= 7.4, then this gets the default definition: m  f = m    fboundA flipped version of (). () =  ()11(C) 2012-2013 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportableNoneQBbound&number tells how many layers are there boundUse to automatically derive  and  instances for your datatype.9Also works for components that are lists or instances of <, but still does not work for a great deal of other things.deriving-compat# package may be used to derive the Show1 and Read1 instances {-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE TemplateHaskell #-} import Bound (Scope, makeBound) import Data.Functor.Classes (Show1, Read1, shosPrec1, readsPrec1) import Data.Deriving (deriveShow1, deriveRead1) data Exp a = V a | App (Exp a) (Exp a) | Lam (Scope () Exp a) | ND [Exp a] | I Int deriving (Functor) makeBound ''Exp deriveShow1 ''Exp deriveRead1 ''Exp instance Read a => Read (Exp a) where readsPrec = readsPrec1 instance Show a => Show (Exp a) where showsPrec = showsPrec1  and in GHCi =ghci> :set -XDeriveFunctor ghci> :set -XTemplateHaskell ghci> import Bound (Scope, makeBound) ghci> import Data.Functor.Classes (Show1, Read1, showsPrec1, readsPrec1) ghci> import Data.Deriving (deriveShow1, deriveRead1) ghci> :{ ghci| data Exp a = V a | App (Exp a) (Exp a) | Lam (Scope () Exp a) | ND [Exp a] | I Int deriving (Functor) ghci| makeBound ''Exp ghci| deriveShow1 ''Exp ghci| deriveRead1 ''Exp ghci| instance Read a => Read (Exp a) where readsPrec = readsPrec1 ghci| instance Show a => Show (Exp a) where showsPrec = showsPrec1 ghci| :}  and # instances can be derived similarly import Data.Functor.Classes (Eq1, Ord1, eq1, compare1) import Data.Deriving (deriveEq1, deriveOrd1) deriveEq1 ''Exp deriveOrd1 ''Exp instance Eq a => Eq (Exp a) where (==) = eq1 instance Ord a => Ord (Exp a) where compare = compare1  or in GHCi: &ghci> import Data.Functor.Classes (Eq1, Ord1, eq1, compare1) ghci> import Data.Deriving (deriveEq1, deriveOrd1) ghci> :{ ghci| deriveEq1 ''Exp ghci| deriveOrd1 ''Exp ghci| instance Eq a => Eq (Exp a) where (==) = eq1 ghci| instance Ord a => Ord (Exp a) where compare = compare1 ghci| :} We cannot automatically derive  and > using the standard GHC mechanism, because instances require Exp to be a : {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) boundExtraty type variablesbound&Apply arguments to a type constructor.  (C) 2012 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportableSafeMbound a p w replaces the free variable a with p in w.9substitute "hello" ["goodnight","Gracie"] ["hello","!!!"]["goodnight","Gracie","!!!"]bound a b w replaces a free variable a with another free variable b in w.5substituteVar "Alice" "Bob" ["Alice","Bob","Charlie"]["Bob","Bob","Charlie"]boundjIf 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]bound$A closed term has no free variables. isClosed []TrueisClosed [1,2,3]False(C) 2012 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportable Trustworthy27Xbound"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 .)boundthis is a bound variableboundthis is a free variableboundThis provides a Prism that can be used with lens library to access a bound .  :: Prism (Var b a) (Var b' a) b b'@ boundThis provides a Prism that can be used with lens library to access a free .  :: Prism (Var b a) (Var b a') a a'@ (C) 2013 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportable Trustworthy 127>SX9bound9 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 9 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  instance and no  instance.<bound9Capture some free variables in an expression to yield a 9 with bound variables in b:m + Data.List$abstract (`elemIndex` "bar") "barry"Scope [B 0,B 1,B 2,B 2,F 'y']=boundAbstract over a single variableabstract1 'x' "xyz"Scope [B (),F 'y',F 'z']>bound0Enter a scope, instantiating all bound variables:m + Data.ListLinstantiate (\x -> [toEnum (97 + x)]) $ abstract (`elemIndex` "bar") "barry""abccy"?boundEnter a 9* that binds one variable, instantiating it+instantiate1 "x" $ Scope [B (),F 'y',F 'z']"xyz"AboundA is just another name for ; and is exported to mimick . In particular no  constraint is required.BboundB is just another name for 9 and is exported to mimick . In particular no  constraint is required.Cbound;Perform substitution on both bound and free variables in a 9.Dbound;Return a list of occurences of the variables bound by this 9.Ebound1Perform a change of variables on bound variables.FboundIPerform a change of variables, reassigning both bound and free variables.Gbound>Perform a change of variables on bound variables given only a  instanceHbound A version of F) that can be used when you only have the  instanceIboundMObtain a result by collecting information from both bound and free variablesJboundMObtain a result by collecting information from both bound and free variablesKbound the bound variables in a 9.Lbound? both the variables bound by this scope and any free variables.Mbound,mapM_ over the variables bound by this scopeNboundA L' that can be used when you only have a  instanceObound&Traverse both bound and free variablesPbound&Traverse both bound and free variablesQboundThis allows you to  a 9.Rbound#This is a higher-order analogue of .Sbound9instantiate bound variables using a list of new variablesUbound'mapM over both bound and free variablesVboundA P' that can be used when you only have a  instancejboundSThe monad permits substitution on free variables, while preserving bound variablesmbound; is provides a list (with duplicates) of the free variables 9:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWX 9:;<=>?ABCDEFGHIJKLMNOPUVWX@QTRS(C) 2012-2013 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportable Trustworthy 127>SXsbounds 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  (using n) an entire tree rather than only succ individual variables, but we're still only allowed to do so once per s. 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 .vbound9Capture some free variables in an expression to yield a s with bound variables in b:m + Data.List$abstract (`elemIndex` "bar") "barry"Scope [B 0,B 1,B 2,B 2,F "y"]wboundAbstract over a single variableabstract1 'x' "xyz"Scope [B (),F "y",F "z"]xbound9Capture some free variables in an expression to yield a s with bound variables in b?. Optionally change the types of the remaining free variables.ybound0Enter a scope, instantiating all bound variables:m + Data.ListLinstantiate (\x -> [toEnum (97 + x)]) $ abstract (`elemIndex` "bar") "barry""abccy"zboundEnter a s* that binds one variable, instantiating it+instantiate1 "x" $ Scope [B (),F "y",F "z"]"xyz"{boundFEnter a scope, and instantiate all bound and free variables in one go.|bound|* quotients out the possible placements of  in sx by distributing them all to the leaves. This yields a more traditional de Bruijn indexing scheme for bound variables.Since, |  } "a  we know that |  }  | "a |and therefore (} . |) is idempotent.}boundDConvert from traditional de Bruijn to generalized de Bruijn indices.#This requires a full tree traversal~bound;Perform substitution on both bound and free variables in a s.bound;Return a list of occurences of the variables bound by this s.bound1Perform a change of variables on bound variables.boundIPerform a change of variables, reassigning both bound and free variables.bound>Perform a change of variables on bound variables given only a  instancebound A version of ) that can be used when you only have the  instancebound>Obtain a result by collecting information from bound variablesboundMObtain a result by collecting information from both bound and free variablesbound the bound variables in a s.bound? both the variables bound by this scope and any free variables.bound,mapM_ over the variables bound by this scopeboundA ' that can be used when you only have a  instancebound the bound variables in a s.bound&Traverse both bound and free variablesbound'mapM over both bound and free variablesboundA ' that can be used when you only have a  instanceboundThis allows you to  a s.bound#This is a higher-order analogue of .bound9instantiate bound variables using a list of new variablesbound#Lift a natural transformation from f to g into one between scopes.boundSThe monad permits substitution on free variables, while preserving bound variablesbound; is provides a list (with duplicates) of the free variables"stuvwxyz{|}~"stuvwxyz{|}~(C) 2012 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportable Trustworthy27^boundWe track the choice of  n% as a forgettable property that does not affect the result of () or .)To compare names rather than values, use (  ) instead.bound Extract the .boundThis provides an Iso+ that can be used to access the parts of a .  :: Iso ( n a) ( m b) (n, a) (m, b) bound-Abstraction, capturing named bound variables.boundAbstract over a single variablebound9Capture some free variables in an expression to yield a sZ with named bound variables. Optionally change the types of the remaining free variables.boundfEnter a scope, instantiating all bound variables, but discarding (comonadic) meta data, like its nameboundEnter a s3 that binds one (named) variable, instantiating it.  = z (C) 2012 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportableNonȇ stuvwyz|}stuvwyz|}   !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHI  JKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~  JKLMNPQRSTUVWXYZ[\]bcde^_a`Ofghi|jklqrstnmopuvwxyz{}~"bound-2.0.1-AtZsY3yZaEKLBfeR1JA5NI Bound.ClassBound.TH Bound.Term Bound.VarBound.Scope.Simple Bound.Scope Bound.NameControl.Monad.FreeFreeBoundScopeControl.Monad.TransEitherT fromScopetoScope Data.Functionon>>>==<<<$fBoundWriterT $fBoundStateT$fBoundReaderT $fBoundRWST $fBoundMaybeT $fBoundListT$fBoundIdentityT $fBoundErrorT $fBoundContT makeBound $fShowProp$fShowComponents substitute substituteVarclosedisClosedVarBFunvar_B_F $fNFDataVar $fRead1Var $fShow1Var $fOrd1Var$fEq1Var $fRead2Var $fShow2Var $fOrd2Var$fEq2Var$fBitraversableVar$fBifoldableVar$fBifunctorVar $fMonadVar$fApplicativeVar$fTraversableVar $fFoldableVar $fFunctorVar$fSerializeVar $fBinaryVar $fSerialVar $fSerial1Var $fSerial2Var $fHashableVar$fHashable1Var$fHashable2Var$fEqVar$fOrdVar $fShowVar $fReadVar $fDataVar $fGenericVar $fGeneric1Varunscopeabstract abstract1 instantiate instantiate1 hoistScopesplatbindingsmapBoundmapScope liftMBound liftMScope foldMapBound foldMapScopetraverseBound_traverseScope_ mapMBound_ mapMScope_ traverseBound traverseScopebitraverseScopetransverseScopeinstantiateVarsbitransverseScope mapMBound mapMScopeserializeScopedeserializeScope$fSerializeScope $fBinaryScope $fSerialScope$fSerial1Scope$fHashableScope$fHashable1Scope $fBoundScope $fReadScope $fShowScope $fOrdScope $fEqScope $fRead1Scope $fShow1Scope $fOrd1Scope $fEq1Scope$fMFunctorTYPEScope$fMonadTransScope $fMonadScope$fApplicativeScope$fTraversableScope$fFoldableScope$fFunctorScope $fNFDataScope$fGenericScope $fDataScope$fGeneric1ScopeabstractEitherinstantiateEitherNamename_Name abstractName abstract1NameabstractEitherNameinstantiateNameinstantiate1NameinstantiateEitherName $fNFDataName$fSerializeName $fBinaryName $fSerialName $fSerial1Name $fSerial2Name $fRead1Name $fShow1Name $fOrd1Name $fEq1Name $fRead2Name $fShow2Name $fOrd2Name $fEq2Name $fComonadName$fBitraversableName$fBifoldableName$fBifunctorName$fTraversableName$fFoldableName $fFunctorName $fOrdName$fHashableName$fHashable1Name$fHashable2Name$fEqName $fShowName $fReadName $fDataName $fGenericName$fGeneric1NamebaseGHC.Basereturn>>=transformers-0.5.5.0Control.Monad.Trans.Classlift.flipFunktor ApplicativeMonadFunctorghc-prim GHC.ClassesEqOrdtypeVarsconAppsT Data.EitherEither Data.Foldable traverse_Data.TraversabletraverseData.Bitraversable bitraversetoListGHC.Enumsuccid==compare