Safe Haskell | Safe |
---|

# Exercises 2 and 3

See ../pdfs/05.pdf.

Lambda terms: variables, application, abstraction.

# Exercise 4

The set of all variables occurring in a term. For example

vars (App (Var "x") (Abs "y" (Var "y"))) == ["x", "y"]

The set of free variables occurring in a term. For example

fvs (App (Var "x") (Abs "y" (Var "y"))) == ["x"]

# Exercise 5

freshName :: Id -> [Id] -> (Id, Term -> Term) Source #

Given a variable `x`

and a set of variable names to avoid `ys`

, `freshName x ys`

computes a pair `(x', ren)`

such that `x'`

is a variable that is fresh for `ys`

(that is, different from all elements of `ys`

) and `ren :: Term -> Term`

is a
function that renames all occurrences of `x`

in a term by `x'`

.