I want to define Alpha-Equivalence using this data definition
type Sym = Char
data Exp = Var Sym | App Term Exp | Lam Sym Exp
deriving (Eq, Read, Show)
What is the best way to do this?
I want to define Alpha-Equivalence using this data definition
type Sym = Char
data Exp = Var Sym | App Term Exp | Lam Sym Exp
deriving (Eq, Read, Show)
What is the best way to do this?
One way is to convert names to De Bruijn indices, where e.g.
0
refers to the variable bound by the innermost enclosing lambda,1
the next enclosing lambda, and so on. So instead of absolute names, you use relative indices, giving you alpha-equivalence and capture-avoiding substitution for free:To do the conversion, you just keep an environment of the names in scope:
Now, alpha equivalence is simple:
Examples: