blanks: Fill-in-the-blanks - A library factoring out substitution from ASTs

[ bsd3, language, library, program ] [ Propose Tags ]

Please see the README on GitHub at

[Skip to Readme]
Versions [faq] 0.3.0, 0.4.0, 0.4.1, 0.4.2, 0.5.0
Dependencies adjunctions (>=4.4 && <5), base (>=4.12 && <5), containers (>=0.6 && <1), deepseq (>=1.4 && <2), distributive (>=0.6 && <1), mtl (>=2.2 && <3) [details]
License BSD-3-Clause
Copyright (c) 2019 Eric Conlon
Author Eric Conlon
Category Language
Home page
Bug tracker
Source repo head: git clone
Uploaded by ejconlon at 2020-06-16T21:14:12Z
Distributions NixOS:0.4.2
Downloads 568 total (82 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2020-06-16 [all 1 reports]


[Index] [Quick Jump]


Maintainer's Corner

For package maintainers and hackage trustees

Readme for blanks-0.4.1

[back to package description]



Fill-in-the-blanks - A library factoring out substitution from ASTs.

It's a pain to track de Bruijn indices yourself to implement capture-avoiding subsititution, so this library provides some wrappers that help. One of the best libraries for this is bound, which uses a clever representation to make these operations safe and fast. The tradeoff is that you have to define a Monad instance for your expression functor, which in practice can be tricky. (It's even trickier to derive Eq and Show!)

This library takes the simpler, slower, and rather "succ-y" free-monad-ish approach, but with a twist. It expects you to rewrite all name-binding constructors in your expression as annotations on a single "binder" constructor. This allows you to use the provided Scope type (or a variant) as a wrapper around your expression functor, which is only required to implement Functor. This representation is less safe (since you can inspect and manipulate bound variables), but if you stick to the provided combinators, things will work out fine.

You'll get most of what you want by just importing this module unqualified. See the Blanks class definition and related methods to manipulate variables and abstractions. See Scope for the basic wrapper and LocScope for a wrapper with annotations you can use for source locations and the like. See the test suite for examples.