bound

Making de Bruijn Succ Less http://github.com/ekmett/bound/

Version on this page:1.0.6
LTS Haskell 9.9:2.0.1
Stackage Nightly 2017-10-20:2.0.1
Latest on Hackage:2.0.1
BSD3 licensed by Edward A. Kmett
Maintained by Edward A. Kmett

Module documentation for 1.0.6

Bound

Hackage Build Status

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 #-}
{-# LANGUAGE TemplateHaskell #-}

import Bound
import Control.Applicative
import Control.Monad
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

instance Monad Exp where
  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

Changes

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

  • SafeHaskell support

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 many examples
  • 100% haddock coverage
  • Added the Name Comonad, to help retain names for bound variables.
  • Bumped dependencies
comments powered byDisqus