# bound

Making de Bruijn Succ Less

http://github.com/ekmett/bound/

 Version on this page: 2.0.1@rev:7 LTS Haskell 21.24: 2.0.7 Stackage Nightly 2023-12-08: 2.0.7 Latest on Hackage: 2.0.7

See all snapshots `bound` appears in

Maintained by
This version can be pinned in stack with:`bound-2.0.1@sha256:b94060debe96f7b9764a08e3caa63f7dbc632c445037f107c6cd2a846f2eb92a,4762`

#### Module documentation for 2.0.1

Depends on 13 packages(full list with versions):

# Bound

## Goals

This library provides convenient combinators for working with “locally-nameless” terms. These can be useful when writing a type checker, evaluator, parser, or pretty printer for terms that contain binders like forall or lambda, as they ease the task of avoiding variable capture and testing for alpha-equivalence.

See the documentation on hackage for more information, but here is an example:

``````{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}

import Bound
import Control.Applicative
import Data.Functor.Classes
import Data.Foldable
import Data.Traversable
import Data.Eq.Deriving (deriveEq1)      -- these two are from the
import Text.Show.Deriving (deriveShow1)  -- deriving-compat package

infixl 9 :@
data Exp a = V a | Exp a :@ Exp a | Lam (Scope () Exp a)
deriving (Eq,Show,Functor,Foldable,Traversable)

instance Applicative Exp where pure = V; (<*>) = ap

return = V
V a      >>= f = f a
(x :@ y) >>= f = (x >>= f) :@ (y >>= f)
Lam e    >>= f = Lam (e >>>= f)

lam :: Eq a => a -> Exp a -> Exp a
lam v b = Lam (abstract1 v b)

whnf :: Exp a -> Exp a
whnf (f :@ a) = case whnf f of
Lam b -> whnf (instantiate1 a b)
f'    -> f' :@ a
whnf e = e

deriveEq1 ''Exp
deriveShow1 ''Exp

main :: IO ()
main = do
let term = lam 'x' (V 'x') :@ V 'y'
print term         -- Lam (Scope (V (B ()))) :@ V 'y'
print \$ whnf term  -- V 'y'
``````

There are longer examples in the examples/ folder.

## Contact Information

Contributions and bug reports are welcome!

Please feel free to contact me through github or on the #haskell IRC channel on irc.freenode.net.

-Edward Kmett

## 2.0.1

• Add `abstractEither` and `instantiateEither` to `Bound.Scope`, and add `abstractEitherName` and `instantiateEitherName` to `Bound.Scope.Name`
• Add `Generic(1)` instances for `Name` and `Scope`
• Support `doctest-0.12`

## 2

• GHC 8.0 and 8.2 support
• Converted from `prelude-extras` to `transformers` + `transformers-compat` for the `Eq1`, `Ord1`, `Show1`, and `Read1` functionality.
• `makeBound` supports `Functor` components
• Add `MFunctor` instance for `Scope`
• Add `NFData` instances for `Name`, `Scope`, and `Var`
• Revamp `Setup.hs` to use `cabal-doctest`. This makes it build with `Cabal-1.25`, and makes the `doctest`s work with `cabal new-build` and sandboxes.

## 1.0.7

• Added an `-f-template-haskell` option to allow disabling `template-haskell` support. This is an unsupported configuration but may be useful for expert users in sandbox configurations.
• Support `cereal` 0.5

## 1.0.6

• Compiles warning-free on GHC 7.10

## 1.0.5

• Widened version bound on `bifunctors`.
• Widened version bound on `profunctors`.

## 1.0.4

• Widened version bound on `transformers`.

## 1.0.3

• Added `bitransverseScope`.

## 1.0.2

• Removed unneccesary constraint on `hoistScope`.

## 1.0.1

• Added a monomorphic `hoistScope` for `Bound.Scope.Simple`

## 1.0

• Added instances for `Bound` for all of the `mtl` monads.
• Added `Data` and `Typeable` support to both versions of `Scope`
• Added the missing `Applictive` instance to `Bound.Scope.Simple`
• Moved `hoistScope`, `bitraverseScope`, `transverseScope`, and `instantiateVars` here from the `ermine` compiler.

## 0.9.1.1

• Updated to work with `bifunctors` 4.0

## 0.9.1

• Updated to work with `comonad` 4.0 and `profunctors` 4.0

## 0.9

• Added the missing instance for `Applicative (Scope b f)`

## 0.8

• Added `Serial`, `Binary` and `Serialize` instances for `Scope`.

## 0.7

• Added `Hashable`, `Hashable1` and `Hashable2` instances where appropriate for `Name`, `Var` and `Scope`.

## 0.6.1

• More aggressive inlining
• Added `unvar`, `_B`, `_F` to `Bound.Var`.
• Added `_Name` to `Bound.Name`.

## 0.6

• Support for `prelude-extras` 0.3

## 0.5.1

• Removed my personal inter-package dependency upper bounds
• Updated doctest suite to use exact versions.

## 0.5

• Created a `doctest`-based test suite
• Added the `Name` `Comonad`, to help retain names for bound variables.