-- $Id: FreeBoundVars.hs,v 1.1 2019/10/15 22:11:38 leavens Exp leavens $
module FreeBoundVars where
import LambdaExpression
occursFreeIn :: Var -> Expression -> Bool
occursFreeIn x (Varref y) = x == y
occursFreeIn x (Lambda y body) =
x /= y && occursFreeIn x body
occursFreeIn x (App left right) =
(occursFreeIn x left) || (occursFreeIn x right)
occursFreeIn x _ = False
freeVariables :: Expression -> [Var]
freeVariables (Varref y) = [y]
freeVariables (Lambda y body) =
delete y (freeVariables body)
freeVariables (App left right) =
(freeVariables left) `union` (freeVariables right)
freeVariables _ = []
occursBoundIn :: Var -> Expression -> Bool
occursBoundIn x (Varref y) = False
occursBoundIn x (Lambda y body) =
x == y && occursFreeIn x body
|| occursBoundIn x body
occursBoundIn x (App left right) =
(occursBoundIn x left) || (occursBoundIn x right)
occursBoundIn x _ = False
boundVariables :: Expression -> [Var]
boundVariables (Varref y) = []
boundVariables (Lambda y body) = ([y] `intersect` (freeVariables body))
`union` (boundVariables body)
boundVariables (App left right) =
(boundVariables left) `union` (boundVariables right)
boundVariables _ = []
-- Some set-like operations on lists needed above
union :: Eq a => [a] -> [a] -> [a]
union [] ys = ys
union (x:xs) ys = if x `elem` ys then union xs ys
else x: union xs ys
intersect :: Eq a => [a] -> [a] -> [a]
intersect [] ys = []
intersect (x:xs) ys = if x `elem` ys then x:(xs `intersect` ys)
else xs `intersect` ys
delete :: Eq a => a -> [a] -> [a]
delete x ys = filter (x /=) ys