b[].      !"#$%&'()*+,-portable experimentalEdward Kmett <ekmett@gmail.com> Safe-Inferred 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"]CIf 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]Falseportable experimentalEdward Kmett <ekmett@gmail.com> Safe-Inferred Instances of ' may or may not be monad transformers. If they are, then m  f "a m . / 0 f is required to hold, and is 0 in fact the default definition. If it is not a 1 instance, then > you have greater flexibility in how to implement this class. CThis is useful for types like expression lists, case alternatives, I schemas, etc. that may not be expressions in their own right, but often  contain expressions. Perform substitution If t is an instance of  MonadTrans0 and you are compiling on GHC >= 7.4, then this  gets the default definition: m  f = m . / 0 fA flipped version of (). () = 2 ()portable experimentalEdward Kmett <ekmett@gmail.com>None"I am not a number, I am a  free monad!" A  b a" is a variable that may either be "bound" ( ) or "free" (). G(It is also technically a free monad in the same near-trivial sense as  3.) this is a free variable this is a bound variable  4 56789:;<=>?@ABCDEFGHIJKLMN    4 56789:;<=>?@ABCDEFGHIJKLMNportable experimentalEdward Kmett <ekmett@gmail.com>None   b f a is an f$ expression with bound variables in b,  and free variables in a 8We store bound variables as their generalized de Bruijn  representation in that we're allowed to / (using  ) an entire 8 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 O6 (which may be applied to an entire tree!) is handled  by . 6NB: equality and comparison quotient out the distinct  placements D allowed by the generalized de Bruijn representation and return the > same result as a traditional de Bruijn representation would. ELogically 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 /. 6Capture 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 variable abstract1 'x' "xyz"Scope [B (),F "y",F "z"]1Enter 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   H by distributing them all to the leaves. This yields a more traditional 0 de Bruijn indexing scheme for bound variables. Since,   0  "a P we know that   0  0  "a and therefore ( . ) is idempotent. EConvert 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  . 2Perform a change of variables on bound variables. JPerform a change of variables, reassigning both bound and free variables. >Perform a change of variables on bound variables given only a Q  instance  A version of ) that can be used when you only have the Q  instance CObtain a result by collecting information from both bound and free  variables CObtain a result by collecting information from both bound and free  variables R the bound variables in a  . S@ 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 Q  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 Q  instance TCThe monad permits substitution on free variables, while preserving  bound variables UV< is provides a list (with duplicates) of the free variables /  !"#$%WXYZ[\]^_`abcdefTgUh  !"#$%  !"#$%-   !"#$%WXYZ[\]^_`abcdefTgUhportable experimentalEdward Kmett <ekmett@gmail.com>None&We track the choice of & n% as a forgettable property that does not affect  the result of (i) or j. )To compare names rather than values, use ( j () instead. ( Extract the (. )This provides an Iso+ that can be used to access the parts of a &.   ) :: Iso (& n a) (& m b) (n, a) (m, b) *.Abstraction, capturing named bound variables. + Abstract over a single variable ,MEnter a scope, instantiating all bound variables, but discarding (comonadic)  meta data, like its name -Enter a  4 that binds one (named) variable, instantiating it. - = !&'()*+,-klmnopqrstuvwxyz{|}~&'()*+,-&')(*+,- &'()*+,-klmnopqrstuvwxyz{|}~portable experimentalEdward Kmett <ekmett@gmail.com>None         !"#$%&'()*+,--./012345678945:78;45<4=>?@ABCDEFGHIJKLMNOPQRSTUVWXY4Z[45\45]4^_4`abc4^defghijklmnopqrstuvwxywxz{|}~ bound-0.8 Bound.Term Bound.Class Bound.Var Bound.Scope Bound.Name Data.FunctiononBound substitute substituteVarclosedisClosed>>>==<<<VarFBunvarScopeunscopeabstract abstract1 instantiate instantiate1 fromScopetoScopesplatbindingsmapBoundmapScope liftMBound liftMScope foldMapBound foldMapScopetraverseBound_traverseScope_ mapMBound_ mapMScope_ traverseBound traverseScope mapMBound mapMScopeserializeScopedeserializeScopeNamename_Name abstractName abstract1NameinstantiateNameinstantiate1NamebaseGHC.Base>>=transformers-0.3.0.0Control.Monad.Trans.Classlift. MonadTransflip Data.EitherEither distinguisher_B_F $fRead1Var $fShow1Var $fOrd1Var$fEq1Var $fRead2Var $fShow2Var $fOrd2Var$fEq2Var$fBitraversableVar$fBifoldableVar$fBifunctorVar $fMonadVar$fApplicativeVar$fTraversableVar $fFoldableVar $fFunctorVar$fSerializeVar $fBinaryVar $fSerialVar $fSerial1Var $fSerial2Var $fHashableVar$fHashable1Var$fHashable2VarGHC.EnumsuccidMonad Data.Foldable traverse_Data.Traversabletraverse $fMonadScope$fFoldableScopetoList$fSerializeScope $fBinaryScope $fSerialScope$fSerial1Scope$fHashableScope$fHashable1Scope $fBoundScope $fRead1Scope $fReadScope $fShow1Scope $fShowScope $fOrd1Scope $fOrdScope $fEq1Scope $fEqScope$fMonadTransScope$fTraversableScope$fFunctorScopeghc-prim GHC.Classes==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