-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Combinators for manipulating locally-nameless generalized de Bruijn terms
--   
--   Combinators for manipulating locally-nameless generalized de Bruijn
--   terms
@package bound
@version 0.1


module Bound.Term

-- | <tt>substitute p a w</tt> replaces the free variable <tt>a</tt> with
--   <tt>p</tt> in <tt>w</tt>
substitute :: (Monad f, Eq a) => f a -> a -> f a -> f a
isClosed :: Traversable f => f a -> Bool

-- | If a term has no free variables, you can freely change the type of
--   free variables it uses
closed :: Traversable f => f a -> Maybe (f b)


module Bound.Class

-- | This may or may not be a monad transformer,
--   
--   If it is, then you can use <tt>m &gt;&gt;&gt;= f = m &gt;&gt;= lift .
--   f</tt>
--   
--   This is useful for types like expression lists, case alternatives,
--   schemas, etc. that may not be expressions in their own right, but
--   often contain one.
class Bound t
(>>>=) :: (Bound t, Monad f) => t f a -> (a -> f c) -> t f c
(=<<<) :: (Bound t, Monad f) => (a -> f c) -> t f a -> t f c


module Bound.Var
data Var b a
B :: b -> Var b a
F :: a -> Var b a
instance (Eq b, Eq a) => Eq (Var b a)
instance (Ord b, Ord a) => Ord (Var b a)
instance (Show b, Show a) => Show (Var b a)
instance (Read b, Read a) => Read (Var b a)
instance Read b => Read1 (Var b)
instance Show b => Show1 (Var b)
instance Ord b => Ord1 (Var b)
instance Eq b => Eq1 (Var b)
instance Read2 Var
instance Show2 Var
instance Ord2 Var
instance Eq2 Var
instance Bitraversable Var
instance Bifoldable Var
instance Bifunctor Var
instance Monad (Var b)
instance Applicative (Var b)
instance Traversable (Var b)
instance Foldable (Var b)
instance Functor (Var b)


module Bound.Scope

-- | <tt>Scope b f a</tt> is a an <tt>f</tt> expression with bound
--   variables in <tt>b</tt>, and free variables in <tt>a</tt>
--   
--   This stores bound variables as their generalized de Bruijn
--   representation, in that the succ's for variable ids are allowed to
--   occur anywhere within the tree permitting <i>O(1)</i> weakening and
--   allowing more sharing opportunities. Here the deBruijn 0 is
--   represented by the <a>B</a> constructor of <a>Var</a>, while the de
--   Bruijn <a>succ</a> (which may be applied to an entire tree!) is
--   handled by <a>F</a>.
--   
--   NB: equality and comparison quotient out the distinct <a>F</a>
--   placements allowed by the choice of a generalized de Bruijn
--   representation and return the same result as a traditional de Bruijn
--   representation would.
newtype Scope b f a
Scope :: f (Var b (f a)) -> Scope b f a
unscope :: Scope b f a -> f (Var b (f a))

-- | Capture some free variables in an expression to yield a Scope with
--   bound variables
abstract :: Monad f => (a -> Maybe b) -> f a -> Scope b f a

-- | Abstract over a single variable
abstract1 :: (Monad f, Eq a) => a -> f a -> Scope () f a

-- | Enter a scope, instantiating all bound variables
instantiate :: Monad f => (b -> f a) -> Scope b f a -> f a

-- | Enter a scope with one bound variable, instantiating it
instantiate1 :: Monad f => f a -> Scope () f a -> f a

-- | Perform substitution on both bound and free variables in a scope
splat :: Monad f => (a -> f c) -> (b -> f c) -> Scope b f a -> f c

-- | <tt>fromScope</tt> quotients out the possible placements of F in Scope
--   distributing them all to the leaves. This yields a traditional
--   deBruijn indexing scheme for bound variables.
--   
--   <pre>
--   fromScope . toScope = id
--   fromScope . toScope . fromScope = fromScope
--   </pre>
--   
--   <tt>(toScope . fromScope)</tt> is idempotent
fromScope :: Monad f => Scope b f a -> f (Var b a)
toScope :: Monad f => f (Var b a) -> Scope b f a
instance Bound (Scope b)
instance (Functor f, Read b, Read1 f) => Read1 (Scope b f)
instance (Functor f, Read b, Read1 f, Read a) => Read (Scope b f a)
instance (Functor f, Show b, Show1 f) => Show1 (Scope b f)
instance (Functor f, Show b, Show1 f, Show a) => Show (Scope b f a)
instance (Monad f, Ord b, Ord1 f) => Ord1 (Scope b f)
instance (Monad f, Ord b, Ord1 f, Ord a) => Ord (Scope b f a)
instance (Monad f, Eq b, Eq1 f) => Eq1 (Scope b f)
instance (Monad f, Eq b, Eq1 f, Eq a) => Eq (Scope b f a)
instance MonadTrans (Scope b)
instance Monad f => Monad (Scope b f)
instance Traversable f => Traversable (Scope b f)
instance Foldable f => Foldable (Scope b f)
instance Functor f => Functor (Scope b f)


module Bound