# bound

Making de Bruijn Succ Less

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

 Version on this page: 2.0.6@rev:1 LTS Haskell 22.32: 2.0.7@rev:2 Stackage Nightly 2024-08-10: 2.0.7@rev:2 Latest on Hackage: 2.0.7@rev:2

See all snapshots bound appears in

Maintained by
This version can be pinned in stack with:bound-2.0.6@sha256:e986ac4701291fa4c7e7144aef893e32e9f49bdd399a4221d1d8d766e3139280,4427

#### Module documentation for 2.0.6

Depends on 14 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.6 [2023.01.18]

• Allow the examples to build with base-4.18.* (GHC 9.6).

## 2.0.5 [2022.05.07]

• Allow building with transformers-0.6.*.

## 2.0.4 [2021.11.07]

• Allow building with template-haskell-2.18 (GHC 9.2).
• The Bound.TH module no longer requires the TemplateHaskell extension (only TemplateHaskellQuotes) when building with GHC 9.0 or later.
• Drop support for pre-8.0 versions of GHC.

## 2.0.3 [2021.02.05]

• Allow the examples to build with vector-0.12.2 or later.
• The build-type has been changed from Custom to Simple. To achieve this, the doctests test suite has been removed in favor of using cabal-docspec to run the doctests.

## 2.0.2 [2020.10.01]

• Allow building with GHC 9.0.

## 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 doctests 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.2

• Removed unneccesary constraint on hoistScope.

## 1.0.1

• Added a monomorphic hoistScope for Bound.Scope.Simple

## 1.0

• 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.

## 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